原文:
算法系列15天速成——第十二天 树操作【中】
View Code
先前说了树的基本操作，我们采用的是二叉链表来保存树形结构，当然二叉有二叉的困扰之处，比如我想找到当前结点
的“前驱”和“后继”，那么我们就必须要遍历一下树，然后才能定位到该“节点”的“前驱”和“后继”，每次定位都是O（n），这
不是我们想看到的，那么有什么办法来解决呢？
（1） 在节点域中增加二个指针域，分别保存“前驱”和“后继”，那么就是四叉链表了，哈哈，还是有点浪费空间啊。
（2） 看下面的这个二叉树，我们知道每个结点有2个指针域，4个节点就有8个指针域，其实真正保存节点的指针
仅有3个，还有5个是空闲的，那么为什么我们不用那些空闲的指针域呢，达到资源的合理充分的利用。
一： 线索二叉树
1 概念
刚才所说的在空闲的指针域里面存放“前驱”和“后继”就是所谓的线索。
<1> 左线索： 在空闲的左指针域中存放该“结点”的“前驱”被认为是左线索。
<2> 右线索： 在空闲的右指针域中存放该“结点“的”后继“被认为是右线索。
当“二叉链表”被套上这种线索，就被认为是线索链表，当“二叉树”被套上这种线索就被认为是线索二叉树，当然线索根据
二叉树的遍历形式不同被分为“先序线索”，“中序线索”，“后序线索”。
2 结构图
说了这么多，我们还是上图说话，就拿下面的二叉树，我们构建一个中序线索二叉树，需要多动动脑子哟。
<1> 首先要找到“中序遍历”中的首结点D，因为“D结点”是首节点，所以不存在“前驱”，左指针自然是空，
”D节点”的右指针存放的是“后继”，那么根据“中序遍历”的规则应该是B，所以D的右指针存放着B节点。
<2> 接着就是“B节点”，他的左指针不为空，所以就不管了，但是他的“右指针”空闲，根据规则“B结点“的右
指针存放的是"A结点“。
<3> 然后就是“A节点”，他已经被塞的满满的，所以就没有“线索”可言了。
<4> 最后就是“C节点”，根据规则，他的“左指针”存放着就是“A节点“，”C节点“是最后一个节点，右指针自然就是空的，你懂的。
3 基本操作
常用的操作一般有“创建线索二叉树”，”查找后继节点“，”查找前驱节点“，”遍历线索二叉树“，下面的操作我们就以”中序遍历“
来创建中序线索二叉树。
<1> 线索二叉树结构
从“结构图”中可以看到，现在结点的指针域中要么是”子节点（SubTree）“或者是”线索（Thread）“，此时就要设立标志位来表示指针域
存放的是哪一种。
1 #region 节点标识(用于判断孩子是节点还是线索)
2 /// <summary>
3 /// 节点标识(用于判断孩子是节点还是线索)
4 /// </summary>
5 public enum NodeFlag
6 {
7 SubTree = 1,
8 Thread = 2
9 }
10 #endregion
11
12 #region 线索二叉树的结构
13 /// <summary>
14 /// 线索二叉树的结构
15 /// </summary>
16 /// <typeparam name="T"></typeparam>
17 public class ThreadTree<T>
18 {
19 public T data;
20 public ThreadTree<T> left;
21 public ThreadTree<T> right;
22 public NodeFlag leftFlag;
23 public NodeFlag rightFlag;
24 }
25 #endregion
<2> 创建线索二叉树
刚才也说了如何构建中序线索二叉树，在代码实现中，我们需要定义一个节点来保存当前节点的前驱，我练习的时候迫不得已，只能使用两个
ref来实现地址操作，达到一个Tree能够让两个变量来操作。
1 #region 中序遍历构建线索二叉树
2 /// <summary>
3 /// 中序遍历构建线索二叉树
4 /// </summary>
5 /// <typeparam name="T"></typeparam>
6 /// <param name="tree"></param>
7 public void BinTreeThreadingCreate_LDR<T>(ref ThreadTree<T> tree, ref ThreadTree<T> prevNode)
8 {
9 if (tree == null)
10 return;
11
12 //先左子树遍历，寻找起始点
13 BinTreeThreadingCreate_LDR(ref tree.left, ref prevNode);
14
15 //如果left为空，则说明该节点可以放“线索”
16 tree.leftFlag = (tree.left == null) ? NodeFlag.Thread : NodeFlag.SubTree;
17
18 //如果right为空，则说明该节点可以放“线索”
19 tree.rightFlag = (tree.right == null) ? NodeFlag.Thread : NodeFlag.SubTree;
20
21 if (prevNode != null)
22 {
23 if (tree.leftFlag == NodeFlag.Thread)
24 tree.left = prevNode;
25 if (prevNode.rightFlag == NodeFlag.Thread)
26 prevNode.right = tree;
27 }
28
29 //保存前驱节点
30 prevNode = tree;
31
32 BinTreeThreadingCreate_LDR(ref tree.right, ref prevNode);
33 }
34 #endregion
<3> 查找后继结点
现在大家都知道，后继结点都是保存在“结点“的右指针域中，那么就存在”两种情况“。
《1》 拿“B节点“来说，他没有右孩子，则肯定存放着线索（Thread),所以我们直接O（1）的返回他的线索即可。
《2》 拿“A节点”来说，他有右孩子，即右指针域存放的是SubTree，悲哀啊，如何才能得到“A节点“的后继呢？其实也很简单，
根据”中序“的定义，”A节点“的后继必定是”A节点“的右子树往左链找的第一个没有左孩子的节点（只可意会，不可言传，嘻嘻）。
1 #region 查找指定节点的后继
2 /// <summary>
3 /// 查找指定节点的后继
4 /// </summary>
5 /// <typeparam name="T"></typeparam>
6 /// <param name="tree"></param>
7 public ThreadTree<T> BinTreeThreadNext_LDR<T>(ThreadTree<T> tree)
8 {
9 if (tree == null)
10 return null;
11
12 //如果查找节点的标志域中是Thread，则直接获取
13 if (tree.rightFlag == NodeFlag.Thread)
14 return tree.right;
15 else
16 {
17 //根据中序遍历的规则是寻找右子树中中序遍历的第一个节点
18 var rightNode = tree.right;
19
20 //如果该节点是subTree就需要循环遍历
21 while (rightNode.leftFlag == NodeFlag.SubTree)
22 {
23 rightNode = rightNode.left;
24 }
25 return rightNode;
26 }
27 }
28 #endregion
<4> 查找前驱节点
这个跟（3)的操作很类似，同样也具有两个情况。
《1》 拿“C结点”来说，他没有“左子树”，则说明“C节点”的左指针为Thread，此时，我们只要返回左指针域即可得到前驱结点。
《2》 拿"A节点“来说，他有”左子树“，则说明”A节点“的左指针为SubTree，那么怎么找的到”A节点“的前驱呢？同样啊，根据
”中序遍历“的性质，我们可以得知在”A节点“的左子树中往”右链“中找到第一个没有”右孩子“的节点。
1 #region 查找指定节点的前驱
2 /// <summary>
3 /// 查找指定节点的前驱
4 /// </summary>
5 /// <typeparam name="T"></typeparam>
6 /// <param name="tree"></param>
7 /// <returns></returns>
8 public ThreadTree<T> BinTreeThreadPrev_LDR<T>(ThreadTree<T> tree)
9 {
10 if (tree == null)
11 return null;
12
13 //如果标志域中存放的是线索，那么可以直接找出来
14 if (tree.leftFlag == NodeFlag.Thread)
15 return tree.left;
16 else
17 {
18 //根据”中序“的规则可知，如果不为Thread，则要找出左子树的最后节点
19 //也就是左子树中最后输出的元素
20 var leftNode = tree.left;
21
22 while (leftNode.rightFlag == NodeFlag.SubTree)
23 leftNode = leftNode.right;
24
25 return leftNode;
26 }
27 }
28 #endregion
<5> 遍历线索二叉树
因为我们构建线索的时候采用的是“中序”，那么我们遍历同样采用“中序”，大家是否看到了“线索”的好处，此时我们找某个节点的时间复杂度变为了
O(1) ~0(n)的时间段，比不是线索的时候查找“前驱"和“后继”效率要高很多。
1 #region 遍历线索二叉树
2 /// <summary>
3 /// 遍历线索二叉树
4 /// </summary>
5 /// <typeparam name="T"></typeparam>
6 /// <param name="tree"></param>
7 public void BinTreeThread_LDR<T>(ThreadTree<T> tree)
8 {
9 if (tree == null)
10 return;
11
12 while (tree.leftFlag == NodeFlag.SubTree)
13 tree = tree.left;
14
15 do
16 {
17 Console.Write(tree.data + "\t");
18
19 tree = BinTreeThreadNext_LDR(tree);
20
21 } while (tree != null);
22
23 }
24 #endregion
最后上一下总的运行代码
View Code
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5
6 namespace ThreadChainTree
7 {
8 class Program
9 {
10 static void Main(string[] args)
11 {
12 ThreadTreeManager manager = new ThreadTreeManager();
13
14 //生成根节点
15 ThreadTree<string> tree = CreateRoot();
16
17 //生成节点
18 AddNode(tree);
19
20 ThreadTree<string> prevNode = null;
21
22 //构建线索二叉树
23 manager.BinTreeThreadingCreate_LDR(ref tree, ref prevNode);
24
25 Console.WriteLine("\n线索二叉树的遍历结果为：\n");
26 //中序遍历线索二叉树
27 manager.BinTreeThread_LDR(tree);
28 }
29
30 #region 生成根节点
31 /// <summary>
32 /// 生成根节点
33 /// </summary>
34 /// <returns></returns>
35 static ThreadTree<string> CreateRoot()
36 {
37 ThreadTree<string> tree = new ThreadTree<string>();
38
39 Console.WriteLine("请输入根节点，方便我们生成树\n");
40
41 tree.data = Console.ReadLine();
42
43 Console.WriteLine("根节点生成已经生成\n");
44
45 return tree;
46 }
47 #endregion
48
49 #region 插入节点操作
50 /// <summary>
51 /// 插入节点操作
52 /// </summary>
53 /// <param name="tree"></param>
54 static ThreadTree<string> AddNode(ThreadTree<string> tree)
55 {
56 ThreadTreeManager mananger = new ThreadTreeManager();
57
58 while (true)
59 {
60 ThreadTree<string> node = new ThreadTree<string>();
61
62 Console.WriteLine("请输入要插入节点的数据：\n");
63
64 node.data = Console.ReadLine();
65
66 Console.WriteLine("请输入要查找的父节点数据：\n");
67
68 var parentData = Console.ReadLine();
69
70 if (tree == null)
71 {
72 Console.WriteLine("未找到您输入的父节点，请重新输入。");
73 continue;
74 }
75
76 Console.WriteLine("请确定要插入到父节点的：1 左侧，2 右侧");
77
78 Direction direction = (Direction)Enum.Parse(typeof(Direction), Console.ReadLine());
79
80 tree = mananger.BinTreeThreadAddNode(tree, node, parentData, direction);
81
82 Console.WriteLine("插入成功，是否继续？ 1 继续， 2 退出");
83
84 if (int.Parse(Console.ReadLine()) == 1)
85 continue;
86 else
87 break;
88 }
89
90 return tree;
91 }
92 #endregion
93 }
94
95 #region 节点标识(用于判断孩子是节点还是线索)
96 /// <summary>
97 /// 节点标识(用于判断孩子是节点还是线索)
98 /// </summary>
99 public enum NodeFlag
100 {
101 SubTree = 1,
102 Thread = 2
103 }
104 #endregion
105
106 #region 线索二叉树的结构
107 /// <summary>
108 /// 线索二叉树的结构
109 /// </summary>
110 /// <typeparam name="T"></typeparam>
111 public class ThreadTree<T>
112 {
113 public T data;
114 public ThreadTree<T> left;
115 public ThreadTree<T> right;
116 public NodeFlag leftFlag;
117 public NodeFlag rightFlag;
118 }
119 #endregion
120
121 #region 插入左节点或者右节点
122 /// <summary>
123 /// 插入左节点或者右节点
124 /// </summary>
125 public enum Direction { Left = 1, Right = 2 }
126 #endregion
127
128 #region 线索二叉树的基本操作
129 /// <summary>
130 /// 线索二叉树的基本操作
131 /// </summary>
132 public class ThreadTreeManager
133 {
134 #region 将指定节点插入到二叉树中
135 /// <summary>
136 /// 将指定节点插入到二叉树中
137 /// </summary>
138 /// <typeparam name="T"></typeparam>
139 /// <param name="tree"></param>
140 /// <param name="node"></param>
141 /// <param name="direction">插入做左是右</param>
142 /// <returns></returns>
143 public ThreadTree<T> BinTreeThreadAddNode<T>(ThreadTree<T> tree, ThreadTree<T> node, T data, Direction direction)
144 {
145 if (tree == null)
146 return null;
147
148 if (tree.data.Equals(data))
149 {
150 switch (direction)
151 {
152 case Direction.Left:
153 if (tree.left != null)
154 throw new Exception("树的左节点不为空，不能插入");
155 else
156 tree.left = node;
157
158 break;
159 case Direction.Right:
160 if (tree.right != null)
161 throw new Exception("树的右节点不为空，不能插入");
162 else
163 tree.right = node;
164
165 break;
166 }
167 }
168
169 BinTreeThreadAddNode(tree.left, node, data, direction);
170 BinTreeThreadAddNode(tree.right, node, data, direction);
171
172 return tree;
173 }
174 #endregion
175
176 #region 中序遍历构建线索二叉树
177 /// <summary>
178 /// 中序遍历构建线索二叉树
179 /// </summary>
180 /// <typeparam name="T"></typeparam>
181 /// <param name="tree"></param>
182 public void BinTreeThreadingCreate_LDR<T>(ref ThreadTree<T> tree, ref ThreadTree<T> prevNode)
183 {
184 if (tree == null)
185 return;
186
187 //先左子树遍历，寻找起始点
188 BinTreeThreadingCreate_LDR(ref tree.left, ref prevNode);
189
190 //如果left为空，则说明该节点可以放“线索”
191 tree.leftFlag = (tree.left == null) ? NodeFlag.Thread : NodeFlag.SubTree;
192
193 //如果right为空，则说明该节点可以放“线索”
194 tree.rightFlag = (tree.right == null) ? NodeFlag.Thread : NodeFlag.SubTree;
195
196 if (prevNode != null)
197 {
198 if (tree.leftFlag == NodeFlag.Thread)
199 tree.left = prevNode;
200 if (prevNode.rightFlag == NodeFlag.Thread)
201 prevNode.right = tree;
202 }
203
204 //保存前驱节点
205 prevNode = tree;
206
207 BinTreeThreadingCreate_LDR(ref tree.right, ref prevNode);
208 }
209 #endregion
210
211 #region 查找指定节点的后继
212 /// <summary>
213 /// 查找指定节点的后继
214 /// </summary>
215 /// <typeparam name="T"></typeparam>
216 /// <param name="tree"></param>
217 public ThreadTree<T> BinTreeThreadNext_LDR<T>(ThreadTree<T> tree)
218 {
219 if (tree == null)
220 return null;
221
222 //如果查找节点的标志域中是Thread，则直接获取
223 if (tree.rightFlag == NodeFlag.Thread)
224 return tree.right;
225 else
226 {
227 //根据中序遍历的规则是寻找右子树中中序遍历的第一个节点
228 var rightNode = tree.right;
229
230 //如果该节点是subTree就需要循环遍历
231 while (rightNode.leftFlag == NodeFlag.SubTree)
232 {
233 rightNode = rightNode.left;
234 }
235 return rightNode;
236 }
237 }
238 #endregion
239
240 #region 查找指定节点的前驱
241 /// <summary>
242 /// 查找指定节点的前驱
243 /// </summary>
244 /// <typeparam name="T"></typeparam>
245 /// <param name="tree"></param>
246 /// <returns></returns>
247 public ThreadTree<T> BinTreeThreadPrev_LDR<T>(ThreadTree<T> tree)
248 {
249 if (tree == null)
250 return null;
251
252 //如果标志域中存放的是线索，那么可以直接找出来
253 if (tree.leftFlag == NodeFlag.Thread)
254 return tree.left;
255 else
256 {
257 //根据”中序“的规则可知，如果不为Thread，则要找出左子树的最后节点
258 //也就是左子树中最后输出的元素
259 var leftNode = tree.left;
260
261 while (leftNode.rightFlag == NodeFlag.SubTree)
262 leftNode = leftNode.right;
263
264 return leftNode;
265 }
266 }
267 #endregion
268
269 #region 遍历线索二叉树
270 /// <summary>
271 /// 遍历线索二叉树
272 /// </summary>
273 /// <typeparam name="T"></typeparam>
274 /// <param name="tree"></param>
275 public void BinTreeThread_LDR<T>(ThreadTree<T> tree)
276 {
277 if (tree == null)
278 return;
279
280 while (tree.leftFlag == NodeFlag.SubTree)
281 tree = tree.left;
282
283 do
284 {
285 Console.Write(tree.data + "\t");
286
287 tree = BinTreeThreadNext_LDR(tree);
288
289 } while (tree != null);
290
291 }
292 #endregion
293 }
294 #endregion
295 }
将文章开头处的数据输入到存储结构中
