中序线索二叉树

代码部分

以下内容参考数据结构教程（C++语言描述）（第2版·微课视频版）

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include<iostream>
#include<stack>
using namespace std;

//以下仅涉及中序线索化二叉树

struct BthNode
{
    char data;
    BthNode *lchild, *rchild;
    int ltag, rtag;             
    //标记为0，则表示指针域存储的为孩子
    //标记为1，则表示指针域存储的是前驱后继结点
    BthNode() {}
    BthNode(char d){
        data = d;
        ltag = rtag = 0;
        lchild = rchild = NULL;
    }
};

class ThreadTree{                   //中序线索二叉树类
    BthNode *r;                     //二叉树的根节点
    BthNode *root;                  //线索二叉树的头结点指针
    BthNode *pre;                   //用于中序线索化，指向中序前驱结点
public:
    ThreadTree(){                   //构造函数，用于初始化
        //初始二叉树和线索二叉树为空树
        r = NULL;
        root = NULL;
    }
    
    ~ThreadTree(){
        if(r != NULL){
            DestoryBTree(r);
        }
        if(root != NULL){
            DestoryBTree(root);
        }
    }

    void DestoryBTree(BthNode *b){
        if(b->ltag == 0){
            DestoryBTree(b->lchild);
        }
        if(b->rtag == 0){
            DestoryBTree(b->rchild);
        }
        delete b;
    }

    void CreateBTree(string str);//括号表示法构建二叉树

    void DispBTree();//输出二叉树的括号表示串

    void DispBTree(BthNode *b);

    //建立以root为结点的中序线索二叉树
    //p是永远指向中序遍历当前的结点的，pre只需要在调用Thread前更新为p即可，不要害怕，干就完了！
    void CreateThread(){
        root = new BthNode();
        root->ltag = 0;
        root->rtag = 1;
        root->rchild = r;
        if(r == nullptr){
            root->lchild = root;
            root->rchild = nullptr;
        }else{
            root->lchild = r;
            pre = root;
            Thread(r);
            pre->rchild = root;//因为中序遍历的最后一个结点是叶子结点，所以压根不用管其他条件，Thread结束后直接把pre的后继设为root即可
            pre->rtag = 1;
            root->rchild = pre;
        }
    }

    void Thread(BthNode* p){
        if (p != nullptr)
        {
            Thread(p->lchild);
            if(p->lchild == nullptr){
                p->ltag = 1;
                p->lchild = pre;
            }else{
                p->ltag = 0;
            }
            if(pre->rchild == nullptr){
                pre->rchild = p;
                pre->rtag = 1;
            }else{
                pre->rtag = 0;
            }
            pre = p;
            Thread(p->rchild);
        }
    }

    void ThInOrder();//中序遍历中序线索二叉树
};

void ThreadTree::CreateBTree(string str){
    stack<BthNode*> st;
    BthNode *p;
    bool flag;
    int i = 0;
    while(i < str.length()){
        switch(str[i]){
        case '('://说明该结点p有孩子
            st.push(p);
            flag = true;
            break;
        case ')'://说明p的孩子已经处理完了
            st.pop();
            break;
        case ','://说明栈顶结点有右孩子
            flag = false;//表示开始处理栈顶结点的右孩子
            break;
        default://即遇到的是字符
            p = new BthNode(str[i]);
            if(r == NULL){//如果
                r = p;
            }else{
                if(flag && !st.empty()){
                    //该结点作为栈顶结点的左孩子结点
                    st.top()->lchild = p;
                }else if(!st.empty()){
                    //该结点作为栈顶结点的右孩子结点
                    st.top()->rchild = p;
                }
            }
            break;
        }
        i++;
    }
}

void ThreadTree::DispBTree(){
    DispBTree(r);
}

void ThreadTree::DispBTree(BthNode *b){
    if(b != nullptr){
        cout << b->data;
        if(b->lchild != nullptr || b->rchild != nullptr){
            cout << '(';
            DispBTree(b->lchild);
            cout << ',';
            DispBTree(b->rchild);
            cout << ')';
        }
    }
}

void ThreadTree::ThInOrder(){
    BthNode *p = root->lchild;
    while(p != root){
        while(p->lchild != nullptr){//这个循环就是不断找到开始结点的过程
            p = p->lchild;
        }
        cout << p->data << ' ';
        while(p->rtag == 1 && p->rchild != root){//这个循环就是不断找到后继结点的过程
            p = p->rchild;
            cout << p->data;
        }
        p = p->rchild;//这里改变p的值，再次进入大循环就是无法直接找到它的后继，但是可以通过再次找到开始结点的方式找到以它为前驱的结点
    }
}

重点部分理解

构建中序线索二叉树

把当前所处结点记作p，前驱结点记作pre

  • 由于是中序遍历，所以递归函数的基本顺序仍然已知，左中右
  • 要想清楚Thread对当前所处的结点（p）的作用是什么
    1. 首先，p是pre的后继，pre是p的前驱，而线索化的过程则是为每个结点探索添加前驱后继的可能性，那么在每个函数中p的可能性就是获得前驱和成为后继
    2. 先看是否可以获得前驱，即检查p的左孩子指针域是否为空：不为空，那很可惜，无法获得；为空，则把p的指针指向pre并改变p的左标记
    3. 再看是否可以成为后继，即检查pre的右孩子指针域是否为空：不为空，那很可惜，无法成为；为空，则把pre的指针指向p，并改变pre的右标记
  • 当把当前的结点的操作干完之后，我们才可以在中序遍历的顺序串上向后移动，也就是说，对p本身的操作结束后，才会改变pre，使p成为pre（即用p给pre赋值）

遍历线索化二叉树

首先我们要知道，构建线索化二叉树的目的就是为了避免以递归（空间上优化）的方式遍历（毕竟构建只用一次，但是遍历不止一次）。那么为了在遍历时获得和递归同样结果的顺序串，我们就要利用构建好的前驱后继关系。

非递归，自然离不开循环，那如何知道我们已经走到了顺序串末尾呢？这就和前面的设计联系起来了，我们已经让最后一个结点指向了root，所以循环从root的左孩子开始，也在回到root时结束

  1. 找到中序序列开始的位置（即最左下方的结点）并输出
  2. 尝试找到它的后继并输出
    1. 它的右指针是后继：则直接访问
    2. 它的右指针不是后继：那么就找以它的为前驱的结点啊，这不也就相当于找到了它的后继嘛。而对于一个右子树不为空的树，容易知道“以它为前驱的结点”（它的后继）就是它的右子树的最左下方的结点。