数据结构与算法——线索二叉树

线索二叉树的引入

二叉树的结构特点会导致有大量的指针域空间的浪费，并且在二叉树的遍历时，每一次要想知道该结点的前驱和后继都需要进行一次遍历，这样会导致空间和时间上的浪费。因此，我们利用浪费的指针域，引入线索二叉树，同时解决上述两个问题。

线索二叉树的原理

初步想法是在二叉树中，我们利用没有指向孩子的指针域，使其指向该结点的前驱或后继。并且规定，原本指向左孩子的指针域负责指向前驱结点，原本指向右孩子的指针域负责指向后继结点。

为了方便记忆，我们可以把二叉树按照某种遍历次序想象成一个线性表，从左到右就是从前到后，方便记忆前驱和后继的指针位置。

但是，这样的方式会导致我们无法得知，在指针域中究竟指向的是该结点的孩子结点还是指向前驱或后继。为此，我们需要稍加修改结点的结构，在其中加入两个域，分别为 ltag 和 rtag，用于分辨上述问题。

数值	1	0
rtag	后继结点	右孩子结点
ltag	前驱结点	左孩子结点

线索存储结点的结构定义代码如下

typedef enum {Link,Thread} Pointertag;	//Link==0，表示指向左右孩子的指针；
										//Thread==1，表示指向前驱或后继
typedef struct BiThrnode
{
	TElemType data;		//数据结点
	struct BiThrnode *rchild, *lchild;		//左右孩子结点
	//左右标签
	PointerTag LTag;
	PointerTag RTag;
}

线索二叉树的线索化

线索化就是对二叉树以某种次序的遍历使其变成线索二叉树，其过程就是在遍历的过程中修改空白指针域的值

线索化的递归函数代码实现如下（以中序为例）

BiThrTree pre;		//全局变量，始终指向刚刚访问过的结点

void InThrreading(BiThrTree p)
{
	if(p)
	{
		InThrreading(p->lchild);
		if(!p->lchild)		//如果没有左孩子
		{
			p->LTag = Thread;		//左标签赋值为1
			p->lchild = pre;		//左指针指向前驱
		}
		if(!pre->rchild)		//如果前驱没有右孩子
        {
			pre->Rtag = Thread;		//右标签赋值为1
            pre->rchild = p;		//右指针指向后继（当前结点p）
		}
		pre = p;		//保持pre始终指向刚刚访问过的结点
		InThrreading(p->rchild);
	}
}

通过上述代码，我们不难发现，线索化的递归代码，与之前的中序遍历的递归代码结构完全相同，就只是改变了对结点进行的访问操作。

线索二叉树的遍历

既然提出了线索二叉树是为了解决二叉树的遍历问题，那么我们一起看看实现遍历的代码究竟是怎样的。

对线索二叉树的遍历，其实可以看成是对一个双向链表的遍历，我们使一个头结点指向线索二叉树的根结点。头结点的rchild指向树的根节点，lchild指向

线索二叉树的遍历代码

Status InOrderTraverse_Thr (BiThrTree T)	//T即为二叉树的头结点
{
	BiThrTree p;
    p = T->lchild;		//使p指向T的根节点
    while(p != T)		//p = T时，说明该二叉树是空树或遍历结束
    {
    	while(p->LTag == Link)   //说明结点有左孩子
        {
            p = p->lchild;	//p指向p的左孩子
            printf("%c",p->data);
        }
        while(p->RTag == Thread && p->rchild != T)		//结点没有右孩子，
            											//并且不是中序遍历最后一个结点
      	{
            p = p->rchild;		//p指向p的后继结点
            printf("%c", p->data);
        }
        p = p->rchild;
    }
    return OK;
}