轻松让你彻底搞定c++版线索二叉树的线索化算法

我会带着你远行 2022-06-06 14:16 229阅读 0赞

![这里写图片描述][SouthEast]  
二叉树图

首先我们要先谈谈线索二叉树数据结构的出现理由，为什么要出现。我们可以不用线索二叉树吗，那是肯定的。

谈线索二叉树之前你必须对二叉树的链式存储结构遍历非常了解。

如果不了解请先搞懂先，

我们知道二叉树的节点数据类型有如下几种设计孩子双亲节点，我就谈这一种设计。

孩子双亲那就说明这个节点数据保存了孩子和双亲的地址，可以立马找到当前节点的孩子和双亲，但是如果我想不用遍历就得到比如中序遍历后的当前节点的前序和后序节点。

那么我们在不改变比如我们当前节点类型的设计结构上，怎么做，才让我们可以轻松拿到节点的中序遍历后的前后驱节点呢。

这个时候线索二叉树就诞生了，我们肯定知道我们的二叉树数据类型肯定并且不是完全二叉树，也许很多二叉树节点的指针域都是空的，是不是浪费了，这个时候我们可以把这些空的指针利用起来。我们可以保存中序遍历后的前后驱节点。

我们这里是针对中序遍历的前后驱，并且设计的节点数据类型比较简单，仅仅是当前节点数据+ 孩子节点的地址指针，现在问题来了既然节点指针域既可以保存他的孩子节点，又可以保存线索也就是中序遍历的前或者后驱节点地址。

那么我们可以必须设计新节点的数据类型

//设计二叉树的节点数据类型
    typedef struct BiTree
    {
        //节点数据
        int data;
    
    //左孩子的指针变量
        struct BiTree* lChild, *rChild;
    
    int lTag, rTag; // 规则：0表示当前节点左指针域保存的是左孩子地址 1保存是当前节点的前驱节点线索
    
    }*BiTree;
    
    
    我们首先个约定：约定lTag这个变量取0和1并且是针对当前节点的左孩子指针变量，至于这个变量保存的是左孩子节点还是前驱节点，我们可以根据是 0 还是1  我们默认保存左孩子节点 这个时候标志lTag = 0,
    
    rTag这个是针对右指针 0表示存的是节点的右孩子节点   1表示存的是后驱节点
    
    
    下面上具体代码。我们采用的是递归算法线索化二叉树。也就是把空指针域里面填上线索的过程。

//中序遍历二叉树并线索化 root：保存了二叉树对象的根节点地址  
void InitThread(BiTree root)  
\{  
//开辟临时变量保存当前遍历的节点地址  
BiTree temp = root;

//判断二叉树是不是为空
    if(root != null)
    {
         //先递归调用自身线索化当前节点的左子树  由于是中序遍历
         InitThread(root->lChild);
    
         /*开始线索化当前节点*/
          先线索化当前节点前驱节点
         if(root->lChild == null)
         {
            //设置标志位  表明当前节点存的是线索而不是孩子节点地址
            root->lTag = 1;
    
            //开始真正线索化
            root->lChild = pre;     //根据中序遍历我们知道当前访问的节点就是其左孩子的前驱节点
         }
    
         //开始当前节点的后驱线索化
         if(pre != null && pre->rChild == null)
         {
              //开始设计标志为 表示当前右指针域存的是线索不是右孩子节点
              pre->rTag = 1;
    
              //后驱线索化真正开始
              pre->rChild = root; 
         }
    
        //递归右孩子线索化
        InitThread(root->rChild);
    }

\}  
“\`

[SouthEast]: /images/20220606/57a60e60301748ec900bc0ef85c92d9e.png