biscuitの博客

线索二叉树#

四种遍历得到的序列，结点之间有先后关系，例如序列BDAC,D称为A的前驱，C称为A的后继

如何在树中找任意节点的前驱或者后继？

对二叉树的链式存储方式进行修改，利用空指针，让他们指向前驱或者后继。依据的结论是空指针的个数=结点个数+1。这种指向前驱或者后继的空指针称为线索 线索指空的含义不再是没有孩子，而是没有前驱或后继。

左指针指向前驱，右指针指向后继。

基于先序序列的线索二叉树称为先序线索二叉树，以此类推。不同序列构造的线索二叉树唯一。这个过程称为二叉树的线索化

1
 struct BTreeNode {
2
    int data;
3
    BTreeNode* left;
4
    BTreeNode* right;
5
    int ltag
6
    int rtag // 引入tag来说明是指向前驱后继（1）还是左右孩子（0）。
7
    TreeNode(int val) : data(val), left(nullptr), right(nullptr)
8
}

二叉树的线索化#

根据序列判断前驱后继，检查左右指针是否为空，如果为空则改成线索。

线索二叉树的遍历#

只有空指针改成了线索，原来左右指针非空的结点如何寻找前驱后继？

遍历定义为从第一个结点开始不断找后继的过程。

TIP

后继只和右线索有关，可以隐藏所有左线索。

中序线索二叉树找中序前驱：