「线索二叉树」【数据结构】线索二叉树（构造与遍历）

线索二叉树

主要内容

基本概念
构造线索二叉树
遍历线索二叉树

基本概念

遍历二叉树是对非线性结构结点的线性化过程，由此得到的遍历序列中，每个结点有且仅有一个前驱和后继（除了序列中的第一个和最后一个结点）。

原始二叉链表的结点结构仅包含数据元素信息和左右指针域，若在结点结构中增加前驱和后继的指针域，则该存储结构称为线索二叉树。

虽然可以直接增加两个指针域来实现这种结构，但这样会使结构的存储密度大大降低。（存储密度 = 数据元素本身占用的存储量 / 结点结构占用的存储量）

那我们应该怎么改善呢？

先来回顾一下https://blog.csdn.net/Ha1f_Awake/article/details/85010489#t5

要想利用空指针域来存放前驱、后继的地址，还需要将前驱、后继和左、右子树根结点区分开。因此我们新增两个标志域：LTag和RTag（整型），1表示有子树，0表示无子树。

1）当LTag = 0时，lchild域指示结点的左子树根结点；当LTag = 1时，lchild域指示结点在某个遍历序列中的前驱。

2）当RTag = 0时，rchild域指示结点的右子树根结点；当RTag = 1时，rchild域指示结点在某个遍历序列中的后继。

指向前驱、后继的指针称为线索。

typedef struct ThBinode
{
    Elemtype data;

    struct ThBinode *lchild, *rchild;

    int LTag, RTag;

} ThBinode, *ThBiTree;

构造线索二叉树

构造线索二叉树实质上是将二叉链表中的空指针域改为前驱、后继指针域。

又因为前驱、后继的信息只有在遍历的时候才能得到，所以线索化的过程就是在遍历的时候修改空指针的过程。

为了记下遍历过程中访问结点的先后关系，附设一个指针pre指向刚刚访问过的结点（即序列中的前一个结点），而指针p指向当前访问的结点。

/*--------以结点p为根的子树的中序线索化--------*/

void InThreading(ThBiTree p)
{
    if(p)
	{
		InThreading(p->lchild);		/*左子树递归线索化*/

		if(!p->lchild)				/*如果没有左子树*/
		{
			p->LTag = 1;			/*设置前驱*/
			p->lchild = pre;
		}

		else p->RTag = 0;			/*有左子树*/

		if(!pre->rchild)			/*如果没有右子树*/
		{
			pre->RTag = 1;			/*设置后继*/
			pre->rchild = p;
		}

		else pre->rchild = 0;

		pre = p;

		InThreading(p->rchild);		/*右子树递归线索化*/
	}
}

/*---------带头结点的二叉树的中序线索化--------*/

void InorderThreading(ThBiTree &tb, ThBiTree t)
{
	tb = new ThBinode;		/*建立头结点*/

	tb->LTag = 0;			/*头结点有左孩子，为根结点*/
	tb->Rtag = 1;			/*头结点无右孩子，后继线索为中序遍历的最后一个结点*/

	tb->rchild = tb;		/*初始化时后继为头结点本身*/

	if(!t) tb->lchild = tb;	/*若二叉树为空，左孩子也为头结点本身*/

	else
	{
		tb->lchild = t; pre = tb;	/*头结点的作用体现，统一根结点与其他结点的处理方式*/

		InThreading(t);				/*对二叉树中序线索化*/

		pre->RTag = 1;				/*线索化结束后，pre为二叉树的最右结点*/

		pre->rchild = tb;			/*使其右线索指向头结点*/
									
		tb->rchild = pre;			/*将头结点的后继从它本身改为最右结点*/
	}
}

遍历线索二叉树

由于有了结点的前驱和后继信息，线索二叉树的遍历和指定次序下查找结点的前驱和后继算法都变得简单。

线索二叉树的遍历不需要设栈，避免了频繁的进栈、出栈，因此在时间和空间上都较遍历二叉树节省。

因此，若需要经常查找结点在所遍历线性序列中的前驱和后继，则采用线索链表作为存储结构。

1）中序线索二叉树

1. 查找p的前驱：查左线索；若无左线索，结点的前驱是遍历左子树时访问的最后一个结点。

2. 查找p的后继：查右线索；若无右线索，结点的后继是遍历右子树时访问的第一个结点。

2）先序线索二叉树

1. 查找p的前驱：查左线索；若无左线索，结点的前驱是结点的双亲结点，或是先序遍历其双亲结点左子树时最后访问的结点。

2. 查找p的后继：查右线索；若无右线索，结点的后继必为结点的左子树（若存在）或右子树根结点。

3）后序线索二叉树

1. 查找p的前驱：查左线索；若无左线索，且无右线索时，结点的前驱是右子树根结点；若无左线索，但是有右线索时，结点的前驱是左子树根结点。

2. 查找p的后继，这种查找比较复杂，分4类情况讨论：

若p为二叉树的根结点，后继为空；
若p为右子树根结点，后继为双亲结点；
若p为左子树根结点，且无右兄弟，后继为双亲结点；
若p为左子树根结点，且有右兄弟，后继为后序遍历双亲结点右子树时访问的第一个结点。

由上述情况可知，在先序线索二叉树上找前驱和在后序线索二叉树上找后继都比较复杂。

遍历线索二叉树的时间复杂度为O(n)，与递归或非递归遍历二叉链表一样，但前者的空间复杂度为O(1)，而后者为O(n)，因为遍历线索二叉树不需要栈。

/*----------遍历中序线索二叉树----------*/

void InOrderTraverse(ThBiTree t)
{/*t指向线索二叉树的头结点，而头结点的左指针指向二叉树的根结点*/
	ThBinode *p = t->lchild;		/*使p指向根结点*/

	while(p != t)					/*若线索二叉树不为空或遍历未结束*/
	{
		while(p->LTag == 0) p=p->lchild;	/*沿左孩子往下，定位*/

		cout<<p->data;						/*访问左子树为空的结点*/

		while(p->RTag == 1 && p->rchild != t)	/*若有右线索，且右线索不为头结点*/
		{
			p = r->rchild;
			cout<<p->data;					/*沿右线索访问后继结点*/
		}

		p = p->rchild;				/*转向p的右子树*/
	}
}

【数据结构】线索二叉树（构造与遍历）