算法系列15天速成 第十一天 树操作（上）

先前我们讲的都是“线性结构”，他的特征就是“一个节点最多有一个”前驱“和一个”后继“。那么我们今天讲的树会是怎样的呢？

我们可以对”线性结构“改造一下，变为”一个节点最多有一个"前驱“和”多个后继“。哈哈，这就是我们今天说的”树“。

一： 树

      我们思维中的”树“就是一种枝繁叶茂的形象，那么数据结构中的”树“该是怎么样呢？对的，他是一种现实中倒立的树。

1：术语

     其实树中有很多术语的，这个是我们学习树形结构必须掌握的。

     <1>  父节点，子节点，兄弟节点

                  这个就比较简单了，b和c的父节点就是a，反过来说就是b和c是a的子节点。b和c就是兄弟节点。

     <2>  结点的度

                 其实”度“就是”分支数“，比如a的分支数有两个“b和c",那么a的度为2。

     <3> 树的度

                看似比较莫名其妙吧，他和”结点的度“的区别就是，树的度讲究大局观，乃树中最大的结点度，其实也就是2。

     <4> 叶结点，分支结点

                叶结点就是既没有左孩子也没有右孩子结点，也就是结点度为0。分支节点也就是if的else的条件咯。

    <5> 结点的层数

               这个很简单，也就是树有几层。

   <6> 有序树，无序树

               有序树我们先前也用过，比如“堆”和“二叉排序树”，说明这种树是按照一定的规则进行排序的，else条件就是无序树。

   <7>  森林

               现实中，很多的树形成了森林，那在数据结构中，我们把上图的“a”节点砍掉，那么b，c子树合一起就是森林咯。

2: 树的表示

     树这个结构的表示其实有很多种，常用的也就是“括号”表示法。
     比如上面的树就可以表示为：(a(b(d),(e)),(c(f),(g)))

二： 二叉树

         在我们项目开发中，很多地方都会用到树，但是多叉树的处理还是比较纠结的，所以俺们本着“大事化小，小事化了“的原则

      把”多叉树“转化为”二叉树“，那么问题就简化了很多。

1： ”二叉树“和”树“有什么差异呢？

         第一点:  树的度没有限制，而“二叉树”最多只能有两个，不然也就不叫二叉树了，哈哈。
         第二点：树中的子树没有左右划分，很简单啊，找不到参照点，二叉树就有参照物咯。

2： 二叉树的类型

       二叉树中有两种比较完美的类型，“完全二叉树”和“满二叉树”。

          <1>  满二叉树    

                       除叶子节点外，所有节点的度都为2，文章开头处的树就是这里的“满二叉树”。

          <2>  完全二叉树

                      必须要满足两个条件就即可：  干掉最后一层，二叉树变为“满二叉树”。

   最后一层的叶节点必须是“从左到右”依次排开。

   我们干掉文章开头处的节点“f和”g",此时还是“完全二叉树”，但已经不是“满二叉树”了，你懂的。

3： 二叉树的性质

         二叉树中有5点性质非常重要，也是俺们必须要记住的。

     <1>  二叉树中，第i层的节点最多有2(i-1)个。

     <2>  深度为k的二叉树最多有2k-1个节点。

     <3>  二叉树中，叶子节点树为n1个，度为2的节点有n2个，那么n1=n2+1。

     <4>  具有n个结点的二叉树深度为（log2 n）+1层。

     <5>  n个结点的完全二叉树如何用顺序存储，对于其中的一个结点i，存在以下关系，

              2*i是结点i的父结点。

              i/2是结点i的左孩子。

              (i/2)+1是结点i的右孩子。

4： 二叉树的顺序存储

      同样的存储方式也有两种，“顺序存储”和“链式存储”。

       <1> 顺序存储

                 说实话，树的存储用顺序结构比较少，因为从性质定理中我们都可以看出只限定为“完全二叉树”，那么如果二叉树不是

              “完全二叉树”，那我们就麻烦了，必须将其转化为“完全二叉树”，将空的节点可以用“#”代替，图中也可看出，为了维护

              性质定理5的要求，我们牺牲了两个”资源“的空间。

     <2> 链式存储

               上面也说了，顺序存储会造成资源的浪费，所以嘛，我们开发中用的比较多的还是“链式存储”，同样“链式存储”

            也非常的形象，非常的合理。

               一个结点存放着一个“左指针”和一个“右指针”，这就是二叉链表。

               如何方便的查找到该结点的父结点，可以采用三叉链表。

5: 常用操作

      一般也就是“添加结点“，“查找节点”，“计算深度”，“遍历结点”，“清空结点”

<1> 这里我们就用二叉链表来定义链式存储模型
 

复制代码 代码如下:

<2> 添加结点

  要添加结点，我们就要找到添加结点的父结点，并且根据指示插入到父结点中指定左结点或者右结点。

复制代码 代码如下:

<3>  查找节点 

                 二叉树中到处都散发着递归思想，很能锻炼一下我们对递归的认识，同样查找也是用到了递归思想。

复制代码 代码如下:

<4> 计算深度

          这个问题纠结了我二个多小时，原因在于没有深刻的体会到递归，其实主要思想就是递归左子树和右子树，然后得出较大的一个。

复制代码 代码如下:

<5>  遍历结点

             二叉树中遍历节点的方法还是比较多的，有“先序”，“中序”，“后序”，“按层”，其实这些东西只可意会，不可言传，真的很难在口头

        上说清楚，需要反复的体会递归思想。

            先序：先访问根，然后递归访问左子树，最后递归右子树。（dlr模式）

            中序：先递归访问左子树，在访问根，最后递归右子树。（ldr模式）

            后序：先递归访问左子树，然后递归访问右子树，最后访问根。（lrd模式）

            按层：这个比较简单，从上到下，从左到右的遍历节点。

复制代码 代码如下:

<6> 清空二叉树

           虽然c#里面有gc，但是我们能自己释放的就不麻烦gc了，同样清空二叉树节点，我们用到了递归，说实话，这次练习让我喜欢

       上的递归，虽然xxx的情况下，递归的不是很好，但是递归还是很强大的。

复制代码 代码如下:

最后上一下总的代码

1. using system; 
2. using system.collections.generic; 
3. using system.linq; 
4. using system.text; 
5.  
6.  
7.  
8. namespace chaintree 
9. { 
10.     public class program 
11.     { 
12.         static void main(string[] args) 
13.         { 
14.             chaintreemanager manager = new chaintreemanager(); 
15.  
16.             //插入节点操作 
17.             chaintree<string> tree = createroot(); 
18.  
19.             //插入节点数据 
20.             addnode(tree); 
21.  
22.             //先序遍历 
23.             console.writeline("\n先序结果为： \n"); 
24.             manager.bintree_dlr(tree); 
25.  
26.             //中序遍历 
27.             console.writeline("\n中序结果为： \n"); 
28.             manager.bintree_ldr(tree); 
29.  
30.             //后序遍历 
31.             console.writeline("\n后序结果为： \n"); 
32.             manager.bintree_lrd(tree); 
33.  
34.             //层次遍历 
35.             console.writeline("\n层次结果为： \n"); 
36.             manager.length = 100; 
37.             manager.bintree_level(tree); 
38.  
39.             console.writeline("\n树的深度为：" + manager.bintreelen(tree) + "\n"); 
40.  
41.             console.readline(); 
42.  
43.         } 
44.  
45.         #region 生成根节点 
46.         /// <summary> 
47. /// 生成根节点 
48. /// </summary> 
49. /// <returns></returns> 
50.         static chaintree<string> createroot() 
51.         { 
52.             chaintree<string> tree = new chaintree<string>(); 
53.  
54.             console.writeline("请输入根节点，方便我们生成树\n"); 
55.  
56.             tree.data = console.readline(); 
57.  
58.             console.writeline("根节点生成已经生成\n"); 
59.  
60.             return tree; 
61.         } 
62.         #endregion 
63.  
64.         #region 插入节点操作 
65.         /// <summary> 
66. /// 插入节点操作 
67. /// </summary> 
68. /// <param name="tree"></param> 
69.         static chaintree<string> addnode(chaintree<string> tree) 
70.         { 
71.             chaintreemanager mananger = new chaintreemanager(); 
72.  
73.             while (true) 
74.             { 
75.                 chaintree<string> node = new chaintree<string>(); 
76.  
77.                 console.writeline("请输入要插入节点的数据：\n"); 
78.  
79.                 node.data = console.readline(); 
80.  
81.                 console.writeline("请输入要查找的父节点数据：\n"); 
82.  
83.                 var parentdata = console.readline(); 
84.  
85.                 if (tree == null) 
86.                 { 
87.                     console.writeline("未找到您输入的父节点，请重新输入。"); 
88.                     continue; 
89.                 } 
90.  
91.                 console.writeline("请确定要插入到父节点的：1 左侧，2 右侧"); 
92.  
93.                 direction direction = (direction)enum.parse(typeof(direction), console.readline()); 
94.  
95.                 tree = mananger.bintreeaddnode(tree, node, parentdata, direction); 
96.  
97.                 console.writeline("插入成功，是否继续？  1 继续， 2 退出"); 
98.  
99.                 if (int.parse(console.readline()) == 1) 
100.                     continue; 
101.                 else 
102.                     break; 
103.             } 
104.  
105.             return tree; 
106.         } 
107.         #endregion 
108.     } 
109.  
110.     #region 插入左节点或者右节点 
111.     /// <summary> 
112. /// 插入左节点或者右节点 
113. /// </summary> 
114.     public enum direction { left = 1, right = 2 } 
115.     #endregion 
116.  
117.     #region 二叉链表存储结构 
118.     /// <summary> 
119. /// 二叉链表存储结构 
120. /// </summary> 
121. /// <typeparam name="t"></typeparam> 
122.     public class chaintree<t> 
123.     { 
124.         public t data; 
125.  
126.         public chaintree<t> left; 
127.  
128.         public chaintree<t> right; 
129.     } 
130.     #endregion 
131.  
132.     /// <summary> 
133. /// 二叉树的操作帮助类 
134. /// </summary> 
135.     public class chaintreemanager 
136.     { 
137.         #region 按层遍历的length空间存储 
138.         /// <summary> 
139. /// 按层遍历的length空间存储 
140. /// </summary> 
141.         public int length { get; set; } 
142.         #endregion 
143.  
144.         #region 将指定节点插入到二叉树中 
145.         /// <summary> 
146. /// 将指定节点插入到二叉树中 
147. /// </summary> 
148. /// <typeparam name="t"></typeparam> 
149. /// <param name="tree"></param> 
150. /// <param name="node"></param> 
151. /// <param name="direction">插入做左是右</param> 
152. /// <returns></returns> 
153.         public chaintree<t> bintreeaddnode<t>(chaintree<t> tree, chaintree<t> node, t data, direction direction) 
154.         { 
155.             if (tree == null) 
156.                 return null; 
157.  
158.             if (tree.data.equals(data)) 
159.             { 
160.                 switch (direction) 
161.                 { 
162.                     case direction.left: 
163.                         if (tree.left != null) 
164.                             throw new exception("树的左节点不为空，不能插入"); 
165.                         else 
166.                             tree.left = node; 
167.  
168.                         break; 
169.                     case direction.right: 
170.                         if (tree.right != null) 
171.                             throw new exception("树的右节点不为空，不能插入"); 
172.                         else 
173.                             tree.right = node; 
174.  
175.                         break; 
176.                 } 
177.             } 
178.  
179.             bintreeaddnode(tree.left, node, data, direction); 
180.             bintreeaddnode(tree.right, node, data, direction); 
181.  
182.             return tree; 
183.         } 
184.         #endregion 
185.  
186.         #region 获取二叉树指定孩子的状态 
187.         /// <summary> 
188. /// 获取二叉树指定孩子的状态 
189. /// </summary> 
190. /// <typeparam name="t"></typeparam> 
191. /// <param name="tree"></param> 
192. /// <param name="direction"></param> 
193. /// <returns></returns> 
194.         public chaintree<t> bintreechild<t>(chaintree<t> tree, direction direction) 
195.         { 
196.             chaintree<t> childnode = null; 
197.  
198.             if (tree == null) 
199.                 throw new exception("二叉树为空"); 
200.  
201.             switch (direction) 
202.             { 
203.                 case direction.left: 
204.                     childnode = tree.left; 
205.                     break; 
206.                 case direction.right: 
207.                     childnode = tree.right; 
208.                     break; 
209.             } 
210.  
211.             return childnode; 
212.         } 
213.  
214.         #endregion 
215.  
216.         #region 获取二叉树的深度 
217.         /// <summary> 
218. /// 获取二叉树的深度 
219. /// </summary> 
220. /// <typeparam name="t"></typeparam> 
221. /// <param name="tree"></param> 
222. /// <returns></returns> 
223.         public int bintreelen<t>(chaintree<t> tree) 
224.         { 
225.             int leftlength; 
226.             int rightlength; 
227.  
228.             if (tree == null) 
229.                 return 0; 
230.  
231.             //递归左子树的深度 
232.             leftlength = bintreelen(tree.left); 
233.  
234.             //递归右子书的深度 
235.             rightlength = bintreelen(tree.right); 
236.  
237.             if (leftlength > rightlength) 
238.                 return leftlength + 1; 
239.             else 
240.                 return rightlength + 1; 
241.         } 
242.         #endregion 
243.  
244.         #region 判断二叉树是否为空 
245.         /// <summary> 
246. /// 判断二叉树是否为空 
247. /// </summary> 
248. /// <typeparam name="t"></typeparam> 
249. /// <param name="tree"></param> 
250. /// <returns></returns> 
251.         public bool bintreeisempty<t>(chaintree<t> tree) 
252.         { 
253.             return tree == null ? true : false; 
254.         } 
255.         #endregion 
256.  
257.         #region 在二叉树中查找指定的key 
258.         /// <summary> 
259. ///在二叉树中查找指定的key 
260. /// </summary> 
261. /// <typeparam name="t"></typeparam> 
262. /// <param name="tree"></param> 
263. /// <param name="data"></param> 
264. /// <returns></returns> 
265.         public chaintree<t> bintreefind<t>(chaintree<t> tree, t data) 
266.         { 
267.             if (tree == null) 
268.                 return null; 
269.  
270.             if (tree.data.equals(data)) 
271.                 return tree; 
272.  
273.             return bintreefind(tree, data); 
274.         } 
275.         #endregion 
276.  
277.         #region 清空二叉树 
278.         /// <summary> 
279. /// 清空二叉树 
280. /// </summary> 
281. /// <typeparam name="t"></typeparam> 
282. /// <param name="tree"></param> 
283.         public void bintreeclear<t>(chaintree<t> tree) 
284.         { 
285.             //递的结束点，归的起始点 
286.             if (tree == null) 
287.                 return; 
288.  
289.             bintreeclear(tree.left); 
290.             bintreeclear(tree.right); 
291.  
292.             //在归的过程中，释放当前节点的数据空间 
293.             tree = null; 
294.         } 
295.         #endregion 
296.  
297.         #region 二叉树的先序遍历 
298.         /// <summary> 
299. /// 二叉树的先序遍历 
300. /// </summary> 
301. /// <typeparam name="t"></typeparam> 
302. /// <param name="tree"></param> 
303.         public void bintree_dlr<t>(chaintree<t> tree) 
304.         { 
305.             if (tree == null) 
306.                 return; 
307.  
308.             //先输出根元素 
309.             console.write(tree.data + "\t"); 
310.  
311.             //然后遍历左子树 
312.             bintree_dlr(tree.left); 
313.  
314.             //最后遍历右子树 
315.             bintree_dlr(tree.right); 
316.         } 
317.         #endregion 
318.  
319.         #region 二叉树的中序遍历 
320.         /// <summary> 
321. /// 二叉树的中序遍历 
322. /// </summary> 
323. /// <typeparam name="t"></typeparam> 
324. /// <param name="tree"></param> 
325.         public void bintree_ldr<t>(chaintree<t> tree) 
326.         { 
327.             if (tree == null) 
328.                 return; 
329.  
330.             //优先遍历左子树 
331.             bintree_ldr(tree.left); 
332.  
333.             //然后输出节点 
334.             console.write(tree.data + "\t"); 
335.  
336.             //最后遍历右子树 
337.             bintree_ldr(tree.right); 
338.         } 
339.         #endregion 
340.  
341.         #region 二叉树的后序遍历 
342.         /// <summary> 
343. /// 二叉树的后序遍历 
344. /// </summary> 
345. /// <typeparam name="t"></typeparam> 
346. /// <param name="tree"></param> 
347.         public void bintree_lrd<t>(chaintree<t> tree) 
348.         { 
349.             if (tree == null) 
350.                 return; 
351.  
352.             //优先遍历左子树 
353.             bintree_lrd(tree.left); 
354.  
355.             //然后遍历右子树 
356.             bintree_lrd(tree.right); 
357.  
358.             //最后输出节点元素 
359.             console.write(tree.data + "\t"); 
360.         } 
361.         #endregion 
362.  
363.         #region 二叉树的按层遍历 
364.         /// <summary> 
365. /// 二叉树的按层遍历 
366. /// </summary> 
367. /// <typeparam name="t"></typeparam> 
368. /// <param name="tree"></param> 
369.         public void bintree_level<t>(chaintree<t> tree) 
370.         { 
371.             if (tree == null) 
372.                 return; 
373.  
374.             //申请保存空间 
375.             chaintree<t>[] treelist = new chaintree<t>[length]; 
376.  
377.             int head = 0; 
378.             int tail = 0; 
379.  
380.             //存放数组 
381.             treelist[tail] = tree; 
382.  
383.             //循环链中计算tail位置 
384.             tail = (tail + 1) % length; 
385.  
386.             while (head != tail) 
387.             { 
388.                 var tempnode = treelist[head]; 
389.  
390.                 head = (head + 1) % length; 
391.  
392.                 //输出节点 
393.                 console.write(tempnode.data + "\t"); 
394.  
395.                 //如果左子树不为空,则将左子树存于数组的tail位置 
396.                 if (tempnode.left != null) 
397.                 { 
398.                     treelist[tail] = tempnode.left; 
399.  
400.                     tail = (tail + 1) % length; 
401.                 } 
402.  
403.                 //如果右子树不为空，则将右子树存于数组的tail位置 
404.                 if (tempnode.right != null) 
405.                 { 
406.                     treelist[tail] = tempnode.right; 
407.  
408.                     tail = (tail + 1) % length; 
409.                 } 
410.             } 
411.         } 
412.         #endregion 
413.  
414.     } 
415. } 

我们把文章开头的“二叉树”的节点输入到我们的结构中，看看遍历效果咋样。