4.3.2 线索二叉树

二叉树结点的各种遍历序列，其实质是对一个非线性结构进行线性化操作，使在这个访问序列中每一个结点（除第一个和最后一个）都有一个直接前驱和直接后继。

传统的链式存储技能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继，通过观察，我们发现在二叉链表表示的二叉树中存在大量的空指针，若利用这些空链域存放指向其直接前驱或后继的指针，则可以更方便地运用某些二叉树操作算法，引入线索二叉树是为了加快查找结点前驱和后继的速度。

前面提到，在有N个结点的二叉树中，有N+1个空指针。这是因此每一个叶结点有2个空指针，而在每一个度为1的结点有1个空指针，总的空指针为2N0+N1，又有N0=N2+1，所以总的空指针为N0+N1+N2+1=N+1。

在二叉树线索化时，通常规定，若无左子树，另lchild指向其前驱结点；若无右子树，令rchild指向其后继结点。还需要整个两个标志域表明当前指针域所指对象是指向左（右）子结点还是直接前驱（后继）。

其中标志域含义如下：

ltag=0 lchild域指示结点的左孩子

ltag=1 lchild域指示结点的前驱

rtag=0 rchild域指示结点的右孩子

rtag=1 rchild域指示结点的后继

线索二叉树的存储结构描述如下：

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

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

对二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点左右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。

以中序线索二叉树的建立为例，指针pre指向中序遍历时上一个刚刚访问过的结点，用它来表示各结点的访问的前后关系。

通过中序遍历对二叉树线索化的递归算法如下：

void InThread(ThreadTree &p,Thread &pre){
//中序遍历对二叉树线索化的递归算法
	if(p!=null){
		inThread(p->lchild,pre);//递归，线索化左子树
		if(p->lchild==null){//左子树为空，建立前驱线索
			p->lchild=pre;
			p->ltag=1;
		}
		if(pre!=null&&pre->rchild==null){
			pre->rchild=p;//建立前驱结点的后继线索
			pre->rtag=1;
		}
		pre=p;//标记当前结点成为刚刚访问过的结点
		inThread(p->rchild,pre);//递归，线索化右子树
	}
}

通过中序遍历建立中序线索二叉树的主过程算法如下：

void CreateInThread(ThreadTree T){
	ThreadTree pre=null; 
	if(T!=null){
		inThread(T,pre);//非空二叉树，线索化
		pre->rchild=null;//处理遍历的最后一个结点
		pre->rtag=1;
	}
}

有时为了方便，仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，并令其lchild域的指针指向二叉树的根结点其rchild域的指针指向中序遍历时访问的最后一个结点；反之，令二叉树中序序列的第一个结点的lchild域的指针和最后一个结点rchild域的指针均指向头结点。这好比为二叉树建立一个双向线索链表，既可以从第一个结点起顺后继进行遍历，也可从最后一个结点其顺前驱进行遍历。

3.线索二叉树的遍历

中序线索化二叉树主要是为了访问运算服务的，这种遍历不再需要借助栈，因为它的结点中隐含了线索二叉树的前驱和后继信息。利用线索二叉树，可以实现二叉树遍历和非递归算法。不含头结点的线索二叉树的遍历算法如下： 1）求中序线索二叉树中中序序列下的第一个结点

ThreadNode *Firstnode(ThreadNode *p){
	while(p->ltag==0)
		p=p-lchild;//最左下结点（不一定是叶结点）
	return p;
}

2）求中序线索二叉树中结点P在中序序列下的后继结点

ThreadNode *Nextnode(ThreadNode *p){
	if(p->ltag==0)
		return FirtNode(p->rchild);
	else
		return  p-rchild;//rtag==1直接返回后继线索
}

3）利用上面两个算法，可以写出不含头结点的中序线索二叉树的中序遍历的算法；

void inorder(ThreadNode *T){
	for(ThreadNode *p=FirstNode(T);p!=Null;p=Nextnode(p))
		visit(p);
}