第5章：线索二叉树（Threaded Binary Tree）

线索二叉树

5.5 线索二叉树

5.5.1 线索的概念

  • 线索：在二叉链表中，将空的 leftChild 或 rightChild 指针改为指向其前驱或后继结点的指针。这边的前驱后继可以分别为前中后序遍历
  • 线索化：将二叉树变为线索二叉树的过程。
  • 线索二叉树的作用：
    • 在不使用递归或栈的情况下，实现高效的前序、中序、后序遍历。
    • 节省存储空间（利用空指针）。

结点结构

1
2
3
4
5
6
template <class T> struct ThreadNode {
    int ltag, rtag;          // 标志位：0表示孩子，1表示线索
    ThreadNode<T> *leftChild, *rightChild;
    T data;
    ThreadNode(const T item) : data(item), leftChild(NULL), rightChild(NULL), ltag(0), rtag(0) {}
};
  • `tag = 1 : 指向前驱或者后继， tag = 0 时仍然指向左右孩子节点

5.5.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
template<class T>
class ThreadTree {
protected:
    ThreadNode<T>* root; // 根节点
    void createInThread(ThreadNode<T>* current, ThreadNode<T>*& pre);
    ThreadNode<T>* parent(ThreadNode<T>* t);
public:
    ThreadTree() : root(nullptr) {};
    
    // 两种创建方式：递归和迭代
    void CreateInThread();      // 递归版本
    void CreateInThread2();     // 迭代版本
    //调用protected中的createInThread
    
    // 遍历相关操作
    ThreadNode<T>* First(ThreadNode<T>* current);
    ThreadNode<T>* Last(ThreadNode<T>* current);
    ThreadNode<T>* Next(ThreadNode<T>* current);
    ThreadNode<T>* prior(ThreadNode<T>* current);
    void Inorder(void(*visit)(ThreadNode<T>* p));
    
    // 前序后继查找
    ThreadNode<T>* Next_pre(ThreadNode<T>* p);
};

中序线索化算法

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

template<class T>
void ThreadTree<T>::CreateInThread() {
    ThreadNode<T>* pre = nullptr;
    if (root != nullptr) {
        createInThread(root, pre);  //调用protected里的同名重构函数
        pre->rightChild = nullptr;  // 最后一个节点的后继设为null
        pre->rtag = 1;
    }
}

template <class T>
void ThreadTree<T>::createInThread(ThreadNode<T>* current, ThreadNode<T>* &pre) {
    if (current == NULL) return;
    createInThread(current->leftChild, pre);  // 递归左子树 
    //先把左边的全部线索化
    // 建立当前结点的前驱线索
    if (current->leftChild == NULL) {
        current->leftChild = pre;
        current->ltag = 1;
    }
    // 建立前驱结点的后继线索
    if (pre != NULL && pre->rightChild == NULL) {
        pre->rightChild = current;
        pre->rtag = 1;
    }
    pre = current;
    createInThread(current->rightChild, pre); // 递归右子树
}
  • `注意以上pre传入的是引用，当然可以将pre放在全局里面，遍历，这样也是可以的

这边再给出自己写的一份迭代方法：

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
template<class T>
void ThreadTree<T>::CreateInThread2() {
    //用栈来模拟递归的过程
    stack<ThreadNode<T>*> s;
    ThreadNode<T>* p = root;        
    ThreadNode<T>* pre = nullptr;
    
    while (p != nullptr || !s.empty()) {
    //首先把左孩子结点全部压入栈中
        while (p != nullptr) {
            s.push(p);
            p = p->leftChild;
        }
        //如果遍历到nullptr节点，那么弹出栈顶的节点，此时就是需要建立线索的节点
        //之后进入右节点继续下一轮while压入左节点
        if (!s.empty()) {
            p = s.top();
            s.pop();
            
            // 建立前驱线索
            if (p->leftChild == nullptr) {
                p->leftChild = pre;
                p->ltag = 1;
            }
            
            // 建立前驱节点的后继线索
            if (pre != nullptr && pre->rightChild == nullptr) {
                pre->rightChild = p;
                pre->rtag = 1;
            }
            
            pre = p;
            p = p->rightChild;
        }
    }
}

中序遍历线索二叉树

1
2
3
4
5
6
7
template <class T>
void ThreadTree<T>::InOrder(void(*visit)(ThreadNode<T>* p)) {
    ThreadNode<T>* p;
    for (p = First(root); p != NULL; p = Next(p)) {
        visit(p);
    }
}
  • 采用线索化之后，中序遍历就变得很方便

寻找中序第一个结点

1
2
3
4
5
6
template <class T>
ThreadNode<T>* ThreadTree<T>::First(ThreadNode<T>* current) {
    ThreadNode<T>* p = current;
    while (p->ltag == 0) p = p->leftChild;  // 最左下结点
    return p;
}

寻找中序后继结点

1
2
3
4
5
6
7
8
template <class T>
ThreadNode<T>* ThreadTree<T>::Next(ThreadNode<T>* current) {
    ThreadNode<T>* p = current->rightChild;
    if (current->rtag == 0)  // 有右孩子
        return First(p);      // 返回右子树中第一个结点
    else
        return p;             // 直接返回后继线索
}

5.5.3 前序与后序线索二叉树

前序线索二叉树中找后继

  • 如果 ltag == 0，左孩子为后继；
  • 否则如果 rtag == 0，右孩子为后继；
  • 否则沿后继线索回溯到第一个有右孩子的结点，其右孩子为后继。
1
2
3
4
5
6
7
8
9
10
11
12
template <class T>
ThreadNode<T>* ThreadTree<T>::Next_Pre(ThreadNode<T>* p) {
    if (p == NULL) return NULL;
    if (p->ltag == 0) return p->leftChild;
    else if (p->rtag == 0) return p->rightChild;
    else {
        while (p != NULL && p->rtag == 1)
            p = p->rightChild;
        if (p == NULL) return NULL;
        return p->rightChild;
    }
}

后序线索二叉树中找后继

  • 需借助父结点指针或复杂回溯；
  • 若 rtag == 1，直接返回后继；
  • 否则需判断当前结点是否为父结点的右孩子，再决定后继。