导读

本篇文章将会介绍线索二叉树的基本概念、二叉树的线索化、在线索二叉树中找前驱后继

线索二叉树

对于一个二叉树，我们可以对其进行遍历，遍历之后，会得到一个线性序列，此序列与线性表极为相似，即除了第一个和最后一个元素，每一个元素包含一个前驱和后继，那么对于任一一个结点，我们怎么去找到其前驱和后继呢？

有一个较为复杂的方法是，用指针q指向目标元素，用指针p进行遍历，并且用pre一直指向p的前一个元素

若p==q 则pre就为q的前驱

若pre==q 则p就为q的后继

如果引入线索二叉树，在原有二叉树结构：

typedef struct BiTNode{
	int data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;

的基础上，加入标签ltag和rtag：

typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild,*rchild;
	int ltag,rtag;
}ThreadNode,*ThreadTree; 

ltag==0时表示lchild指向该结点左孩子，rtag同理（右孩子）

ltag==1时表示lchild指向该结点前驱

rtag==1时表示rchild指向该结点后继

当然这是线索化之后的结果，如何线索化，亟待解决

二叉树线索化

三种遍历方式对应了三种线索二叉树，下面一个一个来说：

中序线索化：

可以把上面那个用pre，p，q找前驱后继的方法牵引到这里：

刚开始的时候，所有结点的ltag和rtag都是0

在中序遍历的基础上，把visit的内容进行修改就可以变成一个线索化函数：

void InThread(ThreadTree T,ThreadTree pre)
{
	if(T!=NULL)
	{
		InThread(T->lchild,pre);
	    if(T->lchild==NULL)
	    {
	    	T->lchild=pre;
	    	T->ltag=1;
		}
		if(pre!=NULL&&pre->rchild==NULL)
		{
			pre->rchild=T;
			pre->rtag=1;
		}
pre=T；
		InThread(T->rchild,pre);
	}
}

由此我们可以得到创建一个中序线索二叉树的完整代码：

void CreatInThread(ThreadTree T)
{
	ThreadTree pre=NULL;
	if(!T)
	{
		InThread(T,pre);
		if(pre->rchild==NULL)
		pre->rtag=1;
	}
}

先序与中序极为相似，但中间有一个地方极其容易漏掉：

 比如，上图当中，假设有一个时刻，pre指向2，q指向3，q的左孩子是空，所以让q的左孩子指向pre，但这之后q进入q的左孩子又会到达pre，形成了死循环，所以需要加入一个特殊的语句：

if(T->ltag==0)
        PreThread(T->lchild,pre);

得出代码：

 void PreThread(ThreadTree T,ThreadTree pre)
{
	if(T!=NULL)
	{
		if(T->lchild==NULL)
	    {
	    	T->lchild=pre;
	    	T->ltag=1;
		}
		if(pre!=NULL&&pre->rchild==NULL)
		{
			pre->rchild=T;
			pre->rtag=1;
		}
		pre=T;
		if(T->ltag==0)
		PreThread(T->lchild,pre);
		PreThread(T->rchild,pre);
	}
} 
void CreatPreThread(ThreadTree T)
{
	ThreadTree pre=NULL;
	if(!T)
	{
		PreThread(T,pre);
		if(pre->rchild==NULL)
		pre->rtag=1;
	}
}

后序就没有这个问题，与中序几乎一样，在此省略

为什么要线索化，不就是为了找前驱后继吗，所以拿到线索树之后，怎么去找也是重点：

在线索二叉树中找前驱后继

中序线索二叉树找中序后继：

如果p->ltag==1;右孩子即后继

如果p->rtag==0;

p肯定有右孩子，根据左根右，后继就是右孩子当中第一个被中序遍历的结点，如下：

ThreadTree FirstNode(ThreadTree T)
{
	while(T->lchild==0)T=T->lchild;
	return T;
} 

综上所述，找中序遍历的后继代码：

ThreadTree NextNode(ThreadTree T)
{
	if(T->rtag==0) return FirstNode(T->rchild);
	else return T->rchild;
}

由此，还可以得到中序线索树的中序遍历非递归算法：

void InOrderTraverse(ThreadTree T)
{
    ThreadTree p;
    for(p=FirstNode(T);p!=NULL;p=NextNode(p))
    visit(p);
 } 

再来看找中序前驱：

这个不再多说跟上边类比（可以推出逆向中序遍历的算法）

找p的最后一个访问结点、找中序前驱、逆向中序遍历代码依次如下：

//找以p为根的树中最后一个被访问的结点
ThreadTree LastNode(ThreadTree T)
{
	while(T->rtag==0)T=T->rchild;
	return T;
 }
//找中序遍历前驱
ThreadTree PreNode(ThreadTree T)
{
	if(T->ltag==0) return LastNode(T->lchild);
	else return T->lchild;
 } 
//进行逆向中序遍历：
void RevInOrderTraverse(ThreadTree T)
{
	ThreadTree p;
	for(p=LastNode(T);p!=NULL;p=LastNode(p))
	visit(p);
 } 

再看先序找先序后继：

rtag=1略

当p->rtag=0,一定有右孩子，如果有左孩子，那么左孩子就是后继，如果没左孩子，那么右孩子就是后继

再看后序找后序前驱：

ltag=1略

当p->ltag=0,一定有左孩子，如果有右孩子，那么右孩子就是前驱，如果没右孩子，那么左孩子就是前驱

再看先序找先序前驱：

ltag=1好说

但ltag=0的时候，单单用二叉链表就没办法找到了，但是如果用三叉链表（有指向父节点的指针）就可以了

1.如果能找到p的父节点，且p是左孩子，那么父节点就是其前驱

2.如果能找到p的父节点，且p是右孩子，兄弟结点是空的，那么父节点就是其前驱

3.如果能找到p的父节点，且p是右孩子，兄弟结点不是空的，那么兄弟结点当中先序遍历的最后一个结点就是p的前驱

4.如果找不到p的父节点，那么前驱为null

后序找后继与之相同，请自行分析

暑期编程PK赛 得CSDN机械键盘等精美礼品！