浅谈二叉树线索化相关问题

二叉树线索化最简单的就是中序了，无脑按照中序遍历递归算法套就OK了。
现在我们有如下代码实现

1. //file:threadBiTree.h
2. #ifndef THREAD_BI_TREE_H
3. #define THREAD_BI_TREE_H
5. typedef struct threadBiNode {
6.     int data;
7.     struct threadBiNode *lchild, *rchild;
8.     int ltag, rtag;
9. }threadBiNode, *threadBiTree;
11. void _thread_in(threadBiTree &T, threadBiNode *&pre);
12. void create_thread_in(threadBiTree &T);
14. #endif
16. /**********************/
18. //file:threadBiTree.cpp
19. #include "threadBiTree.h"
21. void _thread_in(threadBiTree &T, threadBiNode *&pre)
22. {
23.     if (!T)
24.         return;
26.     _thread_in(T->lchild, pre);
27.     if (pre && pre->rchild == nullptr)
28.     {
29.         pre->rtag = 1;
30.         pre->rchild = T;
31.     }
33.     if (T->lchild == nullptr)
34.     {
35.         T->ltag = 1;
36.         T->lchild = pre;
37.     }
39.     pre = T;
40.     _thread_in(T->rchild, pre);
41. }
43. //assume that the tags of tree have been initialize by zero
44. void create_thread_in(threadBiTree &T)
45. {
46.     if (!T)
47.         return;
48.     threadBiNode *pre = nullptr;
49.     _thread_in(T, pre);
50.     if (pre)
51.     {
52.         pre->rtag = 1;
53.         pre->rchild = nullptr;
54.     }
55. }

复制代码

在笔者看来中序二叉树是一种很方便的数据结构，中序线索二叉树类似于一个双链表，可以沿着中序下第一个节点向后作中序遍历也可以沿着中序下最后一个节点向前作遍历，但是对于任意前序线索二叉树不一定能作反向前序遍历，任意后序线索二叉树不一定能作正向后序遍历。而要实现中序二叉树的双向遍历功能，只需要几个简单的辅助函数即可。而这些辅助函数的实现也很好理解，因为中序的第一个结点，最后一个节点，某个节点的直接前驱或后继都非常好找，而要怎么找这里就请看下面代码注释不赘述
于是我们有如下辅助函数和用于正反向中序遍历的函数

1. //file: threadBiTree.cpp
3. /**********用于正向中序遍历**********/
4. // assume that the data structure is validate
5. threadBiNode *first_thread_in(threadBiTree &T)
6. {
7.     if (!T)
8.         return nullptr;
9.     threadBiNode *p = T;
10.     while (p->ltag == 0)        //中序下第一个节点必然是整棵树最左下节点
11.         p = p->lchild;
12.     return p;
13. }
15. // assume that the data structure is validate
16. threadBiNode *next_thread_in(threadBiNode *&p)
17. {
18.     if (!p)
19.         return nullptr;
20.     if (p->rtag == 1)        //某个节点的后继要么是由其后继指针指定（即无右子树）
21.         return p->rchild;
22.     else
23.         return first_thread_in(p->rchild);        //要么是其右子树在中序下的第一个节点，简单理解为因为中序是LNR，现在存在右子树那就是R了，另外中序遍历是递归的
24. }
26. // assume that the data structure is validate
27. void traverse_thread_in(threadBiTree &T, void (*visit)(threadBiNode *&p))
28. {
29.     for (threadBiNode *p = first_thread_in(T); p != nullptr; p = next_thread_in(p))
30.         visit(p);
31. }
33. /**********用于逆向中序遍历**********/
34. // assume that the data structure is validate
35. threadBiNode *last_thread_in(threadBiTree &T)
36. {
37.     if (!T)
38.         return nullptr;
39.     threadBiNode *p = T;
40.     while (p->rtag == 0)        //中序下最后一个节点必然是整棵树最右下节点
41.         p = p->rchild;
42.     return p;
43. }
45. // assume that the data structure is validate
46. threadBiNode *previous_thread_in(threadBiNode *&p)
47. {
48.     if (!p)
49.         return nullptr;
50.     if (p->ltag == 1)        //前驱就往左子树上找，和找后继原理是一样的，无左子树则其前驱为该节点左线索所指明的节点
51.         return p->lchild;
52.     else
53.         return last_thread_in(p->lchild);        //有左子树，前驱就是左子树中序遍历下的最后一个节点
54. }
56. // assume that the data structure is validate
57. void traverse_reverse_thread_in(threadBiTree &T, void (*visit)(threadBiNode *&p))
58. {
59.     for (threadBiNode *p = last_thread_in(T); p != nullptr; p = previous_thread_in(p))
60.         visit(p);
61. }

复制代码

中序和后序二叉树实现方法上是一致的，照搬递归遍历算法即可，只是需要注意一下在最后一个节点线索化时不能照搬中序的，因为中序遍历下的最后一个结点必然无右孩子，于是这个结点的右指针必然是线索，但是后序显然不是
于是我们有如下二叉树后序线索化实现

1. /******postorder thread******/
2. // cannot be called by user
3. void _thread_post(threadBiTree &T, threadBiNode *&pre)
4. {
5.     if (!T)
6.         return;
7.     _thread_post(T->lchild, pre);
8.     _thread_post(T->rchild, pre);
9.     if (T->lchild == nullptr)
10.     {
11.         T->ltag = 1;
12.         T->lchild = pre;
13.     }
14.     if (pre && pre->rchild == nullptr)
15.     {
16.         pre->rtag = 1;
17.         pre->rchild = T;
18.     }
19.     pre = T;
20. }
22. // assume that the tags of tree have been initialize by zero
23. void create_thread_post(threadBiTree &T)
24. {
25.     if (!T)
26.         return;
27.     threadBiNode *pre = nullptr;
28.     _thread_post(T, pre);
29.     if (pre && pre->rchild == nullptr)        //如果最后一个结点右指针确实为空那么可以设其为线索
30.     {
31.         pre->rtag = 1;
32.     }
33. }

复制代码

至于用于反向遍历后序线索二叉树得到代码这里不给出，我也没去细想，反正考研不考，也就问问线索怎么个连法
最后一个就是前序二叉树线索化，前序二叉树线索化需要注意的就是避免某个结点被重复线索化，因为前序遍历的特点，必定是根先被线索化。可以这样想某个前序线索化到某个节点后，直接调用前序线索化函数，如果左指针是线索，那么就开始处理之前已经线索化的结点。试想，如果采用中序、后序类似的代码而不对函数递归调用作出限制，那么至少会产生无限递归的问题，例如我们可以考虑对图中对节点A的线索化

所以，限制以下递归调用的条件会产生正确结果，从而我们有如下二叉树先序线索化实现

1. //file: threadBiTree.cpp
3. /******preorder thread******/
4. // cannot be called by user
5. void _thread_pre(threadBiTree &T, threadBiNode *&pre)
6. {
7.     if (!T)
8.         return;
9.     if (pre && pre->rchild == nullptr)
10.     {
11.         pre->rtag = 1;
12.         pre->rchild = T;
13.     }
14.     if (T->lchild == nullptr)
15.     {
16.         T->ltag = 1;
17.         T->lchild = pre;
18.     }
19.     pre = T;
20.     if (T->ltag == 0) // 若已经线索化再次进入则会因为指针不空再次被线索化所以当未被线索化才递归执行线索化
21.         _thread_pre(T->lchild, pre);
22.     if (T->rtag == 0)
23.         _thread_pre(T->rchild, pre);
24. }
26. // assume that the tags of tree have been initialize by zero
27. void create_thread_pre(threadBiTree &T)
28. {
29.     if (!T)
30.         return;
31.     threadBiNode *pre = nullptr;
32.     _thread_pre(T, pre);
33.     if (pre && pre->rchild == nullptr)
34.     {
35.         pre->rtag = 1;
36.         pre->rchild = nullptr;
37.     }
38. }

复制代码

另外，先序遍历下的第一个节点明显根节点，某个节点的后继也很好找，如果该节点有左子树，那么左孩子就是其后继，若无左子树有右子树，那么就是右孩子，如果为叶节点，那么就是后继线索所指向的节点，这样我们能非常轻松地写出先序线索二叉树的正向先序遍历代码，如下所示

1. //file: threadBiTree.cpp
3. /**********用于正向中序遍历**********/
4. // assume that the data structure is validate
5. threadBiNode *first_thread_pre(threadBiTree &T) {
6.     return T;
7. }
9. // assume that the data structure is validate
10. threadBiNode *next_thread_pre(threadBiNode *&p) {
11.     if(!p)
12.         return nullptr;
13.     threadBiNode *q = p;
14.     if(q->ltag == 0)
15.         return q->lchild;
16.     else
17.         return q->rchild;
18. }
20. // assume that the data structure is validate
21. void traverse_thread_pre(threadBiTree &T, void (*visit)(threadBiNode *&p)) {
22.     for(threadBiNode *p = first_thread_pre(T); p != nullptr; p = next_thread_pre(p))
23.         visit(p);
24. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！