线索二叉树

﹏ヽ暗。殇╰゛Y 2022-12-09 02:46 9阅读 0赞

## 一 概述 ##

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继。

一般的二叉树链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。前面提到，在含有n个结点的二叉树中，有n+1个空指针。这是因为每个叶子结点有2个空指针，每个度为1的结点有1个空指针，度为2的结点不存在空指针。如果令度为2的结点树为n2，度为1的结点数为n1，度为0即叶子结点数位n0，则树的空指针总数为2n0+n1，同时存在度为2的结点数(n2)和叶子结点数(n0)的关系为n0=n2+1，所以空指针总数为n0+n1+n2+1 = n+1。

此时我们可以利用这些空指针来存放指向其前驱或后继的指针，使得我们可以像遍历单链表那样方便地遍历二叉树。而线索二叉树正是为了加快查找结点前驱和后继的速度。

## 二 线索二叉树 ##

![20201130150004520.png][]

线索话过程为：如图如果一棵二叉树中，若无左子树，则将其左指针指向其前驱结点；若无右子树，则将右指针指向其后继结点。同时还需要增加两个标志域标识指针域是指向左（右）孩子还是指向前驱（后继）。

![20200921164215584.png][]

其中，标志域的含义如下：

<table> 
 <tbody> 
  <tr> 
   <td colspan="1">ltag</td> 
   <td>0</td> 
   <td>lchild域指示结点的左孩子</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>lchild域指示结点的前驱结点</td> 
  </tr> 
  <tr> 
   <td colspan="1">rtag</td> 
   <td>0</td> 
   <td>rchild域指示结点的右孩子</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>rchild域指示结点的后继结点</td> 
  </tr> 
 </tbody> 
</table>

线索二叉树的存储结构：

typedef struct ThreadNode{
        ElemType data;        //数据元素
        struct ThreadNode *lchild,*rchild;  //左，右孩子指针
        int ltag,rtag;        //左，右线索标志
    }ThreadNode,*ThreadTree;

以这种结点结构构成的二叉链表作为二叉树的存储结构，称为线索链表，其中指向结点前驱或后继的指针称为线索。加上线索化的二叉树称为线索二叉树。

[20201130150004520.png]: /images/20221123/e54e7269fcb142f98e937881ff4804ec.png
[20200921164215584.png]: /images/20221123/98297006ce5f4205a49cd780e9323477.png