线索二叉树

Posted on | Post modified: | In
Words count in article: 1,099 | Reading time ≈ 4

-6天回归战场
-希望有个好成绩吧

线索二叉树基本概念
二叉树的遍历就是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到，二叉树结点的各种遍历序列。二叉树遍历的实质就是对一个非线性结构进行线性化操作，使在这个访问序列中每一个结点（除第一个和最后一个）都有一个直接前驱和直接后继。
传统的链式存储只能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。通过观察，我们发现在二叉链表表示的二叉树中存在大量的空指针，若利用这些空链域存放指向其直接前驱或后继的指针，便可以更方便地运用某些二叉树的操作算法。引入线索二叉树是为了加快查找结点前驱和后继的速度。

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

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

这里写图片描述
其中标志域的含义：
ltag=0 时lchild指向左子女；
ltag=1 时lchild指向前驱；
rtag=0 时rchild指向右子女；
rtag=1 时rchild指向后继；

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

1
2
3
4
5
typedef struct ThreadNode{
	ElemType data;                       //数据元素
	struct ThreadNode *lchild,*rchild;   //左、右孩子指针
	int ltag,rtag;                       //左右线索标志
}ThreadNode,*ThreadTree;

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InThread(ThreadTree &p,ThreadTree &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);       //递归，线索化右子树
	}
}

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

1
2
3
4
5
6
7
8
void CreateInThread(ThreadTree T){
	ThreadTree pre=NULL;
	if(T!=NULL){              //非空二叉树，线索化
		InThread(T,pre);      //线索化二叉树
		pre->rchild=NULL;     //处理遍历的最后一个结点
		pre->rtag=1;
	}
}

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

1
2
3
4
5
ThreadNode *Firstnode(ThreadNode *p){
	while(p->ltag=0)
		p=p->lchild;    //最左下结点
	return p;
}

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

1
2
3
4
5
6
ThreadNode *Nextnode(ThreadNode *p){
	if(p->rtag==0)                   
		return Firstnode(p->rchild);
	else //rtag==1直接返回后继线索
		return p->rchild;
}

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

1
2
3
4
void Inorder(ThreadNode *T){
	for(ThreadNode *p=Firstnode(T); p!=NULL; p=Nextnode(p))
		visit(p);
}

Thanks for your reward！