【数据结构】C语言实现线索二叉树

C语言实现线索二叉树

导读

大家好，很高兴又和大家见面啦！！！

在前面的内容中我们认识了线索二叉树，并通过C语言实现了二叉树的三种线索化。

不过我相信肯定还是有朋友不太理解为什么要有线索二叉树，如果只是需要获取一个二叉树的遍历序列，我们直接对二叉树进行遍历不就好了吗？何必多此一举呢？

对于这个问题，我的个人理解是——线索二叉树不仅降低了空间的消耗，而且还提升了遍历的速度。

从空间消耗上来看：

传统的二叉树遍历是要么通过递归、要么通过栈实现的。不管是递归还是栈，在内存空间上都是有一定消耗的：

递归中的每一次递进都会开辟一个函数栈帧
在栈中每一次入栈都需要消耗一个结点的空间

在线索二叉树中，同样会在每个结点新增一个标志域：

每个标志只需要消耗1字节的空间。

以一个结点的空间消耗进行比较我们不难发现这三者的空间消耗的关系为：

那现在问题来了，线索二叉树是否真正的做到了提升遍历的效率呢？

在今天的内容中我们将会介绍线索二叉树是如何完成遍历的以及通过C语言实现一棵线索二叉树，并对三种遍历方式的性能进行测试。今天的内容干货满满，话不多说，我们一起进入今天的内容吧！！！

一、线索二叉树的遍历

与传统的二叉树不同，在线索二叉树中，度为0和度为1的结点会存放其前驱和后继结点的信息，以中序线索二叉树为例：

【数据结构】C语言实现线索二叉树_结点_03

以结点7为例，结点4为其前驱结点，节点2为其后继结点。因此我们找到了结点7，那我们就能够快速的找到结点4和结点2。

那我们在进行遍历时应该如何才能快速的找到每一个结点呢？

首先我们需要明确一个点：

中序二叉树中最左侧的结点一定是中序遍历序列的起点
中序二叉树中最右侧的结点一定是中序遍历序列的终点

可能有朋友不太理解这个点，我们还是以上图的二叉树为例来说明。

图示的二叉树的中序遍历序列为：

代码语言：javascript代码运行次数：0运行复制

6->4->7->2->1->3->5->8

可以看到在该遍历序列中，结点6为序列起点，结点8为序列终点。

会得到这个序列的原因是因为中序遍历是以 左->根->右 的顺序完成的遍历，所以对于一棵二叉树而言，其中序序列的起点一定在左子树，终点一定在右子树。

如何获取遍历序列在前面的内容中有详细的介绍，有需要的朋友可以回顾——【数据结构】C语言实现二叉树的遍历这里我就不再赘述。

1.1 遍历逻辑

对于一个遍历序列而言，由于该序列中的元素在逻辑上是一个线性结构：

除了首元素外，每一个元素都有一个唯一的直接前驱
除了尾元素外，每一个元素都有一个唯一的直接后继

因此我们要想获取完整的遍历序列，我们就需要先找到序列的起点，之后借助前驱与后继指针来找到完整的遍历序列。

1.2 序列起点的获取

不同的线索二叉树有着不同的起点，有遍历的形式我们可以得到序列起点与终点的信息：

先序线索二叉树：
遍历顺序：根->左->右
序列起点：二叉树的根结点
序列终点：二叉树的右子树
中序线索二叉树：
遍历顺序：左->根->右
序列起点：二叉树的左子树
序列终点：二叉树的右子树
后序线索二叉树：
遍历顺序：左->右->根
序列起点：二叉树的左子树
序列终点：二叉树的根结点

因此对于任意一棵二叉树而言，我们要获取其遍历序列的起点，我们就需要获取其根结点与左子树。为了帮助大家更好的理解，我们会详细介绍中序线索二叉树的遍历过程。

1.3 序列前驱与后继

在中序线索二叉树中，对于给定的任一结点，我们都可以通过找其左子树获取该结点的前驱，找其右子树获取该结点的后继：

【数据结构】C语言实现线索二叉树_线索化_04

就比如在这棵二叉树中，如果给我们的结点是4，此时我们会发现其左右孩子都是存在的，这时我们就可以通过左孩子找前驱，右孩子找后继：

找前驱：
结点4 的左孩子为结点6，接下来我们根据结点6继续找前驱：
结点6的左孩子为线索，且线索为NULL，因此结点6为序列的首元素；
结点6的右孩子为线索，且线索指向结点4，因此结点6为结点4的前驱结点；
找后继：
结点4的右孩子为结点7，接下来我们根据结点7继续找后继：
结点7的左孩子为线索，且线索指向结点4，因此结点7为结点4的后继结点

这时有朋友可能会有疑问，为什么找后继是找右孩子的左孩子？

这个问题就是涉及到二叉树的遍历问题，我们通过一张图来进行说明：

【数据结构】C语言实现线索二叉树_线索化_05

从上图的步骤中我们不难得出结论：

一个结点的前驱结点一定是其左子树最右侧的右孩子
一个结点的后继结点一定是其右子树最左侧的左孩子

因此我们在寻找结点B的前驱结点A与后继结点C时，如果结点B没有前驱与后继的线索，那我们就可以通过等价替换的方式查找：

寻找结点A的后继，如果为B，则结点A为结点B的前驱
寻找结点C的前驱，如果为B，则结点C为结点B的后继

这里有点绕，大家可以结合上图的步骤去理解。

1.4 遍历步骤

当我们要对一棵线索二叉树进行遍历获取其遍历序列时，整个步骤可以分为3步完成：

找到二叉树的最左侧结点，确定遍历序列的起点
找到起点的后继结点：
存在右子树：找到右子树的最左侧结点
没有右子树：线索指向的结点即为后继结点
找到所有结点的后继结点

当我们从任一结点开始进行遍历时，对于起点的确立我们则需要根据该结点的左子树完成：

存在左子树，继续往左子树寻找
没有左子树，找到该结点的前驱结点，继续从前驱结点的左子树寻找

当我们寻找到某个结点的前驱结点为已经线索化，且为空指针时，则说明我们找到了序列的起点；

1.5 C语言实现

确定了整个遍历的步骤后，接下来我们就可以通过代码实现线索二叉树的遍历了。

整个过程分为三步：

找起点
找后继
找到所有结点的后继结点

1.5.1 找起点

找起点的逻辑很简单，我们需要通过结点的左孩子与线索标记完成：

未被线索化，继续找左孩子的左子树
已被线索化，继续找前驱结点的左子树

当找到以及线索化且没有前驱结点的结点时，就说明我们找到了起点，代码如下所示：

代码语言：javascript代码运行次数：0运行复制

ThreadNode* GetFirstNode(ThreadNode* p) {
	while (p->ltag == 0 || p->lchild) {
		p = p->lchild;
	}
	return p;
}

该实现的方式对于任意一个线索二叉树上的结点都是适用的，此时我们就不会拘泥于一定要从根结点开始；

1.5.2 找后继

后继结点的寻找逻辑也很简单：

为被线索化，则找右子树的最左侧结点
已被线索化，则线索指针的指向结点为该结点的后继结点

那么，我们应该如何找一棵二叉树的最左侧结点呢？

所谓的最左侧的结点，即该结点的左子树为NULL，那也就是说，该结点的左孩子一定完成了线索化，因此我们只需要找到该子树的左孩子中第一个被线索化的结点即可，代码如下所示：

代码语言：javascript代码运行次数：0运行复制

ThreadNode* GetLeftNode(ThreadNode* p) {
	while (p->ltag == 0) {
		p = p->lchild;
	}
	return p;
}

那么整个找后继的过程就应该是：

代码语言：javascript代码运行次数：0运行复制

ThreadNode* GetPostNode(ThreadNode* p) {
	return p->rtag == 0 ? GetLeftNode(p->rchild) : p->rchild;
}

看到找最左侧的结点与找起点的代码，不知道有没有朋友会有疑问——为什么这两个代码这么像，能不能将二者合并为同一个代码？

要合并二者，我们首先需要知道二者的区别在哪？

在找起点的代码中，我们是通过两个条件来判断是否找到了指定的结点：

结点的左孩子是否被线索化
线索化后的前驱结点是否为空

而在找最左侧结点的代码中，我们是通过一个条件来判断是否找到了指定的结点：

结点的左孩子是否被线索化

可以看到，二者的区别就在于对找到结点的前驱结点的判断：

前者是传入的结点为任意结点，因此需要判断找到的结点的前驱是否为空
后者传入的结点在该子树中为子树的根结点，因此当找到被线索化的第一个结点时，该结点一定是该子树中的最左侧结点

也就是说，如果第一种情况传入的也是根结点，那么我们就可以直接采用后者的找最左侧结点的代码；

如果要采用前者的找起点的代码，那么我们就可以通过传入前驱结点来完成结点的判断，如下所示：

代码语言：javascript代码运行次数：0运行复制

ThreadNode* GetFirstLeftNode(ThreadNode* p, ThreadNode* pre) {
	while (p->ltag == 0 || p->lchild != pre) {
		p = p->lchild;
	}
	return p;
}

此时，对于传入的任一结点，我们都可以找到序列的起点，而对于传入以该结点为根结点的子树中的任一结点，我们都能够找到该子树的最左侧结点。

1.5.3 查找所有结点的后继结点

既然要查找所有结点的后继结点，那我们最开始查找的结点一定是序列的起点，之后才能够继续往后查找，对应代码如下所示：

代码语言：javascript代码运行次数：0运行复制

void ThreadOrder(ThreadTree t) {
	for (ThreadNode* p = GetFirstLeftNode(t, NULL); p; p = GetPostNode(p)) {
		visit_Node(p);
	}
}

1.5.4 完整代码

下面我们就来看一下中序二叉树遍历的完整代码：

代码语言：javascript代码运行次数：0运行复制

//获取最左侧结点
ThreadNode* GetFirstLeftNode(ThreadNode* p, ThreadNode* pre) {
	while (p->ltag == 0 || p->lchild != pre) {
		p = p->lchild;
	}
	return p;
}
//获取后继结点
ThreadNode* GetPostNode(ThreadNode* p) {
	return p->rtag == 0 ? GetFirstLeftNode(p->rchild, p) : p->rchild;
}
//线索二叉树的遍历
void ThreadOrder(ThreadTree t) {
	for (ThreadNode* p = GetFirstLeftNode(t, NULL); p; p = GetPostNode(p)) {
		visit_Node(p);
		printf("p->data = %d\np->ltag = %d\np->rtag = %d\n", p->data, p->ltag, p->rtag);
	}
}

在找后继中，当该结点的右孩子未被线索化时，传入的参数的含义如下：

指针 p->rchild 为查找子树的根结点
指针 p 为查找的子树最左侧结点的前驱结点

当然，如果传入的结点都是根结点的话，我们在找最左侧的结点时，也是不需要传入前驱结点作为判断的，这个就看自己的实际需求了。我个人倾向于当前展示的代码实现，因此后续的内容中我们也会以该代码进行测试。

二、普通二叉树转化线索二叉树

在普通二叉树的线索化中，我们需要注意普通二叉树与线索二叉树的区别：

普通二叉树没有标志域
线索二叉树有标志域

正因为结点的不同，当我们获取到一个普通二叉树时，我们是无法直接将其线索化。

为了完成线索化，我们首先需要做的是将普通二叉树转化为线索二叉树。这个转化的过程我们可以通过先序遍历的方式实现：

代码语言：javascript代码运行次数：0运行复制

ThreadTree BiTree_to_ThreadTree(BT t) {
	if (t == NULL) {
		return NULL;
	}
	ThreadNode* root = (ThreadNode*)calloc(1, sizeof(ThreadNode));
	assert(root);
	root->data = t->data;
	root->lchild = BiTree_to_ThreadTree(t->lchild);
	root->rchild = BiTree_to_ThreadTree(t->rchild);
	return root;
}

我们从根结点开始，依次对左子树与右子树进行转化，具体的实现逻辑比较简单，大家直接看代码理解即可，这里就不再赘述；

三、二叉树的线索化

当我们完成二叉树的转化后，我们就可以对新获取的线索二叉树实现线索化了，这里我们同样以中序线索化为例：

代码语言：javascript代码运行次数：0运行复制

//中序线索二叉树的创建
void CreateInThread(ThreadTree t) {
	ThreadNode* pre = NULL;
	InThread(t, &pre);
	pre->rchild = NULL;
	pre->rtag = 1;
}
//中序线索二叉树
void InThread(ThreadNode* p, ThreadNode** pre) {
	if (p) {
		InThread(p->lchild, pre);
		Thread(p, pre);
		InThread(p->rchild, pre);
	}
}
//根结点线索化
void Thread(ThreadNode* p, ThreadNode** pre) {
	if (p->lchild == NULL) {
		p->lchild = *pre;
		p->ltag = 1;
	}
	if ((*pre) && (*pre)->rchild == NULL) {
		(*pre)->rchild = p;
		(*pre)->rtag = 1;
	}
	*pre = p;
}

具体的实现过程在上一个篇章中有详细介绍，这里我就不再赘述；

四、代码测试

这里我们以下列二叉树先序序列为例：

代码语言：javascript代码运行次数：0运行复制

[1,2,4,-1,6,-1,-1,-1,3,-1,5,7,-1,-1,-1]

该序列中，-1表示的是空指针。

接下来我们会完成以下任务：

二叉树的创建
二叉树转化为线索二叉树
线索二叉树的线索化
线索二叉树的遍历
二叉树的销毁
线索二叉树的销毁

4.1 二叉树的创建

我们通过先序遍历的方式创建二叉树，这样我们就能够得到图示二叉树：

【数据结构】C语言实现线索二叉树_线索化_06

创建完后，通过先序遍历获取的序列应该与给出的先序序列相同，下面我们就来进行测试：

【数据结构】C语言实现线索二叉树_线索二叉树_07

可以看到，我们成功创建了图示二叉树；

4.2 二叉树转化为线索二叉树

该转化的过程所对应的代码我们已经给出，现在直接进行测试，如下所示：

【数据结构】C语言实现线索二叉树_线索二叉树_08

4.3 二叉树的线索化

当我们完成线索化后，我们将会得到如下所示的线索二叉树：

【数据结构】C语言实现线索二叉树_结点_09

现在我们就无法直接通过访问二叉树的方式去访问，这时，我们就需要通过线索二叉树的遍历完成访问，如下所示：

【数据结构】C语言实现线索二叉树_线索二叉树_10

此时我们就完成了所有内容的测试。

五、三种线索二叉树的区别

线索二叉树是通过将二叉树线索化后能够快速找到其前驱与后继的二叉树。但是由于遍历方式的不同，不同的二叉树寻找其前驱后继的方式也不同：

5.1 先序线索二叉树

先序线索二叉树：由 根->左->右 的方式完成线索化的线索二叉树。

其前驱结点的获取方式如下所示：

若左孩子指针完成了线索化，则前驱指针指向的结点即为该结点的前驱结点
若左孩子指针没有线索化，当我们希望通过一个结点获取其前驱结点时，从遍历的方式不难看出，根结点就是遍历的起点，因此我们无法获取其前驱结点；

其后继结点的获取方式如下所示：

当右孩子指针完成线索化时，后继指针指向的结点即为该结点的后继结点
当右孩子指针没有线索化时，则根据左右孩子情况的不同会有不同情况，其后继结点也会不同：
有左孩子，则左孩子为后继结点
没有左孩子，有右孩子，则右孩子为后继结点

5.2 中序线索二叉树

中序线索二叉树：由 左->根->右 的方式完成线索化的线索二叉树。

其前驱结点的获取方式如下：

左孩子指针完成了线索化，则前驱指针指向的结点为前驱结点
左孩子指针没有线索化，则其左子树的最右侧结点为前驱结点

其后继结点的获取方式如下：

右孩子指针完成了线索化，则后继指针指向的结点为后继结点
右孩子指针没有线索化，则其右子树的最左侧结点为后继结点

5.3 后序线索二叉树

后序线索二叉树：由 左->右->根 的方式完成线索化的线索二叉树。

其前驱结点的获取方式如下：

左孩子指针完成了线索化，则前驱指针指向的结点为前驱结点
左孩子指针没有线索化：
有右孩子，则右孩子为其前驱结点
没有有孩子，有左孩子，则左孩子为其前驱结点

其后继结点的获取方式如下：

右孩子指针完成了线索化，则后继指针指向的结点为后继结点
右孩子指针没有线索化，则无法获取其后继结点

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。原始发表：2025-03-15，如有侵权请联系 cloudcommunity@tencent 删除遍历测试指针二叉树数据结构

科技改变生活-雨落星辰 - 所有的伟大,都源于一个勇敢的开始

【数据结构】C语言实现线索二叉树