学习笔记-数据结构-树与二叉树（2024-04-23）

线索二叉树
传统的二叉链表存储仅能体现一种父子关系，不能直接得到节点在遍历中的前驱或后继。在含有n个节点的二叉树中，有n+1个空指针。这是因为每个叶节点都有2个空指针，每个度为1的节点都有1个空指针，空指针总数为2n0+n1，又因为n0=n2+1，所以空指针的总数为n0+n1+n2+1=n+1。由此设想利用这些空指针来指向其前驱或后继。
引入线索二叉树正是为了加快查找节点前驱和后继的速度。
规定：若无左子树，令lchild指向其前驱节点；若无右子树，令rchhild指向其后继节点，还需要增加两个标志域，以标识指针域指向左（右）孩子或前驱（后继）。

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

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树。

以中序线索二叉树的建立为例。附设指针pre指向刚刚访问过的节点，指针p指向正在访问的节点，即pre指向p的前驱。在中序遍历的过程中，检查p的左指针是否为空，若为空就将它指向pre；检查pre的右指针是否为空，若为空就将它指向p。
通过中序遍历对二叉树线索化的递归算法如下：

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
9
10
11
12
13
14
15
16
17
18
19

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

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