树与二叉树补充I

发表于 2022-09-20 更新于 2025-10-26 分类于 CS ，数据结构 Disqus：

大家好，按照之前的计划，我们本应该去应用二叉树，实现一些应用的。然鹅，树与森林以及二叉树之间的关系、线索二叉树这些，没有给大家说。这可能会影响大家对之前知识的理解，所以还是补充一下。
我知道你已经迫不及待去敲代码了，学好这些理论可以让你更加清晰的认识代码，帮助你写出更出色的代码，以及节省思考如何写代码的时间。这是非常有必要的。
当你十分清楚流程，以及思路时，背后的代码，就像喝汤一样。

好，废话不多说。紧跟上篇，我想，先介绍一下线索二叉树。再介绍树、森林、以及二叉树三者的关系。

线索二叉树
树
1. 存储方式
2. 遍历
森林
1. 遍历
三者之间的关系

线索二叉树

还记得二叉树吗？二叉树中很多空指针。

一个n个结点的二叉树，有2n个指针，一条边就会少一个空指针，n个结点有n-1条边，所以空指针数量为2n - (n-1) = n+1

可见内存利用有些低，我们让这些有空指针的结点，如果左指针空，就让左指针指向遍历顺序的前驱，右指针空则指向遍历顺序的后继。没有前驱或者后继，指向空即可。

线索二叉树图片

按照遍历顺序，可以得到先序、中序、后序三种线索二叉树。

因为无法知道结点的指针到底是指向子结点，还是前驱或者后继，所以我们需要两个标志位来表示，当前指针指向的意义。

class node{
public:
    char data;
    node * lchild;
    node * rchild;
    bool ltag{false};
    bool rtag{false};
    node()=default;
    node(char d):data{d}{
        lchild = nullptr;
        rchild = nullptr;
    }
};

ltag为false代表当前lchild指向子节点，true表示指向前驱。rtag亦然。

这样下来我们的利用率就大大提高了，还能方便到遍历二叉树。

线索生成

我们在二叉树的基础上，来做。

按照遍历的三种顺序，会有三种生成的方式。我们只需要在访问该节点时，知道它的前驱节点就好。这样很难理解。

我想用代码来说明，如果实在不懂，可以参考王道考研上的线索二叉树。

拿中序线索二叉树来说。

例如这个树

{height=“300px” width=“300px”}

中序遍历结果CBEGDFA

node* pre=nullptr;

void toLineTree(node*& cur){
    if(cur== nullptr)return;

    toLineTree(cur->lchild);
    //指向前驱
    if(cur->lchild== nullptr){
        cur->lchild = pre;
        cur->ltag= true;
    }
    //指向后继
    if(pre!= nullptr&&pre->rchild== nullptr){
        pre->rchild=cur;
        pre->rtag= true;
    }
    pre = cur;
    toLineTree(cur->rchild);
}

先序结果ABCDEGF

先序与中序不同，当前驱节点指向前驱后，因为下一个要遍历左结点，左节点指向了前驱，这样就会又回到前驱结点，形成死环。因此需要判断是否已经指向前驱，如果已经指向前驱，就跳过去。

node* pre=nullptr;

void toLineTree(node*& cur){
    if(cur== nullptr)return;

   
    //指向前驱
    if(cur->lchild== nullptr){
        cur->lchild = pre;
        cur->ltag= true;
    }
    //指向后继
    if(pre!= nullptr&&pre->rchild== nullptr){
        pre->rchild=cur;
        pre->rtag= true;
    }
    pre = cur;
    if(cur->ltag==false) toLineTree(cur->lchild);
    toLineTree(cur->rchild);
}

后序结果CGEFDBA

node* pre=nullptr;

void toLineTree(node*& cur){
    if(cur== nullptr)return;

   
    //指向前驱

    
    toLineTree(cur->lchild);
    toLineTree(cur->rchild);
        if(cur->lchild== nullptr){
        cur->lchild = pre;
        cur->ltag= true;
    }
    //指向后继
    if(pre!= nullptr&&pre->rchild== nullptr){
        pre->rchild=cur;
        pre->rtag= true;
    }
    pre = cur;
}