线索二叉树

线索二叉树

线索二叉树的结点定义：

1
2
3
4
5
6
7
typedef struct TBTNode
{
	char data;
	int ltag,rtaghy;
	struct TBTNode *lchild;
	struct TBTNode *rchild;
}TBTNode;

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void InThread(TBTNode *p,TBTNode *&pre)  //p指向根结点
{
	if(p!=NULL)
	{
		InThread(p->lchild,pre); //pre指针一直指向p指针指向的结点的前驱结点
		if(p->lchild==NULL)
		{
			p->lchild=pre; //左指针指向前驱结点，
			p->ltag=1;  //且将ltag设为1
		}
		if(pre!=NULL&&pre->rchild==NULL)
		{
			pre->rchild=p;  //右指针指向后继结点，
			pre->rtag=1;  //且将rtag设为1
		}
		pre=p; //p结点的要指向后继结点了，所以要将pre指向p，让他跟上来，这一句话要重点注意
		p=p->rchild;  //左子树全部访问完，开始访问右子树
		InThread(p,pre); //递归，右子树线索化
	}
}

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

1
2
3
4
5
6
7
8
9
10
11
void createInThread(TBTNode *root)
{
	TBTNode *pre=NULL;
	if(root!=NULL)
	{
		InThread(root,pre);
		pre->rchild=NULL;
		pre->rtag=1;
	}
}

以p为根的中序线索二叉树中，中序序列下的第一个结点的算法：

1
2
3
4
5
6
TBTNode *First(TBTNode *p)
{
	while(p->ltag=0)
		p=p->lchild;
	return p;
}

在中序线索二叉树中，结点p在中序下的后继结点的算法：

1
2
3
4
5
6
7
8
TBTNode *Next(TBTNode *p)
{
	if(p->ltag==0)
		return First(p->rchild);
	else
		return p->rchild;
}

中序线索二叉树上执行中序遍历的算法：

1
2
3
4
5
void Inorder(TBTNode *root)
{
	for(TBTNode *p=First(root);p!=NULL;p=Next(p))
		Visit(p);
}

通过前序遍历的二叉树线索化递归算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void preThread(TBTNode *p,TBTNode *&pre)
{
	if(p!=NULL)
	{
		if(p->lChild==NULL)
		{
			p->lChild=pre;
			p->pre=1;
		}
		if(pre !=NULL&&pre->rChild ==NULL)
		{
			pre->rChild=p;
			pre->rTag=1;
		}
		pre=p;
		if(p->lTag==0)  //注意
			preThread(p->lChild,pre);
		if(p->rTag==0)
			preThread(p->rChild,pre);
	}
}

在前序线索二叉树上的遍历操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void preOrder(TBTNode *tbt)
{
	if(tbt !=NULL)
	{
		TBTNode *p=tbt;
		while(p!=NULL)
		{
			while(p->lTag==0)
			{
				Visit(p);
				p=p->lChild;
			}
			Visit(p);
			p=p->rChild;
		}
	}
}

通过后序遍历的二叉树线索化递归算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void postThread(TBTNode *p,TBTNode *&pre)
{
	if(p!=NULL)
	{
		postThread(p->lChild,pre);
		postThread(p->rChild,pre);
		if(p->lChild==NULL)
		{
			p->lChild=pre;
			p->pre=1;
		}
		if(pre !=NULL&&pre->rChild ==NULL)
		{
			pre->rChild=p;
			pre->rTag=1;
		}
		pre=p;			
	}
}