数据结构篇——线索二叉树

一、引入

遍历二叉树是按一定规则将二叉树结点排成线性序列，得到先序、中序或后序序列，本质是对非线性结构线性化，使结点（除首尾）在线性序列中有唯一前驱和后继；但以二叉链表作存储结构时，只能获取结点左右孩子信息，无法直接得任一序列中的前驱和后继信息，该信息需在遍历动态过程中获取，所以我们将引入线索二叉树来保存遍历动态过程中得到的前驱和后继信息。

二、线索二叉树的基本概念

试做如下规定:若结点有左子树,则其lchild域指示其左孩子,否则令 Ichild域指示其前驱;若结点有右子树,则其rchild 域指示其右孩子,否则令rchild域指示其后继。为了避免混淆,尚需改变结点结构,增加两个标志域,其结点形式如图所示。

其中：LTag=0,lchild指示结点的左孩子；=1时，lchild指示结点的前驱。

RTag=0,rchild指示结点的右孩子；=1时，rchild指示结点的后继。

这样我们就能得到二叉树的二叉线索类型定义如下：

//二叉树的二叉线索存储表示
typedef struct BiThrNode{TElemType data;struct BiThrNode *lchild,*rchild;    //左右孩子的指针int LTag,RTag;    //左右标志
}BiTheNode,*BiThrThree;

以这种结点结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱和后继的指针,叫做线索。加上线索的二叉树称之为线索二叉树(Threaded Binary Tree)。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。
例如下图中(a)所示为中序线索二叉树,与其对应的中序线索链表如图5.16(b)所示。其中实线为指针(指向左、右子树),虚线为线索(指向前驱和后继)。

三、线索二叉树的构造与遍历

3.1、构造线索二叉树

线索二叉树构造的实质是将二叉链表中的空指针改为指向前驱或后继的线索,而前驱或后继的信息只有在遍历时才能得到,因此线索化的过程即为在遍历的过程中修改空指针的过程。
Tips：为了记下遍历过程中访问结点的先后关系,附设一个指针pre 始终指向刚刚访问过的结点,而指针p指向当前访问的结点,由此记录下遍历过程中访问结点的先后关系。

以结点p为根的子树中序线索化：

首先我们来判断指针p，如果p非空,左子树递归线索化。如果p的左孩子为空,则给p加上左线索,将其LTag置为1,让p的左孩子指针指向prc (前驱);否则将p的LTag置为0。然后我们来看pre，如果pre的右孩子为空,则给pre加上右线索,将其RTag置为1,让pre的右孩子指针指向p(后继);否则将pre的RTag置为0。之后将pre指向刚访问过的结点p,即Pre=p。最后右子树递归线索化。

代码描述：

void InThreading(BiThrTree p){//pre是全局变量，初始化时其右孩子指针为空，便于在树的最左结点建立线索。if(p){InThreading(p->lchild);    //左子树递归线索化if(!p->lchild){    //p的左孩子为空p->LTag=1;    //给p加上左线索p->lchild=pre;    //p的左孩子指向pre前驱}else {p->LTag=0;    }if(!pre->rchild){    //pre的右孩子为空pre->RTag=1;    //给pre加上右线索pre->rchild=p;    //pre的右孩子指向p后继}else{pre->RTag=0;}pre=p;    //保持pre指向p的前驱InThreading(pre->rchild);    //右子树递归线索化}
}

3.2、遍历线索二叉树

由于有了结点的前驱和后继信息,线索二叉树的遍历和在指定次序下查找结点的前驱和后继算法都变得简单。因此,若需经常查找结点在所遍历线性序列中的前驱和后继,则采用线索链表作为存储结构。

下面讨论在中序二叉树中如何查找结点的前驱与后继:
①查找p指针所指结点的前驱:

若p->LTag为1,则p的左链指示其前驱;
若p->LTag为0,则说明p有左子树,结点的前驱是遍历左子树时最后访问的一个结点(左子树中最右下的结点)。

②查找p指针所指结点的后继:

若P->RTag为1,则p的右链指示其后继,以上文中图5.16所示的中序线索树为例来看,结点b的后继为结点 *
若P->RTag为0,则说明p有右子树。根据中序遍历的规律可知,结点的后继应是遍历其右子树时访问的第一个结点,即右子树中最左下的结点。例如在找结点 * 的后继时,首先沿右指针找到其右子树的根结点 - ,然后顺其左指针往下直至其左标志为1的结点,即为结点 * 的后继,在图中是结点c。

由于有了结点的前驱和后继的信息,线索二叉树的遍历操作无需设栈,避免了频繁的进栈、出栈,因此在时间和空间上都较遍历二叉树节省。如果遍历某种次序的线索二叉树,则只要从该次序下的根结点出发,反复查找其在该次序下的后继,直到叶子结点。所以我们就能按照下面的步骤来进行线索二叉树的遍历啦（以中序线索二叉树的遍历为例）：

遍历步骤：

指针p指向根结点。
p为非空树或遍历未结束时，执行以下操作：
a、沿左孩子向下，到达最左下结点*p，它是中序的第一个结点；
b、访问*p；
c、沿右线索反复查找当前结点*p的后继结点并访问，直至右线索为0或者遍历结束；
d、转向p的右子树。

代码描述：

void InOrderTraverse_Thr(BiThrTree T){//T指向头结点，头结点的左链lchild指向根结点。//中序遍历的非递归算法，对每个元素直接输出p=T->lchild;    //p指向根结点while(p!=T){    //空树或遍历结束时p==Twhile(p->Ltag==0){    p=p->lchild;    //沿左孩子向下cout<<p->data;    //访问其左子树的结点}while(p->RTag==1&&p->rchild!=T){p=p->rchild;cout<<p->data;    //沿右线索访问后继结点}p=p->rchild;    //转向p的右子树}
}