算法系列15天速成——第十二天 树操作【中】
先前说了树的基本操作，我们采用的是二叉链表来保存树形结构，当然二叉有二叉的困扰之处，比如我想找到当前结点
的“前驱”和“后继”，那么我们就必须要遍历一下树，然后才能定位到该“节点”的“前驱”和“后继”，每次定位都是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
www.zzzyk.com
<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
补充：软件开发 , 其他 ,
