1、二叉树的定义
二叉树(Binary Tree)是一种特殊的树型结构,每个节点至多有两棵子树,且二叉树的子树有左右之分,次序不能颠倒。
由定义可知,二叉树中不存在度(结点拥有的子树数目)大于2的节点。二叉树形状如下下图所示:
2、二叉树的性质
(1)在二叉树中的第i层上至多有2^(i-1)个结点(i>=1)。备注:^表示此方
(2)深度为k的二叉树至多有2^k-1个节点(k>=1)。
(3)对任何一棵二叉树T,如果其终端结点数目为n0,度为2的节点数目为n2,则n0=n2+1。
满二叉树:深度为k且具有2^k-1个结点的二叉树。即满二叉树中的每一层上的结点数都是最大的结点数。
完全二叉树:深度为k具有n个结点的二叉树,当且仅当每一个结点与深度为k的满二叉树中的编号从1至n的结点一一对应。
可以得到一般结论:满二叉树和完全二叉树是两种特殊形态的二叉树,满二叉树肯定是完全二叉树,但完全二叉树不不一定是满二叉树。
举例如下图是所示:
(4)具有n个节点的完全二叉树的深度为log2n + 1。
3、二叉树的存储结构
可以采用顺序存储数组和链式存储二叉链表两种方法来存储二叉树。经常使用的二叉链表方法,因为其非常灵活,方便二叉树的操作。二叉树的二叉链表存储结构如下所示:
1 typedef struct binary_tree_node
2 {
3 int elem;
4 struct binary_tree_node *left;
5 struct binary_tree_node *right;
6 }binary_tree_node,*binary_tree;
举例说明二叉链表存储过程,如下图所示:
从图中可以看出:在还有n个结点的二叉链表中有n+1个空链域。
4、遍历二叉树
遍历二叉树是按照指定的路径方式访问书中每个结点一次,且仅访问一次。由二叉树的定义,我们知道二叉数是由根结点、左子树和右子树三部分构成的。通常遍历二叉树是从左向右进行,因此可以得到如下最基本的三种遍历方法:
(1)先根遍历(先序遍历):如果二叉树为空,进行空操作;否则,先访问根节点,然后先根遍历左子树,最后先根遍历右子树。采用递归形式实现代码如下:
1 void preorder_traverse_recursive(binary_tree root)
2 {
3 if(NULL != root)
4 {
5 printf("%d\t",root->elem);
6 preorder_traverse_recursive(root->left);
7 preorder_traverse_recursive(root->right);
8 }
9 }
具体过程如下图所示:
(2)中根遍历(中序遍历):如果二叉树为空,进行空操作;否则,先中根遍历左子树,然后访问根结点,最后中根遍历右子树。递归过程实现代码如下:
1 void inorder_traverse_recursive(binary_tree root)
2 {
3 if(NULL != root)
4 {
5 inorder_traverse_recursive(root->left);
6 printf("%d\t",root->elem);
7 inorder_traverse_recursive(root->right);
8 }
9 }
具体过程如下图所示:
(3)后根遍历(后序遍历):如果二叉树为空,进行空操作;否则,先后根遍历左子树,然后后根遍历右子树,最后访问根结点。递归实现代码如下:
1 void postorder_traverse_recursive(binary_tree root)
2 {
3 if(NULL != root)
4 {
5 postorder_traverse_recursive(root->left);
6 postorder_traverse_recursive(root->right);
7 printf("%d\t",root->elem);
8 }
9 }
具体过程如下图所示:
用类和指针实现的二叉树:
#include<iostream>
using namespace std;
struct tree
{
int data;
tree *left,*right;
};
class Btree
{
static int n;
static int m;
public:
tree *root;
Btree()
{
root=NULL;
}
void create_Btree(int);
void Preorder(tree *); //先序遍历
void inorder(tree *); //中序遍历
void Postorder(tree *); //后序遍历
void display1() {Preorder(root); cout<<endl;}
void display2() {inorder(root);cout<<endl;}
void display3() {Postorder(root); cout<<endl;}
int count(tree *); //计算二叉树的个数
int findleaf(tree *); //求二叉树叶子的个数
int findnode(tree *); //求二叉树中度数为1的结点数量,这是当初考数据结构时候的最后一道题目
};
int Btree::n=0;
int Btree::m=0;
void Btree::create_Btree(int x)
{
tree *newnode=new tree;
newnode->data=x;
newnode->right=newnode->left=NULL;
if(root==NULL)
root=newnode;
else
{
tree *back;
tree *current=root;
while(current!=NULL)
{
back=current;
if(current->data>x)
current=current->left;
else
current=current->right;
}
if(back->data>x)
back->left=newnode;
else
back->right=newnode;
}
}
int Btree::count(tree *p)
{
if(p==NULL)
return 0;
else
return count(p->left)+count(p->right)+1; //这是运用了函数嵌套即递归的方法。
}
void Btree::Preorder(tree *temp) //这是先序遍历二叉树,采用了递归的方法。
{
if(temp!=NULL)
{
cout<<temp->data<<" ";
Preorder(temp->left);
Preorder(temp->right);
}
}
void Btree::inorder(tree *temp) //这是中序遍历二叉树,采用了递归的方法。
{
if(temp!=NULL)
{
inorder(temp->left);
cout<<temp->data<<" ";
inorder(temp->right);
}
}
void Btree::Postorder(tree *temp) //这是后序遍历二叉树,采用了递归的方法。
{
if(temp!=NULL)
{
Postorder(temp->left);
Postorder(temp->right);
cout<<temp->data<<" ";
}
}
int Btree::findleaf(tree *temp)
{
if(temp==NULL)return 0;
else
{
if(temp->left==NULL&&temp->right==NULL)return n+=1;
else
{
findleaf(temp->left);
findleaf(temp->right);
}
return n;
}
}
int Btree::findnode(tree *temp)
{
if(temp==NULL)return 0;
else
{
if(temp->left!=NULL&&temp->right!=NULL)
{
findnode(temp->left);
findnode(temp->right);
}
if(temp->left!=NULL&&temp->right==NULL)
{
m+=1;
findnode(temp->left);
}
if(temp->left==NULL&&temp->right!=NULL)
{
m+=1;
findnode(temp->right);
}
}
return m;
}
void main()
{
Btree A;
int array[]={100,4,2,3,15,35,6,45,55,20,1,14,56,57,58};
int k;
k=sizeof(array)/sizeof(array[0]);
cout<<"建立排序二叉树顺序: "<<endl;
for(int i=0;i<k;i++)
{
cout<<array[i]<<" ";
A.create_Btree(array[i]);
}
cout<<endl;
cout<<"二叉树节点个数: "<<A.count(A.root)<<endl;
cout<<"二叉树叶子个数:"<<A.findleaf(A.root)<<endl;
cout<<"二叉树中度数为1的结点的数量为:"<<A.findnode(A.root)<<endl;
cout<<endl<<"先序遍历序列: "<<endl;
A.display1();
cout<<endl<<"中序遍历序列: "<<endl;
A.display2();
cout<<endl<<"后序遍历序列: "<<endl;
A.display3();
}
分享到:
相关推荐
平衡二叉树c++模版,此模版採用二叉链表实现,是本人一个通宵搞出来的。可以提供时间复杂度在nlgn的排序,也可以提供lgn的查询。是一个很不错的数据结构,可是以和其它的现在比较新的一些数据结构比美。虽然有人对其...
通过二级指针对二叉树进行创建,不使用二级指针对树进行创建。
编写程序实现二叉树的如下操作: 1) 建立二叉链表 2) 二叉树的先序、中序、后序遍历 3) 求解二叉树的叶子结点个数 4) 将二叉树中所有结点的左、右子树相互交换 输入: 扩展二叉树先序序列:ab#d##ce###。其中#...
要求:按先序遍历规则,从键盘连续输入二叉树的先序序列,若无孩子结点,则用#代替,以示空指针的位置;然后调用构造二叉链表的递归算法,从屏幕显示该二叉链表的先序序列。 2、分别调用先序、中序、后序遍历算法对...
实现了二叉树的前序递归创建,非递归层次创建,非递归前序加中序创建;前序、中序、后序的递归遍历以及前、中、后、层次的非递归遍历;操作方面,使用后序递归遍历实现了size()和height()方法;除此,还有find...
①输入aa则返回的指针指向的二叉树应该就是仅有一个节点,值为a. ②输入123213则返回的指针指向的二叉树应该就是,根节点(1),左子树只有一个节点(2),右子树只有一个节点(3) ③输入1313则返回的指针指向的...
。。。
/* 设栈元素为二叉树的指针类型 */ typedef struct { QElemType *base; int front; /* 头指针,若队列不空,指向队列头元素 */ int rear; /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */ } SqQueue; ...
输入一组关键字序列,并以此顺序建立一棵平衡二叉树(提示:为简化运算,可采用含有左、右子树高度和指向父母的指针的三叉链表表示),并在建树过程中用逆中序法输出每次插入新结点后的平衡二叉树形状。
实验目的: (1)进一步掌握指针变量的使用。 (2)掌握_一叉树的结构特征以及各种存储结构的特点及使用范围。 (3)掌握用指针类型描述、访问和处理二叉树的运算。 (4)掌握栈或队列的使用。
//C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include “stdafx.h”#include<iostream>#include<string>#include <stack>using namespace std;template<class>struct BiNode{ T data; struct...
二叉树实现源代码 经典版c++源码 *建立二叉树算法描述: 用ch扫描采用括号表示法表示二叉树的字符串Str。分以下几种情况: 1、若ch='('则将前面刚创建的结点作为双亲结点进栈,并置k=1,表示其后创建的结点将做为这...
根据二叉树的抽象数据类型的定义,使用二叉链表实现一个二叉树。 二叉树的基本功能: 1、二叉树的建立 2、前序遍历二叉树 3、中序遍历二叉树 4、后序遍历二叉树 5、按层序遍历二叉树 6、求二叉树的深度 7、求指定...
二叉树的建立,利用左右孩子指针,查找节点并求指定节点路径
数据结构 实习 全部 c++ 指针 线性表 树 二叉树 遍历 线序遍历 中序遍历 后续遍历 堆栈 入栈 出栈 队列
二叉树的链式数据结构struct tree /* 声明树的结构 */ { struct tree *left; /* 存放左子树的指针 */ int data; /* 存放节点数据内容 */ struct tree *right; /* 存放右子树的指针 */ }; typedef struct tree ...
题 目 二叉排序树与平衡二叉树的实现 1、课程设计的目的 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法,以及它们在程序中的使用方法。 使学生掌握软件设计的基本内容...
基于C++、文件操作和Huffman算法实现图片压缩源码+使用说明+详细注释+sln解决方案.zip ——使用C++、文件操作和Huffman算法实现“图片压缩程序”。 ## 1. 核心知识 (1) 树的存储结构 (2) 二叉树的三种遍历方法...
4.5 比较基于数组的实现和基于链表的实现 148 第5章 作为问题求解技术的递归 155 5.1 定义语言 156 5.1.1 语法知识基础 156 5.1.2 两种简单的语言 158 5.2 代数表达式 160 5.2.1 代数表达式的类型 160 5.2.2 ...
寻找中序线索化二叉树指定结点的后继 动画讲解