算法系列15天速成—— 树操作
最近项目赶的紧，歇了一个星期没写博客了，趁周末继续写这个系列。
先前我们讲的都是“线性结构”，他的特征就是“一个节点最多有一个”前驱“和一个”后继“。那么我们今天讲的树会是怎样的呢？
我们可以对”线性结构“改造一下，变为”一个节点最多有一个"前驱“和”多个后继“。哈哈，这就是我们今天说的”树“。
一： 树
我们思维中的”树“就是一种枝繁叶茂的形象，那么数据结构中的”树“该是怎么样呢？对的，他是一种现实中倒立的树。
1：术语
其实树中有很多术语的，这个是我们学习树形结构必须掌握的。
父节点，子节点，兄弟节点
这个就比较简单了，B和C的父节点就是A，反过来说就是B和C是A的子节点。B和C就是兄弟节点。
结点的度
其实”度“就是”分支数“，比如A的分支数有两个“B和C",那么A的度为2。
树的度
看似比较莫名其妙吧，他和”结点的度“的区别就是，树的度讲究大局观，乃树中最大的结点度，其实也就是2。
叶结点，分支结点
叶结点就是既没有左孩子也没有右孩子结点，也就是结点度为0。分支节点也就是if的else的条件咯。
结点的层数
这个很简单，也就是树有几层。
有序树，无序树
有序树我们先前也用过，比如“堆”和“二叉排序树”，说明这种树是按照一定的规则进行排序的，else条件就是无序树。
森林
现实中，很多的树形成了森林，那在数据结构中，我们把上图的“A”节点砍掉，那么B，C子树合一起就是森林咯。
2: 树的表示
树这个结构的表示其实有很多种，常用的也就是“括号”表示法。
比如上面的树就可以表示为：(A(B(D),(E)),(C(F),(G)))
二： 二叉树
在我们项目开发中，很多地方都会用到树，但是多叉树的处理还是比较纠结的，所以俺们本着“大事化小，小事化了“的原则
把”多叉树“转化为”二叉树“，那么问题就简化了很多。
1： ”二叉树“和”树“有什么差异呢？
第一点: 树的度没有限制，而“二叉树”最多只能有两个，不然也就不叫二叉树了，哈哈。
第二点：树中的子树没有左右划分，很简单啊，找不到参照点，二叉树就有参照物咯。
2： 二叉树的类型
二叉树中有两种比较完美的类型，“完全二叉树”和“满二叉树”。
满二叉树
除叶子节点外，所有节点的度都为2，文章开头处的树就是这里的“满二叉树”。
完全二叉树
必须要满足两个条件就即可： 干掉最后一层，二叉树变为“满二叉树”。
最后一层的叶节点必须是“从左到右”依次排开。
我们干掉文章开头处的节点“F和”G",此时还是“完全二叉树”，但已经不是“满二叉树”了，你懂的。
3： 二叉树的性质
二叉树中有5点性质非常重要，也是俺们必须要记住的。
二叉树中，第i层的节点最多有2(i-1)个。
深度为k的二叉树最多有2k-1个节点。
二叉树中，叶子节点树为N1个，度为2的节点有N2个，那么N1=N2+1。
具有N个结点的二叉树深度为（Log2 N）+1层。
N个结点的完全二叉树如何用顺序存储，对于其中的一个结点i，存在以下关系，
2*i是结点i的父结点。
i/2是结点i的左孩子。
(i/2)+1是结点i的右孩子。
4： 二叉树的顺序存储
同样的存储方式也有两种，“顺序存储”和“链式存储”。
顺序存储
说实话，树的存储用顺序结构比较少，因为从性质定理中我们都可以看出只限定为“完全二叉树”，那么如果二叉树不是
“完全二叉树”，那我们就麻烦了，必须将其转化为“完全二叉树”，将空的节点可以用“#”代替，图中也可看出，为了维护
性质定理5的要求，我们牺牲了两个”资源“的空间。
链式存储
上面也说了，顺序存储会造成资源的浪费，所以嘛，我们开发中用的比较多的还是“链式存储”，同样“链式存储”
也非常的形象，非常的合理。
一个结点存放着一个“左指针”和一个“右指针”，这就是二叉链表。
如何方便的查找到该结点的父结点，可以采用三叉链表。
5: 常用操作
一般也就是“添加结点“，“查找节点”，“计算深度”，“遍历结点”，“清空结点”
这里我们就用二叉链表来定义链式存储模型
1 #region 二叉链表存储结构 2 ///3 /// 二叉链表存储结构 4 /// 5 ///6 public class ChainTree 7 { 8 public T data; 9 10 public ChainTree left; 11 12 public ChainTree right; 13 } 14 #endregion
添加结点
要添加结点，我们就要找到添加结点的父结点，并且根据指示插入到父结点中指定左结点或者右结点。
1 #region 将指定节点插入到二叉树中 2 ///3 /// 将指定节点插入到二叉树中 4 /// 5 ///6 /// 7 /// 8 /// 插入做左是右 9 /// 10 public ChainTree BinTreeAddNode (ChainTree tree, ChainTree node, T data, Direction direction) 11 { 12 if (tree == null) 13 return null; 14 15 if (tree.data.Equals(data)) 16 { 17 switch (direction) 18 { 19 case Direction.Left: 20 if (tree.left != null) 21 throw new Exception("树的左节点不为空，不能插入"); 22 else 23 tree.left = node; 24 25 break; 26 case Direction.Right: 27 if (tree.right != null) 28 throw new Exception("树的右节点不为空，不能插入"); 29 else 30 tree.right = node; 31 32 break; 33 } 34 } 35 36 BinTreeAddNode(tree.left, node, data, direction); 37 BinTreeAddNode(tree.right, node, data, direction); 38 39 return tree; 40 } 41 #endregion
查找节点
二叉树中到处都散发着递归思想，很能锻炼一下我们对递归的认识，同样查找也是用到了递归思想。
1 #region 在二叉树中查找指定的key 2 ///3 ///在二叉树中查找指定的key 4 /// 5 ///6 /// 7 /// 8 /// 9 public ChainTree BinTreeFind (ChainTree tree, T data) 10 { 11 if (tree == null) 12 return null; 13 14 if (tree.data.Equals(data)) 15 return tree; 16 17 return BinTreeFind(tree, data); 18 } 19 #endregion
计算深度
这个问题纠结了我二个多小时，原因在于没有深刻的体会到递归，其实主要思想就是递归左子树和右子树，然后得出较大的一个。
1 #region 获取二叉树的深度 2 ///3 /// 获取二叉树的深度 4 /// 5 ///6 /// 7 /// 8 public int BinTreeLen (ChainTree tree) 9 { 10 int leftLength; 11 int rightLength; 12 13 if (tree == null) 14 return 0; 15 16 //递归左子树的深度 17 leftLength = BinTreeLen(tree.left); 18 19 //递归右子书的深度 20 rightLength = BinTreeLen(tree.right); 21 22 if (leftLength > rightLength) 23 return leftLength + 1; 24 else 25 return rightLength + 1; 26 } 27 #endregion
遍历结点
二叉树中遍历节点的方法还是比较多的，有“先序”，“中序”，“后序”，“按层”，其实这些东西只可意会，不可言传，真的很难在口头
上说清楚，需要反复的体会递归思想。
先序：先访问根，然后递归访问左子树，最后递归右子树。（DLR模式）
中序：先递归访问左子树，在访问根，最后递归右子树。（LDR模式）
后序：先递归访问左子树，然后递归访问右子树，最后访问根。（LRD模式）
按层：这个比较简单，从上到下，从左到右的遍历节点。
1 #region 二叉树的先序遍历 2 ///3 /// 二叉树的先序遍历 4 /// 5 ///6 /// 7 public void BinTree_DLR (ChainTree tree) 8 { 9 if (tree == null) 10 return; 11 12 //先输出根元素 13 Console.Write(tree.data + "t"); 14 15 //然后遍历左子树 16 BinTree_DLR(tree.left); 17 18 //最后遍历右子树 19 BinTree_DLR(tree.right); 20 } 21 #endregion 22 23 #region 二叉树的中序遍历 24 /// 25 /// 二叉树的中序遍历 26 /// 27 ///28 /// 29 public void BinTree_LDR (ChainTree tree) 30 { 31 if (tree == null) 32 return; 33 34 //优先遍历左子树 35 BinTree_LDR(tree.left); 36 37 //然后输出节点 38 Console.Write(tree.data + "t"); 39 40 //最后遍历右子树 41 BinTree_LDR(tree.right); 42 } 43 #endregion 44 45 #region 二叉树的后序遍历 46 /// 47 /// 二叉树的后序遍历 48 /// 49 ///50 /// 51 public void BinTree_LRD (ChainTree tree) 52 { 53 if (tree == null) 54 return; 55 56 //优先遍历左子树 57 BinTree_LRD(tree.left); 58 59 //然后遍历右子树 60 BinTree_LRD(tree.right); 61 62 //最后输出节点元素 63 Console.Write(tree.data + "t"); 64 } 65 #endregion 66 67 #region 二叉树的按层遍历 68 /// 69 /// 二叉树的按层遍历 70 /// 71 ///72 /// 73 public void BinTree_Level (ChainTree tree) 74 { 75 if (tree == null) 76 return; 77 78 //申请保存空间 79 ChainTree [] treeList = new ChainTree [Length]; 80 81 int head = 0; 82 int tail = 0; 83 84 //存放数组 85 treeList[tail] = tree; 86 87 //循环链中计算tail位置 88 tail = (tail + 1) % Length; 89 90 while (head != tail) 91 { 92 var tempNode = treeList[head]; 93 94 head = (head + 1) % Length; 95 96 //输出节点 97 Console.Write(tempNode.data + "t"); 98 99 //如果左子树不为空,则将左子树存于数组的tail位置 100 if (tempNode.left != null) 101 { 102 treeList[tail] = tempNode.left; 103 104 tail = (tail + 1) % Length; 105 } 106 107 //如果右子树不为空，则将右子树存于数组的tail位置 108 if (tempNode.right != null) 109 { 110 treeList[tail] = tempNode.right; 111 112 tail = (tail + 1) % Length; 113 } 114 } 115 } 116 #endregion
清空二叉树
虽然C#里面有GC，但是我们能自己释放的就不麻烦GC了，同样清空二叉树节点，我们用到了递归，说实话，这次练习让我喜欢
上的递归，虽然XXX的情况下，递归的不是很好，但是递归还是很强大的。
1 #region 清空二叉树 2 ///3 /// 清空二叉树 4 /// 5 ///6 /// 7 public void BinTreeClear (ChainTree tree) 8 { 9 //递的结束点，归的起始点 10 if (tree == null) 11 return; 12 13 BinTreeClear(tree.left); 14 BinTreeClear(tree.right); 15 16 //在归的过程中，释放当前节点的数据空间 17 tree = null; 18 } 19 #endregion
最后上一下总的代码
View Code
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5
6 namespace ChainTree
7 {
8 public class Program
9 {
10 static void Main(string[] args)
11 {
12 ChainTreeManager manager = new ChainTreeManager();
13
14 //插入节点操作
15 ChainTree tree = CreateRoot();
16
17 //插入节点数据
18 AddNode(tree);
19
20 //先序遍历
21 Console.WriteLine("n先序结果为： n");
22 manager.BinTree_DLR(tree);
23
24 //中序遍历
25 Console.WriteLine("n中序结果为： n");
26 manager.BinTree_LDR(tree);
27
28 //后序遍历
29 Console.WriteLine("n后序结果为： n");
30 manager.BinTree_LRD(tree);
31
32 //层次遍历
33 Console.WriteLine("n层次结果为： n");
34 manager.Length = 100;
35 manager.BinTree_Level(tree);
36
37 Console.WriteLine("n树的深度为：" + manager.BinTreeLen(tree) + "n");
38
39 Console.ReadLine();
40
41 }
42
43 #region 生成根节点
44 ///
45 /// 生成根节点
46 ///
47 /// CreateRoot()
49 {
50 ChainTree tree = new ChainTree();
51
52 Console.WriteLine("请输入根节点，方便我们生成树n");
53
54 tree.data = Console.ReadLine();
55
56 Console.WriteLine("根节点生成已经生成n");
57
58 return tree;
59 }
60 #endregion
61
62 #region 插入节点操作
63 ///
64 /// 插入节点操作
65 ///
66 ///
67 static ChainTree AddNode(ChainTree tree)
68 {
69 ChainTreeManager mananger = new ChainTreeManager();
70
71 while (true)
72 {
73 ChainTree node = new ChainTree();
74
75 Console.WriteLine("请输入要插入节点的数据：n");
76
77 node.data = Console.ReadLine();
78
79 Console.WriteLine("请输入要查找的父节点数据：n");
80
81 var parentData = Console.ReadLine();
82
83 if (tree == null)
84 {
85 Console.WriteLine("未找到您输入的父节点，请重新输入。");
86 continue;
87 }
88
89 Console.WriteLine("请确定要插入到父节点的：1 左侧，2 右侧");
90
91 Direction direction = (Direction)Enum.Parse(typeof(Direction), Console.ReadLine());
92
93 tree = mananger.BinTreeAddNode(tree, node, parentData, direction);
94
95 Console.WriteLine("插入成功，是否继续？ 1 继续， 2 退出");
96
97 if (int.Parse(Console.ReadLine()) == 1)
98 continue;
99 else
100 break;
101 }
102
103 return tree;
104 }
105 #endregion
106 }
107
108 #region 插入左节点或者右节点
109 ///
110 /// 插入左节点或者右节点
111 ///
112 public enum Direction { Left = 1, Right = 2 }
113 #endregion
114
115 #region 二叉链表存储结构
116 ///
117 /// 二叉链表存储结构
118 ///
119 ///
121 {
122 public T data;
123
124 public ChainTree left;
125
126 public ChainTree right;
127 }
128 #endregion
129
130 ///
131 /// 二叉树的操作帮助类
132 ///
133 public class ChainTreeManager
134 {
135 #region 按层遍历的Length空间存储
136 ///
137 /// 按层遍历的Length空间存储
138 ///
139 public int Length { get; set; }
140 #endregion
141
142 #region 将指定节点插入到二叉树中
143 ///
144 /// 将指定节点插入到二叉树中
145 ///
146 /// BinTreeAddNode(ChainTree tree, ChainTree node, T data, Direction direction)
152 {
153 if (tree == null)
154 return null;
155
156 if (tree.data.Equals(data))
157 {
158 switch (direction)
159 {
160 case Direction.Left:
161 if (tree.left != null)
162 throw new Exception("树的左节点不为空，不能插入");
163 else
164 tree.left = node;
165
166 break;
167 case Direction.Right:
168 if (tree.right != null)
169 throw new Exception("树的右节点不为空，不能插入");
170 else
171 tree.right = node;
172
173 break;
174 }
175 }
176
177 BinTreeAddNode(tree.left, node, data, direction);
178 BinTreeAddNode(tree.right, node, data, direction);
179
180 return tree;
181 }
182 #endregion
183
184 #region 获取二叉树指定孩子的状态
185 ///
186 /// 获取二叉树指定孩子的状态
187 ///
188 /// BinTreeChild(ChainTree tree, Direction direction)
193 {
194 ChainTree childNode = null;
195
196 if (tree == null)
197 throw new Exception("二叉树为空");
198
199 switch (direction)
200 {
201 case Direction.Left:
202 childNode = tree.left;
203 break;
204 case Direction.Right:
205 childNode = tree.right;
206 break;
207 }
208
209 return childNode;
210 }
211
212 #endregion
213
214 #region 获取二叉树的深度
215 ///
216 /// 获取二叉树的深度
217 ///
218 /// (ChainTree tree)
222 {
223 int leftLength;
224 int rightLength;
225
226 if (tree == null)
227 return 0;
228
229 //递归左子树的深度
230 leftLength = BinTreeLen(tree.left);
231
232 //递归右子书的深度
233 rightLength = BinTreeLen(tree.right);
234
235 if (leftLength > rightLength)
236 return leftLength + 1;
237 else
238 return rightLength + 1;
239 }
240 #endregion
241
242 #region 判断二叉树是否为空
243 ///
244 /// 判断二叉树是否为空
245 ///
246 /// (ChainTree tree)
250 {
251 return tree == null ? true : false;
252 }
253 #endregion
254
255 #region 在二叉树中查找指定的key
256 ///
257 ///在二叉树中查找指定的key
258 ///
259 /// BinTreeFind(ChainTree tree, T data)
264 {
265 if (tree == null)
266 return null;
267
268 if (tree.data.Equals(data))
269 return tree;
270
271 return BinTreeFind(tree, data);
272 }
273 #endregion
274
275 #region 清空二叉树
276 ///
277 /// 清空二叉树
278 ///
279 /// (ChainTree tree)
282 {
283 //递的结束点，归的起始点
284 if (tree == null)
285 return;
286
287 BinTreeClear(tree.left);
288 BinTreeClear(tree.right);
289
290 //在归的过程中，释放当前节点的数据空间
291 tree = null;
292 }
293 #endregion
294
295 #region 二叉树的先序遍历
296 ///
297 /// 二叉树的先序遍历
298 ///
299 /// (ChainTree tree)
302 {
303 if (tree == null)
304 return;
305
306 //先输出根元素
307 Console.Write(tree.data + "t");
308
309 //然后遍历左子树
310 BinTree_DLR(tree.left);
311
312 //最后遍历右子树
313 BinTree_DLR(tree.right);
314 }
315 #endregion
316
317 #region 二叉树的中序遍历
318 ///
319 /// 二叉树的中序遍历
320 ///
321 /// (ChainTree tree)
324 {
325 if (tree == null)
326 return;
327
328 //优先遍历左子树
329 BinTree_LDR(tree.left);
330
331 //然后输出节点
332 Console.Write(tree.data + "t");
333
334 //最后遍历右子树
335 BinTree_LDR(tree.right);
336 }
337 #endregion
338
339 #region 二叉树的后序遍历
340 ///
341 /// 二叉树的后序遍历
342 ///
343 /// (ChainTree tree)
346 {
347 if (tree == null)
348 return;
349
350 //优先遍历左子树
351 BinTree_LRD(tree.left);
352
353 //然后遍历右子树
354 BinTree_LRD(tree.right);
355
356 //最后输出节点元素
357 Console.Write(tree.data + "t");
358 }
359 #endregion
360
361 #region 二叉树的按层遍历
362 ///
363 /// 二叉树的按层遍历
364 ///
365 /// (ChainTree tree)
368 {
369 if (tree == null)
370 return;
371
372 //申请保存空间
373 ChainTree[] treeList = new ChainTree[Length];
374
375 int head = 0;
376 int tail = 0;
377
378 //存放数组
379 treeList[tail] = tree;
380
381 //循环链中计算tail位置
382 tail = (tail + 1) % Length;
383
384 while (head != tail)
385 {
386 var tempNode = treeList[head];
387
388 head = (head + 1) % Length;
389
390 //输出节点
391 Console.Write(tempNode.data + "t");
392
393 //如果左子树不为空,则将左子树存于数组的tail位置
394 if (tempNode.left != null)
395 {
396 treeList[tail] = tempNode.left;
397
398 tail = (tail + 1) % Length;
399 }
400
401 //如果右子树不为空，则将右子树存于数组的tail位置
402 if (tempNode.right != null)
403 {
404 treeList[tail] = tempNode.right;
405
406 tail = (tail + 1) % Length;
407 }
408 }
409 }
410 #endregion
411
412 }
413 }
我们把文章开头的“二叉树”的节点输入到我们的结构中，看看遍历效果咋样。
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/1451/viewspace-2806226/ ，如需转载，请注明出处，否则将追究法律责任。
