数据结构之二叉树_再熬叉树中结点的不足树在节点而直接两个数值结点个数如果异常高尚属于有个节

树

树的简介：

• 树状图是一种数据结构，它是由 n（n>=1）个有限结点组成一个具有层次关系的集合。

• 把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

• 每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；

二叉树的原理精讲

• 我们以前介绍的线性表一样，一个没有限制的线性表应用范围可能有限，但是我们对线性表进行一些限制就可以衍生出非常有用的数据结构如栈、队列、优先队列等。

• 树也是一样，一个没有限制的树由于太灵活，控制起来比较复杂。如果对普通的树加上一些人为的限制，比如节点只允许有两个子节点，这就是我们接下来要介绍的二叉树。

• 二叉树是一个每个结点最多只能有两个分支的树，左边的分支称之为左子树，右边的分支称之为右子树。

(1)	在非空二叉树中，第 i-1 层的结点总数不超过   , i>=1；
    
(2)	深度为 h-1 的二叉树最多有 	个结点(h>=1)，最少有 h 个结点；
    
(3)	对于任意一棵二叉树，如果其叶结点数为 N0，而度数为 2 的结点总数为 N2，则 N0=N2+1；
1
2
3
4
5

常见二叉树分类：

（1）完全二叉树 — 若设二叉树的高度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶子节点，并且叶子结点都是从左到右依次排布，这就是完全二叉树（堆就是完全二叉树）。

（2）满二叉树 —除了叶结点外每一个结点都有左右子节点且叶子结点都处在最底层的二叉树。

（3）平衡二叉树 —又被称为 AVL 树，它是一颗空树或左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

（4）二叉搜索树 —又称二叉查找树、二叉排序树（Binary Sort Tree）。它是一颗空树或是满足下列性质的二叉树：

• 若左子树不空，则左子树上所有节点的值均小于或等于它的根节点的值；

• 若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；

• 左、右子树也分别为二叉排序树。

（5）红黑树 — 是每个节点都带有颜色属性（颜色为红色或黑色）的自平衡二叉查找树，满足下列性质：

• 节点是红色或黑色；

• 根节点是黑色；

• 所有叶子节点都是黑色；

• 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)

• 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

二叉搜索树的算法实现

1. 当我们要在一组数中要找到你女朋友（或未来女朋友）的年龄，比如 26？你该怎么找？

答案：

1. 从左至右 或 从右至左遍历一次，找到这个数字

2. 当我们把数据进行排序（按照从小到大的顺序排列）后，再查找相应的这条记录？还是用上面的方法吗？

答案：最快的方式，是采用折半法（俗称二分查找**）

• **思考：**若用顺序表当有数据删除和插入的时候，会造成大量数据移动，即不合适。

• 抛砖: 链表在插入和删除的时候，不需要移动元素，但是当查找一个元素的时候，会便利一个链表

• 引玉： 二叉树的话，把比根节点小的元素放在左子树中，比根大的放在右子树中。那么在查找 x 时，若 x 比根节点小可以排除右子树所有元素，去左子树中查找（类似二分查找）。故二叉搜索树用作一些查找和插入使用频率比较高的场景。

• 二叉树一般采用链式存储方式：每个结点包含两个指针域，指向两个孩子结点，还包含一个数据域，存储结点信息。

节点结构体的定义:

//为了区分节点和头节点，给结构体起别名
typedef struct Code
{
	int data;
	Code * lchild;
	Code * rchild;
}TreeCode;
1
2
3
4
5
6
7

二叉搜索树插入节点

• 将要插入的结点 e，与节点 root 节点进行比较，若小于则去到左子树进行比较，若大于则去到右子树进行比较，重复以上

操作直到找到一个空位置用于放置该新节点。

//插入树
//因为这里需要改变实参的值且实参是一级指针，所以参数用二级指针。
bool insertTree(TreeCode **root, Code * code)
{
	if (code == NULL)
	{
		return NULL;
	}
	//插入节点插入后一定成为叶子节点,所以置空
	code->lchild = NULL;
	code->rchild = NULL;

	//*root == NULL成立，则表明树上一个节点也没有
	if (*root == NULL)
	{
		*root = code;
		return true;
	}

	//寻找父节点
	Code * temp = *root;
	Code * persent = NULL;
	while (temp != NULL)
	{
		persent = temp;
		if (temp->data > code->data)
		{
			temp = temp->lchild;
			continue;
		}
		if (temp->data < code->data)
		{
			temp = temp->rchild;
			continue;
		}
		else
		{
			break;
		}
	}

	//插入父节点的左节点或者右节点
	if (persent->data > code->data)
	{
		persent->lchild = code;
	}
	else
	{
		persent->rchild = code;
	}
}
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

二叉搜索树删除节点

• 将要删除的节点的值，与节点 root 节点进行比较，若小于则去到左子树进行比较，若大于则去到右子树进行比较，重复以上操作直到找到一个节点的值等于删除的值，则将此节点删除。删除时有 4 中情况须分别处理：

1. 删除节点不存在左右子节点，即为叶子节点，直接删除

2. 删除节点存在左子节点，不存在右子节点，直接把左子节点替代删除节点

3. 删除节点存在右子节点，不存在左子节点，直接把右子节点替代删除节点

4. 删除节点存在左右子节点，则取左子树上的最大节点或右子树上的最小节点替换删除节点。

代码实现四种情况：

//获取左节点最大值
int getMaxValue(TreeCode * root)
{
	Code * code = NULL;
	Code * temp = root;

	//循环找到最右的节点
	while (temp != NULL)
	{
		code = temp;
		temp = temp->rchild;
	}
	return code->data;
}

//根据值删除指定元素
TreeCode * deleteCode(TreeCode * root, int data, Code * deletecode)
{
	//传入参数无效和没找到元素都以这个为出口
	if (root == NULL)
	{
		return NULL;
	}

	//两个if递归寻找需要删除的节点
	if (root->data > data)
	{
		//root->lchild：接收已经处理好(目标节点已经找到且已经移出树)的左节点
		root->lchild = deleteCode(root->lchild, data, deletecode);
		return root;
	}
	if (root->data < data)
	{
		root->rchild = deleteCode(root->rchild, data, deletecode);
		return root;
	}

	//当执行到这里的时候,意味着root.data==code.data ,即找到目标元素,接下来就进行返回值操作
	deletecode = root;

	//如果所要删除的节点没有左右节点,那就直接删除,把指向目标元素的指针置空
	if (root->lchild == NULL && root->rchild == NULL)return NULL;

	//如果只有左节点,没有右节点,把指向目标元素的指针指向左节点
	if (root->lchild != NULL && root->rchild == NULL)return root->lchild;

	//如果只有右节点,没有左节点,把指向目标元素的指针指向右节点
	if (root->lchild == NULL && root->rchild != NULL)return root->rchild;

	//如果存在左右节点,则用左节点的最大值赋值给目标节点,且删除最大值节点
	if (root->lchild != NULL && root->rchild != NULL)
	{
		int maxValue = getMaxValue(root->lchild);
		root = deleteCode(root, maxValue, deletecode);
		root->data = maxValue;
		return root;
	}
}

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

二叉搜索树搜索

//用值查找节点
Code * findCode(TreeCode * root, int val)
{
	if (root == NULL)
	{
		cout << "参数无效" << endl;
		return NULL;
	}

	while (root != NULL)
	{
		if (root->data > val)
		{
			root = root->lchild;
			continue;
		}
		else if (root->data < val)
		{
			root = root->rchild;
			continue;
		}
		else
		{
			break;
		}
	}
	if (root == NULL)
	{
		cout << "没找到元素：" << val << endl;
		return NULL;
	}
	return root;
}
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

二叉树的遍历

二叉树的遍历是指从根结点出发，按照某种次序依次访问所有结点，使得每个结点被当且访问一次。共分为四种方式：

• 前序遍历 - 先访问根节点，然后前序遍历左子树，再前序遍历右子树

• 中序遍历 - 先访问根节点的左子树，然后访问根节点，最后遍历右子树

• 后序遍历 - 从左到右，先叶子后节点的方式遍历访问左右子树，最后访问根节点

• 层序遍历 - 从根节点从上往下逐层遍历，在同一层，按从左到右的顺序对节点逐个访问

代码实现前三种遍历：

//前序遍历
void praTree(TreeCode * root)
{
	if (root == NULL)
	{
		return;
	}
	cout << root->data << "  ";
	praTree(root->lchild);
	praTree(root->rchild);
}

//中序遍历
void medTree(TreeCode * root)
{
	if (root == NULL)
	{
		return;
	}

	medTree(root->lchild);
	cout << root->data << "  ";
	medTree(root->rchild);
}

//后序遍历
void subTree(TreeCode * root)
{
	if (root == NULL)
	{
		return;
	}

	subTree(root->lchild);
	subTree(root->rchild);
	cout << root->data << "  ";
}

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

完整源码实现：

#include<iostream>
using namespace std;

//为了区分节点和头节点，给结构体起别名
typedef struct Code
{
	int data;
	Code * lchild;
	Code * rchild;
}TreeCode;

//插入树
//因为这里需要改变实参的值且实参是一级指针，所以参数用二级指针。
bool insertTree(TreeCode **root, Code * code)
{
	if (code == NULL)
	{
		return NULL;
	}
	//插入节点插入后一定成为叶子节点,所以置空
	code->lchild = NULL;
	code->rchild = NULL;

	//*root == NULL成立，则表明树上一个节点也没有
	if (*root == NULL)
	{
		*root = code;
		return true;
	}

	//寻找父节点
	Code * temp = *root;
	Code * persent = NULL;
	while (temp != NULL)
	{
		persent = temp;
		if (temp->data > code->data)
		{
			temp = temp->lchild;
			continue;
		}
		if (temp->data < code->data)
		{
			temp = temp->rchild;
			continue;
		}
		else
		{
			break;
		}
	}

	//插入父节点的左节点或者右节点
	if (persent->data > code->data)
	{
		persent->lchild = code;
	}
	else
	{
		persent->rchild = code;
	}
}

//获取左节点最大值
int getMaxValue(TreeCode * root)
{
	Code * code = NULL;
	Code * temp = root;

	//循环找到最右的节点
	while (temp != NULL)
	{
		code = temp;
		temp = temp->rchild;
	}
	return code->data;
}

//根据值删除指定元素
TreeCode * deleteCode(TreeCode * root, int data, Code * deletecode)
{
	//传入参数无效和没找到元素都以这个为出口
	if (root == NULL)
	{
		return NULL;
	}

	//两个if递归寻找需要删除的节点
	if (root->data > data)
	{
		//root->lchild：接收已经处理好(目标节点已经找到且已经移出树)的左节点
		root->lchild = deleteCode(root->lchild, data, deletecode);
		return root;
	}
	if (root->data < data)
	{
		root->rchild = deleteCode(root->rchild, data, deletecode);
		return root;
	}

	//当执行到这里的时候,意味着root.data==code.data ,即找到目标元素,接下来就进行返回值操作
	deletecode = root;

    //下方的返回值都是用来代替要删除的节点的,从而得到覆盖的目的
	//如果所要删除的节点没有左右节点,那就直接删除,把指向目标元素的指针置空
	if (root->lchild == NULL && root->rchild == NULL)return NULL;

	//如果只有左节点,没有右节点,把指向目标元素的指针指向左节点
	if (root->lchild != NULL && root->rchild == NULL)return root->lchild;

	//如果只有右节点,没有左节点,把指向目标元素的指针指向右节点
	if (root->lchild == NULL && root->rchild != NULL)return root->rchild;

	//如果存在左右节点,则用左节点的最大值赋值给目标节点,且删除最大值节点
	if (root->lchild != NULL && root->rchild != NULL)
	{
		int maxValue = getMaxValue(root->lchild);
		root = deleteCode(root, maxValue, deletecode);
		root->data = maxValue;
		return root;
	}
}

//用值查找节点
Code * findCode(TreeCode * root, int val)
{
	if (root == NULL)
	{
		cout << "参数无效" << endl;
		return NULL;
	}

	while (root != NULL)
	{
		if (root->data > val)
		{
			root = root->lchild;
			continue;
		}
		else if (root->data < val)
		{
			root = root->rchild;
			continue;
		}
		else
		{
			break;
		}
	}
	if (root == NULL)
	{
		cout << "没找到元素：" << val << endl;
		return NULL;
	}
	return root;
}

//前序遍历
void praTree(TreeCode * root)
{
	if (root == NULL)
	{
		return;
	}
	cout << root->data << "  ";
	praTree(root->lchild);
	praTree(root->rchild);
}

//中序遍历
void medTree(TreeCode * root)
{
	if (root == NULL)
	{
		return;
	}

	medTree(root->lchild);
	cout << root->data << "  ";
	medTree(root->rchild);
}

//后序遍历
void subTree(TreeCode * root)
{
	if (root == NULL)
	{
		return;
	}

	subTree(root->lchild);
	subTree(root->rchild);
	cout << root->data << "  ";
}

int main()
{
	int text[] = { 19,7,25,5,11,15,21,61 };
	
	//插入根节点
	TreeCode * rootTree = NULL;
	Code * code = new Code;
	code->data = text[0];
	insertTree(&rootTree, code);

	//插入所有节点
	for (int i = 0; i < 7; i++)
	{
		code = new Code;
		code->data = text[i + 1];
		insertTree(&rootTree, code);
	}


	Code * deletecode = NULL;
	//删除叶子节点
	deleteCode(rootTree, 61, deletecode);
	delete deletecode;
	deletecode = NULL;

	//删除有右儿子的节点
	deleteCode(rootTree, 21, deletecode);
	delete deletecode;
	deletecode = NULL;

	//删除根节点
	deleteCode(rootTree, 19, deletecode);
	delete deletecode;
	deletecode = NULL;

	//查找元素11
	code = findCode(rootTree, 11);
	cout << code->data << endl;


	//前序遍历节点
	cout << "---------前序遍历--------" << endl;
	praTree(rootTree);
	cout << endl << endl;

	cout << "---------中序遍历--------" << endl;
	medTree(rootTree);
	cout << endl << endl;

	cout << "---------后序遍历------" << endl;
	subTree(rootTree);
	cout << endl << endl;


	system("pause");
	return 0;
}
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
252