笔试算法题（41）：线索二叉树（Threaded Binary Tree）

议题：线索二叉树（Threaded Binary Tree）

分析：

为除第一个节点外的每个节点添加一个指向其前驱节点的指针，为除最后一个节点外的每个节点添加一个指向其后续节点的指针，通过这些额外的指针可以某种遍历方式对二叉树进行遍历，而加了这些额外指针的二叉树就是线索二叉树；
对于含有N个节点的二叉树而言，一共有2N个指针，但除了根节点的其他节点都有来自其父节点的指针，所以耗用了N-1个指针，则最终剩下2N-(N- 1)=N+1个空指针；线索二叉树就是利用这些空指针存储具有某种遍历顺序的前驱和后续，就遍历顺序而言线索二叉树分为：前序，中序和后序三种线索二叉树；
将一棵二叉树进行线索化就是为其空指针赋值的过程，所以需要对二叉树进行对应的遍历（如构建前序线索二叉树，就需要对二叉树进行前序遍历）；如下例子是将一棵二叉树线索化为一棵中序线索二叉树，
构建线索二叉树的时间复杂度为O(N)，其可以在O(1)或者O(logN)的时间复杂度内找到指定节点在某种遍历下的前驱和后续，但是其维护成本较高，但插入或者删除节点的时候，需要花费额外的时间维护线索指针的正确性；

样例：

 1 struct ThreadedNode {
 2         int value;
 3         int Lthread;
 4         int Rthread;
 5         ThreadedNode *left;
 6         ThreadedNode *right;
 7 };
 8 /**
 9  * 这里仅实现了中序线索化，前序跟后序线索化的实现只是处理节点的顺序
10  * 更改
11  * */
12 void InOrderThreaded(ThreadedNode *cur, ThreadedNode *pre) {
13         if(cur==NULL)
14                 return;
15         else {
16                 /**
17                  * 中序遍历：首先处理左子树，然后当前节点，最后右子树
18                  * */
19                 InOrderThreaded(cur->left, pre);
20 
21                 /**
22                  * 首先对当前节点的Lthread和Rthread标志进行初始化
23                  * */
24                 if(cur->left==NULL)
25                         cur->Lthread=1;
26                 else
27                         cur->Lthread=0;
28 
29                 if(cur->right==NULL)
30                         cur->Rthread=1;
31                 else
32                         cur->Rthread=0;
33                 /**
34                  * 一开始pre需要设置为NULL，但是也可以创建一个head节点，这样就
35                  * 不用每次都进行pre!=NULL的判断
36                  * */
37                 if(pre!=NULL) {
38                         /**
39                          * 完成前一个节点的后续线索化
40                          * */
41                         if(pre->Rthread==1)
42                                 pre->right=cur;
43                         /**
44                          * 完成当前节点的前驱线索化
45                          * */
46                         if(cur->Lthread==1)
47                                 cur->left=pre;
48                 }
49                 pre=cur;
50 
51                 InOrderThreaded(cur->right, pre);
52         }
53 }
54 
55 /**
56  * 查找给定节点target在线索二叉树root的中序遍历中的后续节点successor
57  * 分两种情况：
58  * 1. 如果target的右子树非空，则其后续节点是中序遍历右子树的第一个节点，O(logN)
59  * 2. 如果target的右子树为空，则其后续节点直接就是target->right指向的节点,利用线索化优势,O(1)
60  * */
61 ThreadedNode* FindSuccessor(ThreadedNode *target) {
62         /**
63          * 利用线索化标记进行判断
64          * */
65         if(target->Rthread==1)
66                 return target->right;
67         else {
68                 ThreadedNode *temp=target->right;
69                 /**
70                  * 利用线索化标记进行判断
71                  * */
72                 while(temp->Lthread==0)
73                         temp=temp->left;
74                 return temp;
75         }
76 }
77 
78 /**
79  * 查找给定节点target在线索二叉树root的中序遍历中的前驱节点precursor
80  * 分两种情况：
81  * 1. 如果target的左子树非空，则其前驱节点是中序遍历左子树的最后一个节点，O(logN)
82  * 2. 如果target的左子树为空，则其前驱节点就直接是target->left指向的节点，利用线索化优势，O(1)
83  * */
84 ThreadedNode* FindPrecursor(ThreadedNode *target) {
85         if(target->Lthread==1)
86                 return target->left;
87         else {
88                 ThreadedNode *temp=target->left;
89                 while(temp->Rthread==0)
90                         temp=temp->right;
91                 return temp;
92         }
93 }

参考连接：
http://student.zjzk.cn/course_ware/data_structure/web/main.htm