数据结构树3线索二叉树 [复制链接]

本篇主要讲述线索二叉树

从之前的学习中我们知道，对于遍历二叉树操作，实际上是将树这样一种非线性的数据结构转换为线性的数据结构，使得每一个结点在线性结构中有着唯一的直接前驱和直接后继，但是在图的结构中无法直接表示出直接前驱和直接后继，本篇讲述的线索二叉树的目的就是，如何尽可能多地去利用树中的空链域，使得部分空链域可以用于保存该结点的前驱后继。

非常容易想到的方法是，直接通过在结构体中增加两个地址变量，直接保存前后结点位置，但是该方法存储空间利用率过低，并不优，今天要学习的线索二叉树通过增加两个标志域，将空链域合理的利用起来，相当于给二叉树增加了n+1条线索，因此形象地称作“线索二叉树”。

线索二叉树的结点结构如下：

LTag==1or0?==1:lchild指向前驱==0：lchild指向左孩子

RTag==1or0?==1:rchild指向后继==0：rchild指向右孩子

这样的存储结构叫做线索链表，指向前驱后继的指针叫做线索，加上线索的二叉树称作线索二叉树，对二叉树进行某种遍历使其转换为线索二叉树的过程叫做线索化。线索工作方式及存储结构如上图。

Q1：如何设计算法找到结点的后继？

A：后继结点出现在终端结点上，当遇到终端结点被访问后下一个访问的结点就是后继结点，左子树遍历完毕的最后一个结点的后继为遍历右子树时第一个访问的结点。对于不同的遍历顺序，有着不同复杂程度的寻找办法，由于线索二叉树并不常用，我们主要以中序遍历为例。

Q2：如何设计算法找到结点的前驱？

A：与后继类似，最近一次遍历左子树时最后访问的结点为遍历右子树时最后访问结点的前驱。

存储结构：

typedefenumPointerTag{Link,Thread};//Link==0孩子Thread==1线索typedefstructBiThrNode{TElemTypedata;BiThrNode*lchild,*rchild;PointerTagLTag,RTag;//左右标志}BiThrNode;

顺带定义了一个enum类型，使得后续的代码更加容易理解

中序遍历线索化二叉树的算法：

Ⅰ遍历左子树到输出

Ⅱ检查该点有无合法后继，有后继直接输出

Ⅲ没有后继或后继为头结点走向rchild

intInOrderTraverse_Thr(BiThrNodeT,(*visit)(TElemTypee)){//T指向头结点，头结点的左链指向根结点//中序遍历二叉树T的非递归算法BiThrNode*p=T-lchild;while(p!=T)//空树或者遍历结束时p会回到T{while(p-LTag==Link)p=p-lchild;//如果是孩子指向，则去往孩子，此处将左子树完全遍历if(!visit(p-data))return0;//访问，输出while(p-RTag==Threadp-rchild!=T)//如果有后继，后继不为头结点{p=p-rchild;visit(p-data);//跳至后继并继续访问}p-rchild;//如果没有后继或者后继是头结点则走向下一步}}

中序线索化算法：

voidInThreading(BiThrNode*p,BiTNode*pre){//线索化用到的子函数，采用递归思想if(p){InThreading(p-lchild,pre);//左子树线索化,作用相当于一个循环，到了最左边的位置if(!p-lchild){p-LTag=Thread;p-lchild=pre;}//前驱线索if(!pre-rchild){pre-RTag=Thread;pre-rchild=p;}//后继线索pre=p;//pre保持为p的前驱InThreading(p-rchild,pre);}}

/*pre始终保持为上一个访问的位置*/

在其他数据结构书中，有的甚至已经不再讲解线索二叉树的问题，因此，线索二叉树不需学得过深，了解其思想就好。