如何将线索二叉树的中序线索化操作改写成长尾？

本文共计2210个文字，预计阅读时间需要9分钟。

为什么研究二叉搜索树？

当我们用二叉链表作为二叉树的存储结构时，可以很方便地找到某个节点的左右孩子；但在某些情况下，无法直接找到节点在某种遍历顺序序列中的前驱和后继。

为什么要研究线索二叉树？

当我们用二叉链表作为二叉树的存储结构时，可以很方便地找到某个结点的左右孩子；但一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点。

利用二叉链表中的空指针域：

如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某结点的右孩子为空，则将空的右孩子指针域改为指向其后继。

——这种改变指向的指针称为线索，加上了线索的二叉树称为线索二叉树（Threaded Binary Tree）。

对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化。

为区分lchild和rchild指针到底是指向孩子的指针，还是指向前驱或者后继的指针，对二叉链表中每个结点增设两个标志域LTag和RTag，并约定：

LTag=0,lchild指向该结点的左孩子；

LTag=1，lchild指向该结点的前驱；

RTag=0,rchild指向该结点的右孩子；

RTag=1，rchild指向该结点的后继。

线索二叉树的目的，是为了直观的表示出某结点的前驱和后继。如果每个结点的前驱或后继都能确定，则对二叉树的遍历就会变得非常简单，一条循环语句即可完成：

for (p=First(T);p!=NULL;p=succ(p))

Visit(p);

二叉链表中，直观的表示出了某结点左右孩子的信息。为了将前驱和后继的信息也表示出来，做如下的规定：

若某结点左指针为空，则令其指向其前驱；若某结点右指针为空，则令其指向其后继。

为区分出是左右孩子还是前驱后继，或者说，为区分出是指针还是线索，结点改变为5个域：除原来的data和lchild、rchild外，再增加ltag(左标志)和rtag(右标志)。并规定ltag=0，指向左孩子；ltag=1，指向前驱。rtag=0，指向右孩子，rtag=1，指向后继。

在线索树上进行遍历，只要先找到序列中的第一个结点，然后依次找结点后继直到后继为空为止。

typedef enum PointerThr { Link,Thread }PointerThr;//Link==0:指针，Thread==1:线索 typedef struct BiThrNode { TElemType data; struct BiThrNode *lchild,*rchild; PointerThr LTag,RTag; }BiThrNode,*BiThrTree;

手动模拟线索二叉树（中序）

中序遍历为DGBAECF

增设一个头结点：

LTag=0,lchild指向根结点，RTag=1,rchild指向遍历序列中最后一个结点，遍历序列中第一个结点的lc域和最后一个结点的rc域都指向头结点。

建立中序的线索链表

中序线索化的过程，其实就是在中序遍历的过程中修改空的指针域。问题的关键就是设置另外的一个指针pre，使其始终指向当前结点，或者说p所指向结点的前驱。这样，当p的左指针为空时，将其值修改为pre；而当pre所指的右指针为空时，将其值修改为p即可。

算法设计：中序线索化

中序遍历线索化的递归函数如下：

BiThrTree pre;//全局变量，始终指向刚刚访问过的结点 void InThreading(BiThrTree p) { if(p) { InThreading(p->lchild);//递归左子树线索化 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); } }

if(!p->lchild)表示如果某结点的左指针域为空，因为其前驱结点刚刚访问过，赋值给了pre，所以可以将pre赋值给p->lchild,并修改p->LTag=Thread(也就是定义为1)以完成前驱结点的线索化。

后继比较麻烦，因为此时p结点的后继还没有访问到，因此只能对它的前驱结点pre的右指针做判断，if(!pre->rchild)表示如果为空，则p就是pre的后继，于是pre->rchild=p，并且设置pre->RTag=Thread,完成后继结点的线索化。

完成前驱和后继的判断后，别忘记将当前结点p赋给pre，以便下一次使用。

在二叉树线索链表上添加一个头结点，并令其lchild域的指针指向二叉树的根结点（图中的①），其rchild域的指针指向中序遍历的最后一个结点（图中②）。反之，令二叉树的中序序列中的第一个结点中，lchild域指针和最后一个结点的rchild域指针均指向头结点（图中③和④）。这样定义的好处就是我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

//T指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的最后一个结点 Status InOrderThreading(BiThrTree *Thrt,BiThrTree T) { (*Thrt)=(BiThrTree)malloc(sizeof(BiThrNode)); if(!(*Thrt)) exit(OVERFLOW); (*Thrt)->LTag=Link;//Thrt->LTag=0; (*Thrt)->RTag=Thread;//Thrt->RTag=1; (*Thrt)->rchild=*Thrt; if(!T) (*Thrt)->lchild=(*Thrt); else { (*Thrt)->lchild=T; pre=(*Thrt); //线索化 InThreading(T); pre->rchild=(*Thrt); pre->RTag=Thread; (*Thrt)->rchild=pre; } return OK; }

如何找第一个结点

中序序列第一个结点：从根开始，向左走到尽头。

BiThrTree First(BiThrTree p) { if(!p) return NULL; while(p->LTag==Link) p=p->lchild; return p; }

如何找每个结点的后继

若p->RTag为线索，则后继为p->rchild

若p->RTag为指针，说明p有右子树，因中序遍历的顺序为左根右，将p看作根，后继为其右子树中序序列的第一个结点。

向右走一步，再向左走到尽头。

BiThrTree succ(BiThrTree p) { if(p->RTag==Thread) return p->rchild; p=p->rchild; while(p->LTag==Link) p=p->lchild; return p; }

如何找最后一个结点

中序序列的最后一个结点：从根开始，向右走到尽头

直接取头结点的rchild

BiThrTree Last(BiThrTree Thrt) { return Thrt->rchild; }

如何找每个结点的前驱

若p->LTag为线索，则前导为p->lchild

若p->LTag为指针，说明p有左子树，中序遍历的顺序为左根右，将p看作根，前导为其左子树中序序列的最后一个结点。

向左走一步，再向右走到尽头。

BiThrTree prec(BiThrTree p) { if(p->LTag==Thread) return p->lchild; p=p->lchild; while(p->RTag==Link) p=p->rchild; return p; }

代码实现

#include<stdio.h> #include<stdlib.h> #define OVERFLOW -2 #define OK 1 typedef enum PointerTag {Link,Thread} PointerTag;//Link==0，指针 Thread==1,线索 typedef char TElemType; typedef int Status; typedef struct BiThrNode { TElemType data; struct BiThrNode *lchild,*rchild; PointerTag LTag,RTag; }BiThrNode,*BiThrTree; BiThrTree pre; void InThreading(BiThrTree); Status CreatBiTree(BiThrTree *T) { char ch; ch=getchar(); if(ch=='#') *T=NULL; else { (*T)=(BiThrNode*)malloc(sizeof(BiThrNode)); if(!*T) exit(OVERFLOW); (*T)->data=ch; (*T)->LTag=Link; (*T)->RTag=Link; CreatBiTree(&(*T)->lchild); CreatBiTree(&(*T)->rchild); } return OK; } Status InOrderTravese(BiThrTree T,Status (*visit)(TElemType e)) { if(T) { InOrderTravese(T->lchild,visit); (*visit)(T->data); InOrderTravese(T->rchild,visit); } return OK; } Status visit(TElemType e) { printf("%c\t",e); return OK; } Status InOrderThreading(BiThrTree *Thrt,BiThrTree T) { (*Thrt)=(BiThrTree)malloc(sizeof(BiThrNode)); if(!(*Thrt)) exit(OVERFLOW); (*Thrt)->LTag=Link;//Thrt->LTag=0; (*Thrt)->RTag=Thread;//Thrt->RTag=1; (*Thrt)->rchild=(*Thrt); if(!T) (*Thrt)->lchild=(*Thrt); else { (*Thrt)->lchild=T; pre=(*Thrt); //线索化 InThreading(T); pre->rchild=(*Thrt); pre->RTag=Thread; (*Thrt)->rchild=pre; } return OK; } void InThreading(BiThrTree p) { if(p) { InThreading(p->lchild); if(!p->lchild) { p->LTag=Thread; p->lchild=pre; } if(!pre->rchild) { pre->RTag=Thread; pre->rchild=p; } pre=p; InThreading(p->rchild); } } BiThrTree First(BiThrTree p) { if(!p) return NULL; while(p->LTag==Link) p=p->lchild; return p; } BiThrTree succ(BiThrTree p) { if(p->RTag==Thread) return p->rchild; p=p->rchild; while(p->LTag==Link) p=p->lchild; return p; } BiThrTree prec(BiThrTree p) { if(p->LTag==Thread) return p->lchild; p=p->lchild; while(p->RTag==Link) p=p->rchild; return p; } BiThrTree last(BiThrTree Thrt) { return Thrt->rchild; } int main() { BiThrTree T,Thrt,p; char ch; printf("请输入一个二叉链表:"); CreatBiTree(&T); printf("中序遍历后的二叉链表为:"); InOrderTravese(T,visit); printf("\n"); printf("中序线索化的二叉链表为:"); InOrderThreading(&Thrt,T); for(p=First(T);p!=Thrt&&p;p=succ(p)) printf("%c",p->data); putchar('\n'); return 0; }