---

一、什么是线索二叉树（TBT）？

线索二叉树是一种优化的二叉树结构，对于以结构体指针实现二叉树的方案进行了顺序遍历的优化。

常见的使用结构体指针构建二叉树的方式如图所示：

我们知道，在使用结构体指针构建二叉树时，由于二叉树不满，会产生大量没有意义的指针，事实上即使二叉树为满二叉树，其叶子节点的左子与右子指针也为空。面对数据范围巨大的要求，过多指针的浪费是非常危险的，但是这种情况是结构体指针方案所难以避免的，而我们使用结构体指针其实也是难以避免的

而当我们对二叉树进行不从根结点开始的顺序遍历时，我们要想找到该节点的前趋和后继的结点，我们又必须从根开始遍历一遍。

要想不反复遍历，我们就有两个解决方案：
1.重新建一个数组，先遍历一遍，然后记下来。
2.即本篇文章所说的线索二叉树，这种方案相较上面的方案，不需要重新建数组，直接利用二叉树浪费的空指针完成遍历的记录。

二、线索二叉树的建立

以上图二叉树为例，要求给出该二叉树的中序遍历，线索化方法如图所示：

注意：图中我们用原来左儿子结点指针指前驱，用原来右儿子指针指后继
由此，我们得到了一个线索二叉树。
这个时候，举几个例子感受一下
1，我要求找B的中序遍历前驱：
那我们知道，中序遍历：左根右，所以找中序遍历左子树找到（不需要搜索整树）
2，我们要求E的中序遍历后继：
直接顺着右子树，过去就是。

但是考虑到这种情况：对于访问到的一个节点，其左右子树都不是空指针，那么我们如何确定这个点的指针指的是左右子还是前驱后继呢？这个问题可以通过加入一个bool类型的变量对其记录类型进行标记来解决。很容易分析出来，一个bool变量占用的内存空间一定是比一个指针占用的空间要小的。

于是，我们遍历，然后记录，便可以很轻便的解决这个遍历速度的问题。

当然了，对于较小的数据范围或者一台合格的电脑，我们很明显不需要如此去为空间操劳，但是如果我们面临着巨大的数据范围或者是在单片机上快速查询的要求，我们可以考虑这个方案。

其实，我们并不会经常用到它，但是我们需要理解其内部的利用空余空间的思想，即当我们有冗余的空间时，我们还可以利用它来准备我们后续实现某种功能所需要的东西。

三、线索二叉树的实现

#include
using namespace std;

// 根据既定前序与中序序列递归构造二叉树 
vector<int> inorder = {4,2,7,5,1,3,8,6,9};
vector<int> preorder = {1,2,4,5,7,3,6,8,9};

typedef struct ThreadNode{
    struct ThreadNode *ltree = NULL;
    struct ThreadNode *rtree = NULL;
    int ltag = 0;
    int rtag = 0;
    int data;
}ThreadNode,*ThreadTree;

ThreadNode* BuildTree(vector<int> &preorder,vector<int> &inorder){
    if (preorder.empty() || inorder.empty()) return nullptr;
    ThreadNode *root = (ThreadNode *) malloc(sizeof(ThreadNode));
    root->data = preorder[0];
    auto inRoot = find(inorder.begin(), inorder.end(), preorder[0]);
    vector<int> inLeft(inorder.begin(), inRoot);
    vector<int> inRight(inRoot+1, inorder.end());

    int inLeftSize = inLeft.size(); //两种遍历数组的长度是一样的
    vector<int> preLeft(preorder.begin()+1, preorder.begin()+1+inLeftSize);
    vector<int> preRight(preorder.begin()+1+inLeftSize, preorder.end());

    // 5、递归处理左右子树
    root->ltree = BuildTree(preLeft, inLeft);
    root->rtree = BuildTree(preRight, inRight);
    return root;

}

void visit(ThreadNode *root){
    cout<<root->data<<" ";
}

// 构建前序遍历函数 
void Preorder(ThreadNode *root){
    if(root == NULL) return;
    Preorder(root->ltree);
    visit(root);
    Preorder(root->rtree);
}

// 构建中序遍历函数 
void Inorder(ThreadNode *root){
    if(root == NULL) return;
    Inorder(root->ltree);
    visit(root);
    Inorder(root->rtree);
}

// 设置后序遍历函数
void Postorder(ThreadNode *root){
    if(root == NULL) return;
    Postorder(root->ltree);
    Postorder(root->rtree);
    visit(root);
} 

// 中序线索二叉树的改造
void InThread(ThreadNode *root, ThreadNode *pre){
    if(root != NULL){
        InThread(root->ltree,pre);
        if(root->ltree == NULL){
            root->ltree = pre;
            root->ltag = 1;
        }

        if(pre != NULL && pre->rtree == NULL){
            pre->rtree = root;
            pre->rtag = 1;
        }

        pre = root;
        InThread(root->rtree,pre);
    }
} 

int main(){
    ThreadNode *root = BuildTree(preorder,inorder);
    ThreadNode *pre = NULL;
    InThread(root,pre);
    pre->rtree = NULL;
    pre->rtag = 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88