RobbEr's Blog

Welcome

数据结构-线索二叉树

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 2.1k 阅读时长 ≈ 2 分钟

以下文章结合Wikipedia，简Cloud的简书以及Nice小夫的知乎专栏加上自己的一些修改

简介

什么是线索二叉树？

对一棵二叉树中所有节点的空指针域按照某种遍历方式加线索的过程叫作线索化，被线索化了的二叉树称为线索二叉树

为什么需要线索二叉树？

知道了“前驱”和“后继”信息，就可以把二叉树看作一个链表结构，从而可以像遍历链表那样来遍历二叉树，进而提高效率。

线索化二叉树原理

遍历二叉树的其实就是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列、中序序列或后序序列。这些线性序列中的每一个元素都有且仅有一个前驱结点和后继结点

但是当我们希望得到二叉树中某一个结点的前驱或者后继结点时，普通的二叉树是无法直接得到的，只能通过遍历一次二叉树得到。每当涉及到求解前驱或者后继就需要将二叉树遍历一次，非常不方便

于是是否能够改变原有的结构，将结点的前驱和后继的信息存储进来

对于一个有n个结点的二叉链表，每个节点都有指向左右孩子的两个指针域，一共有2n个指针域。而除了根节点以外每一个节点都有一个指针从它的父节点指向它，所以一共使用了N-1个指针，也就是存在2n-(n-1)=n+1个空指针域

这些指针域只是白白的浪费空间。因此, 可以用空链域来存放结点的前驱和后继。线索二叉树就是利用n+1个空链域来存放结点的前驱和后继结点的信息

如何线索化二叉树

这里列举了中序线索二叉树的方法，及之后线索化操作也是以中序的方式进行

一个二叉树通过如下的方法“串起来”：

所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继，所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱

用图的方法展现一下：

此图的直接意思是让你看到左孩子空，就会想到直接前驱；右孩子空，就会想到直接后继

线索二叉树的结构

  1. 如果 ltag=0，表示指向节点的左孩子。如果 ltag=1，则表示 lchild 为线索，指向节点的直接前驱
  2. 如果 rtag=0，表示指向节点的右孩子。如果 rtag=1，则表示 rchild 为线索，指向节点的直接后继

线索二叉树的定义如下

1
2
3
4
5
typedef struct TBNode {
    TElemType data;                         //结点数据
    struct TBNode *lchild, *rchild;         //左右孩子指针
    int ltag, rtag;                         //左右标志
}TBNode;

线索化实现

线索化算法

约定：

  1. 指针 pre 指向当前正在访问的节点
  2. pre 指向 p 的前驱节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void InThread(TBNode* p, TBNode*& pre)
{
    if(p)
        InThread(p->lchild, pre); //递归，左子树线索化
    if(!p->lchild)
    {
        p->lchild = pre;
        p->ltag = 1;
    }
    if(pre && pre->rchild)
    {//建立前驱节点的后继线索
        pre->rchild = p;
        pre->rtag = 1;
    }
    //pre指向当前的p，作为p将要指向的下一个节点的前驱节点提示指针
    pre = p;
    InThread(p->rchild, pre);
}

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

1
2
3
4
5
6
7
8
9
10
void createInThread(TBNode *root)
{
	TBNode *pre=NULL; //前驱节点指针
	if (root!=NULL)
	{
		InThread(root,pre);
		pre->rchild=NULL;   //非空二叉树线索化
		pre->rtag=1;        //处理中序最后一个节点
	}
}

遍历中序线索二叉树

求以p为根的中序线索二叉树中，中序序列下的第一个节点

1
2
3
4
5
6
7
8
TBNode *First(TBNode *p)
{
	while (p->ltag=0) //表示有左孩子（左孩子不为空）
	{
		return First(p->rchild);
	}
	return p;
}

求在中序线索二叉树中，节点p在中序下的后继节点。

1
2
3
4
5
6
7
8
9
10
11
TBNode *Next(TBNode *p)
{
	if (p->rtag==0) //表示有右孩子（右孩子不为空）
	{
		return First(p->rchild);
	}
	else
	{
		return p->rchild; //rtag==1,直接返回后继线索
	}
}

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

1
2
3
4
5
6
7
void Inorder(TBNode *root)
{
	for (TBNode *p=First(root) ; p!=NULL ; p=Next(p))
	{
		Visit(p); //Visit()是已经定义的访问p所指节点的函数
	}
}

先序和后序线索二叉树同理