数据结构【五-1】:二叉树（C++）

发表于 更新于 分类于   |   字数统计: 4k(字)   |   阅读时长≈ 17(分)

树的一些易混相关概念

1、 结点拥有的子树数称为结点的度（Degree）。树的度是树内各结点度的最大值。

2、树的深度（Depth）或高度是树中结点的最大层次数值。

3、祖先结点：从根结点到该结点所经分支上的所有结点。

4、子孙节点：某一结点的子女以及这些子女的子女。

二叉树

参考文：

图解数据结构-树

数据结构中的各种树

非递归构建二叉树

理解前序中序后序遍历

二叉树的特点

  • 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。
  • 左子树和右子树是有顺序的，次序不能任意颠倒。
  • 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树五种基本形态

  1. 空二叉树
  2. 只有一个根结点
  3. 根结点只有左子树
  4. 根结点只有右子树
  5. 根结点既有左子树又有右子树

几种特殊的二叉树

斜树

​ 又分为左斜树、右斜树。结点个数与二叉树深度相同

​

满二叉树

除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上。

完全二叉树

若设二叉树的深度为h，只看前1~（n-1)层则是满二叉树，第h层所有的结点都连续集中在最左边，这就是完全二叉树。

一个具有n个节点的完全二叉树，其叶子节点的个数为?

n1=0，n为奇数时：n0 = (n+1) / 2

n1=1，n为偶数时：n0 = n / 2

二叉树的性质

  • 性质1：在二叉树的第i层上至多有2i-1个结点（i>=1）

  • 性质2：深度为k的二叉树至多有2k-1个结点（k>=1）—–a1=1 公比为2的等比数列求和

  • 性质3：对任何一棵二叉树T，如果其叶子数为n0,度为2的结点数为n2，则n0 = n2+1。

  • 证明:一棵二叉树，除了终端结点（叶子结点），就是度为1或2的结点。假设n1度为1的结点数，则数T 的结点总数n=n0+n1+n2。我们再换个角度，看一下树T的连接线数，由于根结点只有分支出去，没有分支进入，所以连接线数为结点总数减去1。也就是n-1=n1+2n2，可推导出n0+n1+n2-1 = n1+2n2，继续推导可得n0 = n2+1。

  • 性质4：具有n个结点的完全二叉树的深度为[log2（n+ 1） ] (向上取整)或者[log2n ]+1（向下取整） 。

  • 性质5：如果对一颗有n个结点的完全二叉树（其深度为[log2n ] + 1）的结点按层序编号（从第1层到第[log2n ] + 1层，每层从左到右），对任一结点i(1<=i<=n)有：

    1. 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2]。
    2. 如果2i>n,则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点i。
    3. 如果2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1。
    4. 结点i所在层次为[log2i ]+1（向下取整）

    性质5其实就是顺序储存下父子结点编号关系

顺序结构实现二叉树

利用性质5可以对数组下标操作完成二叉树储存

二叉树的顺序存储结构缺点很明显：不能反应逻辑关系；对于特殊的二叉树（左斜树、右斜树），浪费存储空间。所以二叉树顺序存储结构一般只用于完全二叉树。

对于右斜树，顺序存储结构浪费存储空间：

^表示其中数据为空

链式结构实现二叉树

​ 二叉链表:

三叉链表：

三叉链表在二叉链表的基础上添加一个返回指针指向父亲结点

含n个结点的二叉链表有n+1个空链指针域

含n个结点的三叉链表有n+2个空链指针域

关于遍历顺序

前序遍历顺序：规则是先是根结点，再前序遍历左子树，再前序遍历右子树

中序遍历顺序：规则是先中序遍历左子树，再是根结点，再是中序遍历右子树

后序遍历顺序：规则是先后序遍历左子树，再是后序遍历右子树，再是根结点

详细解释:

1、对于每个节点，访问顺序为遍历顺序

2、！对于每个节点，左子树的节点全部访问完，再能再根据遍历顺序访问右子树的节点。！！！！！！

根据这两条规则我们就能够确定其中任意一种遍历的顺序了。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
#include<iostream>
#include <algorithm>
int defaultSize=100; 
using namespace std;
template <class T> 
struct Node
{
	T data;
	Node<T> *left=NULL,*right=NULL;
} ;
template <class T> 
class Btree
{
	public:
		Btree();
		void creatBtree_Qian(Node<T> *&p,T t);//前序创建二叉树 ，这里以t为标志表示 参数必须为结点指针的引用 
		void output_Qian(Node<T> *p);		//前序遍历 
		void output_Qian_Suojin(Node<T> *p,int n);		//前序遍历的缩进输出表示
		//用n来表示层数控制函数中的‘-’输出 该结点在第几次就输出几个 ‘-’
		void output_Zhong(Node<T> *p);		//中序遍历 
		void output_Hou(Node<T> *p);		//后序遍历 
		void output_Level(Node<T> *p);		//层次遍历 
		Node<T> * search_Qian(Node<T> *p,T x);		//前序遍历查询函数并返回结点的地址 
		bool equal(Node<T> *p,Node<T> *q);//判断两棵树是否相同 
		Node<T>* getRoot();					//获取树根结点 
		bool isEmpty();						//判空函数 
		void destroy(Node<T> *p);			//删除根为p的子树
		int nodeNumbers(Node<T> *p);			//计算结点个数 
		int deepth(Node<T> *p);				//计算树的高度或者深度 
		void countPoint(Node<T> *p,int num[]);//计算二叉树度为0,1,2的结点个数保存在一个数组中 
		void countWidth(Node<T> *p,int num[],int a);//计算二叉树每一层结点个数保存在一个数组中a需要手动赋初始值0或者1 
	protected:
	Node<T> *root;
};
template <class T> 
Btree<T>::Btree()
{
	root=NULL;
}
template <class T> 
void Btree<T>::creatBtree_Qian(Node<T> *&p,T t) //参数必须为结点指针的引用 否则无法链接起来各个结点 
{ 	
	T a;							//我们的操作步骤如下： 
	cin>>a;							
	if(a==t)						//1、根据输入字符 判断 是否按照相应顺序存入数据				
	 return;					
	p=new Node<T>;					 //2、若需要存入数据，我们需要创建并且链接一个结点 
	p->data=a;						//3、之后根据我们相应的创建顺序，决定数据的存放顺序  
	creatBtree_Qian(p->left,t);		 //4、这里是前序，所以，我们存数据，对左结点继续操作 
	creatBtree_Qian(p->right,t);	//5、确认左结点创建完毕后 对右结点操作 
	root=p;							//6、将根结点赋给root; 
}
template <class T> 
void Btree<T>::output_Qian(Node<T> *p)
{
	if(p!=NULL)
	{
	cout<<p->data<<" ";
	output_Qian(p->left);
	output_Qian(p->right);
	}
}
template <class T> 
void Btree<T>::output_Qian_Suojin(Node<T> *p,int n)	//用n来表示层数控制函数中的‘-’输出 该结点在第几次就输出几个 ‘-’
{
	if(p!=NULL)
	{
	for(int i=0;i<n;i++)
	cout<<"-";
	cout<<p->data<<" "<<endl;
	output_Qian_Suojin(p->left,n+1);			//进入递归，代表进入子结点，层数+1; 
	output_Qian_Suojin(p->right,n+1);			
	}
}
template <class T> 
void Btree<T>::output_Zhong(Node<T> *p)
{
	if(p!=NULL)
	{
	output_Zhong(p->left);
	cout<<p->data<<" ";
	output_Zhong(p->right);
	}
}
template <class T> 
void Btree<T>::output_Hou(Node<T> *p)
{
	if(p!=NULL)
	{
	output_Hou(p->left);
	output_Hou(p->right);
	cout<<p->data<<" ";
	}
}
template <class T> 
void Btree<T>::output_Level(Node<T> *p)
{
	Node<T> *Queue[defaultSize];			//建立一个容量100的结点指针数组作为队列 
	int front=0,rear=0;				//建立队首和队位指针 
	if(!isEmpty())					//判空 
	{
		Queue[rear++]=p;						//1、先将根入队
		while(front!=rear)						//2、设置队列非空循环条件 
		{
			cout<<Queue[front]->data<<" ";		//3、输出结点的值 
			if(Queue[front]->left!=NULL)		//4、若该结点左子树不为空则入队列
			{
				Queue[rear]=Queue[front]->left;	//补充:注意先存数据再将尾指针加1 
				rear=(rear+1)%defaultSize;		//5、为了充分使用空间，我们使用循环队列，队尾+1取余 
			}
		
			if(Queue[front]->right!=NULL)		//6、若该结点右子树不为空则入队列
			{
				Queue[rear]=Queue[front]->right; 
				rear=(rear+1)%defaultSize;		//7、同理队尾+1取余 
			}
			front=(front+1)%defaultSize;		//8、将输出过的结点出队列 
		} 				
	} 	
} 
template <class T> 
Node<T> * Btree<T>::search_Qian(Node<T> *p,T x)		//bool型为查询到就终止准备 
{
	Node<T> * t=NULL;
	if(p!=NULL)
	{
		if(p->data==x)
		return p;				//查询到就返回 
		t=search_Qian(p->left,x);
		if(t==NULL)
		//只有当左子树没有查询到我们才进入右子树查询，节省空间。同时防止左子树查询到t=结点地址后进入右子树查询失败导致t=NULL的覆盖				
		t=search_Qian(p->right,x);
	}
	return t;						//最终返回t作为结果 
}
template <class T> 
Node<T>* Btree<T>::getRoot()
{
	return root;
}
template <class T> 
bool Btree<T>::isEmpty()
{
	if(root==NULL)
	return true;
	else
	return false;
}
template <class T> 
void  Btree<T>::destroy(Node<T> *p)
{
	if(p!=NULL)
	{
		destroy(p->left);
		destroy(p->right);
		delete p;
	} 
}
template <class T> 
int  Btree<T>::nodeNumbers(Node<T> *p)
{
	if(p==NULL) return 0;
    return nodeNumbers(p->left) + nodeNumbers(p->right) + 1;		//巧妙递归计算左子树节点数+右子树节点数+根=节点数 
}
template <class T> 
int  Btree<T>::deepth(Node<T> *p)
{
	if(p==NULL) return 0;
    int leftDeepth=deepth(p->left);
    int rightDeepth=deepth(p->right);
    return max(leftDeepth,rightDeepth)+1;				//max()函数需要头文件#include <algorithm> 
}
template <class T> 
void Btree<T>::countPoint(Node<T> *p,int num[])		//计算二叉树度为0,1,2的结点个数保存在一个数组中
{
	if(p!=NULL)
	{
		if(p->left!=NULL&&p->right!=NULL)			//左右结点都不为空 2度结点+1 
			num[2]++;
		else
		if(p->left==NULL&&p->right==NULL)			//左右结点都为空 0度结点+1 
		num[0]++;
		else										//左否则 1度结点+1
		num[1]++;
		countPoint(p->left,num);					
		countPoint(p->right,num);
	}
} 
template <class T> 
void Btree<T>::countWidth(Node<T> *p,int num[],int a)		//计算二叉树每一层的结点数，最后保存在数组中。
{
	if(p!=NULL)
	{
		num[a]++;
		countWidth(p->left,num, a+1);
		countWidth(p->right,num, a+1);
	}
} 
template <class T> 
bool  Btree<T>::equal(Node<T> *p,Node<T> *q)
{
	bool t=true;
	if(p!=NULL&&q!=NULL)
	{
		if(p->data!=q->data)
		return false;	
		t=equal(p->left,q->left);
		if(t==true)					//当左子树相同的时候才比较右子树，提高效率，节省空间 
		t=equal(p->right,q->right);
	}
	else if((p!=NULL&&q==NULL)||(p==NULL&&q!=NULL))
	return false;	
	return t;
} 
int main()
{
	
	Btree<int> test;					//测试数据:1 2 3 -1 -1 4 -1 -1 5 -1 6 -1 -1
	Node<int> *t;						//test.getRoot()这个函数返回值不能直接作为参数放到 test.creatBtree_Qian();中会编译报错。
	test.creatBtree_Qian(t,-1);			//用t存起来再放进去就可以运行。 
	test.output_Qian(test.getRoot());
	cout<<endl; 
	test.output_Zhong(test.getRoot());
	cout<<endl;
	test.output_Hou(test.getRoot());
	cout<<endl;
	cout<<test.nodeNumbers(test.getRoot());
	cout<<endl;
	cout<<test.deepth(test.getRoot());
	cout<<endl;
	test.output_Level(test.getRoot()); 
	cout<<endl; 
	if(test.search_Qian(t,5)!=NULL)
	cout<<"success and is"<<test.search_Qian(t,5)->data<<endl;
	else
	cout<<"false"<<endl; 
	int s[3]={0};
	test.countPoint(t,s);
	for(int i=0;i<3;i++)
	cout<<s[i]<<endl;
	int num[10]={0};
	test.countWidth(t,num,0);
	for(int i=0;i<10;i++)
	cout<<num[i]<<endl; 
	Node<int> *t2;
	test.creatBtree_Qian(t2,-1);
	if(test.equal(t,t2))
	cout<<"equal"<<endl;
	else
	cout<<"not equal"<<endl;
}

参考博文：

求二叉树的节点个数、深度、四种遍历方法

二叉树计数

N个结点二叉树有种

这个函数称为catalan函数

n个节点的二叉树有多少种形态

根据遍历顺序画出一棵二叉树

根据遍历序列确定二叉树

根据二叉树的先序和中序序列画出二叉树的方法

值得注意的是根据遍历顺序确定一棵二叉树必须要有一个中序在里面

总结与思考

通过创建树引发的对指针引用变量的思考：http://lyxf.live/posts/2541aeec/

  • 1.关于求深度、节点数，我们使用递归思想，将问题化为一个小树枝，在设置恰当返回条件的前提下，不断向上返回，左右树不断扩大最终返回到树根

待补充

二叉树非递归遍历

线索二叉树

参考文章:

深入学习二叉树(二) 线索二叉树

线索二叉树

二叉树的线索化及其遍历（必会）

1、二叉树中没有利用的指针

n个节点二叉树有n+1个没有利用的指针

在N个节点的二叉树中，每个节点有2个指针，所以一共有2N个指针，除了根节点以外，每一个节点都有一个指针从它的父节点指向它，所以一共使用了N-1个指针，所以剩下2N-(N-1)也就是N+1个空指针；

2、利用空指针指向前驱后驱

原因:如果利用空指针直接记录前驱后驱结点，在遍历的时候会比递归速度要快还能减少建立递归程序的存储空间。

若结点的左子树为空，则该结点的左孩子指针指向其前驱结点。

若结点的右子树为空，则该结点的右孩子指针指向其后继结点。

3、解决判断左右指针是为指向前后驱还是左右孩子

添加标志位ltag，rtag，并定义规则如下：

ltag为0时，指向左孩子，为1时指向前驱
rtag为0时，指向右孩子，为1时指向后继

5、实现方法

1、首先建立起二叉树

2、按某种次序遍历二叉树，在遍历过程中用线索取代空指针即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//中序遍历进行中序线索化
void inThreading(ThrBiTree T, ThrBiTree &pre){  
    if(T){  
        inThreading(T->lchild, pre);//左子树线索化  
  
        if(!T->lchild){//当前结点的左孩子为空  
            T->lTag = Thread;  
            T->lchild = pre;  
        }else{  
            T->lTag = Link;  
        }  
  
        if(!pre->rchild){//前驱结点的右孩子为空  
            pre->rTag = Thread;  
            pre->rchild = T;  
        }else{  
            pre->rTag = Link;  
        }  
        pre = T;          
        inThreading(T->rchild, pre);//右子树线索化  
    }  
}

把二叉树看成中序遍历序列，序列的第一个结点（最左下结点）的前驱为NULL，最后一个结点（最右下结点）的后继为NULL。通过设置pre的初始化为NULL和最后对pre（指向最后一个结点）的后继（右子树）设置为NULL来实现。

值得注意，我们在一次处理中是处理当前左结点和前驱的右节点，按照这样的顺序递归执行下去的，而不是对当前的左右结点处理

6、遍历

详见参考文章

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享，您的支持将鼓励我继续创作！恰饭^.^~