【数据结构】C语言实现二叉树的线索化——中序线索化、先序线索化、后序线索化

蒙奇D索隆

发布于 2025-03-15 19:56:43

3700

代码可运行

文章被收录于专栏：蒙奇D索隆的学习笔记蒙奇D索隆的学习笔记

运行总次数：0

代码可运行

二叉树的线索化

导读

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

经过上一篇内容的介绍，现在我们知道了什么是线索以及什么是线索二叉树：

指向前驱结点或后继结点的指针称为线索
引入了线索的二叉树即线索二叉树

那对于一棵普通的二叉树而言，我们应该如何将其变为线索二叉树呢？

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

在今天的内容中，我们将会介绍3种二叉树的线索化。下面我们就直接进入正题吧！！！

一、二叉树的中序线索化

1.1 线索化逻辑

当我们通过中序遍历的方式完成线索化时，我们得到的就是一棵中序线索二叉树。

在中序遍历中，我们对二叉树的访问顺序为：左孩子->根结点->右孩子

在线索化的过程中，我们通过前驱指针 pre 和当前指针 p 来完成整个线索化的过程：

前驱指针初始为空，指针 p 初始指向二叉树的根结点；
当结点 p 的左子树为空，此时将左子树指向前驱结点 pre ；
当结点 pre 的右子树为空，此时将右子树指针指向后继结点 p；

【数据结构】C语言实现二叉树的线索化——中序线索化、先序线索化、后序线索化_二叉树_02

接下来我们就尝试着通过C语言将这一过程给展现出来。

1.2 C语言实现中序线索化

1.2.1 准备工作

在使用C语言实现之前，我们先打开自己的编译器，并创建新项目。我自己使用的是VS2019，大家使用自己的编译器即可。

在新项目中创建3个文件——TreadTree.h、TreadTree.c、TestTreadTree.c分别对应的是头文件、算法实现文件以及算法测试文件。

ps:在今天的内容中，我们不会对算法的实现进行测试，因此TestTreadTree.c部分的内容不会进行介绍，在下一篇内容中，会详细介绍如何实现一棵二叉线索树，感兴趣的朋友可以点个关注！！！

在头文件中，我们需要引入所需要的库，并且定义我们要使用的数据结构：

#include <stdio.h>	//标准输入输出
#include <stdlib.h>	//动态内存管理
#include <stdbool.h>//布尔值
#include <assert.h>	//断言

//重命名数据的数据类型
typedef int ElemType;
//重命名标志的数据类型
typedef bool TagType;
typedef struct ThreadNode {
	//数据域
	ElemType data;
	//指针域
	struct ThreadNode* lchild, * rchild;
	//标志域
	TagType ltag, rtag;
}ThreadNode, * ThreadTree;
//ThreadNode——线索结点
//* ThreadTree——线索树

注意！！！

这里需要注意，我为了区分结点与树，这里我通过一个一级指针表示的是树，如果在后续的操作中，我们在传入参数时，出现了取地址的操作，那么代表传入的应该是一个二级指针！！！要是大家难以接受这种写法，可以不用定义一级指针！！！

1.2.2 算法的实现

在TreadTree.c文件中，我们用来实现中序线索化。

在前面的逻辑中我们明确了几件事：

线索化的过程需要2个指针——pre 与 p

pre指向的是前驱结点
p指向的是当前结点

线索化的实现是通过中序遍历的方式

现在我们就可以理清一个大致思路了：

函数的参数为2个结点指针
函数的实现是中序遍历——左、根、右

要实现线索化这个算法，无非就是编写一个函数，而函数的三要素有：

函数名：这里我们不妨定义函数名为 InThread
函数参数：两个数据类型为 ThreadNode* 的指针
函数返回类型：整个实现的过程不需要返回任何值，所以我们可以定义为 void 类型

在函数体中，我们是通过中序遍历的方式实现，因此我们就得到了函数的一个大致框架：

void InThread(ThreadNode* p, ThreadNode* pre) {
	InThread(p->lchild, pre);
	visit(p, pre);
	InThread(p->rchild, pre);
}

既然我们所使用的是递归的方式实现，那我们就需要一个限制条件，防止出现死递归。

在中序遍历中，我们是以指针p是否为空作为限制条件，这是因为当指针p遍历到空指针时，说明此时遍历的是一棵空树，既然是空树，那我们就无需进行遍历，因此p == NULL就是我们递归的限制条件，如下所示：

if (p) {
		InThread(p->lchild, pre);
		visit(p, pre);
		InThread(p->rchild, pre);
	}

这里我是偷懒了，大家勤快点也可以写成p != NULL，这个就看个人习惯了。

有了整体的框架，下面我们就可以开始完成结点访问的实现了。

在访问结点时，我们实际上就是在判断是否进行线索化：

当p->lchild == NULL：说明该结点的左孩子为空，此时我们需要将左孩子指针线索化为前驱指针；
当pre->rchild == NULL：说明当前结点的右孩子为空，此时我们需要将右孩子指针线索化为后继指针；

在完成线索化后，我们需要移动指针的指向，始终保持pre是p的前驱结点，p是pre的后继结点

这里需要注意的是，如果 pre 为空指针，那么我们在进行后继线索化时，就会出现错误，因此我们需要对pre进行判断

因此整个visit的实现应该是：

void visit(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;
}

对于最后一个结点的后继线索化，我们是无法在算法中完成，这是因为最后一个结点的右孩子肯定为空，此时算法会结束递归，在这种情况下，我们需要单独的对最后一个结点进行后继线索化：

InThread(p, pre);
	//最后一个结点的后续线索化
	pre->rchild = p;
	pre->rtag = 1;

整个算法的主要功能是在创建一棵线索二叉树，因此我们不妨将其同样封装成一个函数CreateInThreadTree，该函数的参数为一棵完整的二叉树，该函数的返回类型为void这样我们就得到了最终的函数：

void CreateInThreadTree(ThreadTree tree) {
	ThreadNode* pre = NULL;
	ThreadNode* p = tree;
	InThread(p, pre);
	//最后一个结点的后续线索化
	pre->rchild = NULL;
	pre->rtag = 1;
}

这里需要注意，函数的参数为一个一级指针，之所以不用二级指针，是因为我们在整个线索化的过程中不会对根结点进行修改。

有朋友可能会有疑惑，如果我们将根结点也进行了线索化，那不是也对它进行了修改吗？为什么用的不是二级指针呢？

这个是因为我们对指针进行修改实际上时修改的地址，而不是地址中存放的值。

这个问题要想理解，就需要回顾一下指针传参；

1.2.3 指针传参

这里我简单的用一张图来表示：

【数据结构】C语言实现二叉树的线索化——中序线索化、先序线索化、后序线索化_线索化_03

在指针传参中，如果只是修改指针所指向的地址中的值，那么就不是对指针进行修改，这时是不需要对指针进行取地址操作的。

二、二叉树的先序线索化

先序线索化与中序线索化的实现思路是一致的，都是通过二叉树的遍历实现。

二者的区别无非就是对根结点的访问顺序，在先序遍历中，遵循：根、左、右的顺序进行访问。因此，在线索化时，同样是根据该顺序完成的访问，如下所示：

void PreThread(ThreadNode* p, ThreadNode* pre) {
	if (p) {
		visit(p, pre);
		PreThread(p->lchild, pre);
		PreThread(p->rchild, pre);
	}
}

线索化的过程同样是以判断结点的左右子树是否为空，这里就不再重复展示；

三、二叉树的后序线索化

后序线索化同样是以后序遍历的方式实现，其代码如下：

void PostThread(ThreadNode* p, ThreadNode* pre) {
	if (p) {
		PostThread(p->lchild, pre);
		PostThread(p->rchild, pre);
		visit(p, pre);
	}
}

四、完整代码展示

三种线索化的完整代码如下所示：

//-----头文件<TreadTree.h>-----
#include <stdio.h>	//标准输入输出
#include <stdlib.h>	//动态内存管理
#include <stdbool.h>//布尔值
#include <assert.h>	//断言

//重命名数据的数据类型
typedef int ElemType;
//重命名标志的数据类型
typedef bool TagType;
typedef struct ThreadNode {
	//数据域
	ElemType data;
	//指针域
	struct ThreadNode* lchild, * rchild;
	//标志域
	TagType ltag, rtag;
}ThreadNode, * ThreadTree;
//ThreadNode——线索结点
//* ThreadTree——线索树

//访问根结点
void visit(ThreadNode* p, ThreadNode* pre);

//中序线索化
void InThread(ThreadNode* p, ThreadNode* pre);
//先序线索化
void PreThread(ThreadNode* p, ThreadNode* pre);
//后序线索化
void PostThread(ThreadNode* p, ThreadNode* pre);

//创建中序线索树
void CreateInThreadTree(ThreadTree tree);
//创建先序线索树
void CreateInThreadTree(ThreadTree tree);
//创建后序线索树
void CreateInThreadTree(ThreadTree tree);

//-----算法实现文件<TreadTree.c>-----
#define _CRT_SECURE_NO_WARNINGS 1

#include "blog.h"

//算法实现文件

//访问根结点
void visit(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;
}

//中序线索化
void InThread(ThreadNode* p, ThreadNode* pre) {
	if (p) {
		InThread(p->lchild, pre);
		visit(p, pre);
		InThread(p->rchild, pre);
	}
}

//先序线索化
void PreThread(ThreadNode* p, ThreadNode* pre) {
	if (p) {
		visit(p, pre);
		PreThread(p->lchild, pre);
		PreThread(p->rchild, pre);
	}
}

//后序线索化
void PostThread(ThreadNode* p, ThreadNode* pre) {
	if (p) {
		PostThread(p->lchild, pre);
		PostThread(p->rchild, pre);
		visit(p, pre);
	}
}

//创建中序线索树
void CreateInThreadTree(ThreadTree tree) {
	ThreadNode* pre = NULL;
	ThreadNode* p = tree;
	InThread(p, pre);
	//最后一个结点的后续线索化
	pre->rchild = NULL;
	pre->rtag = 1;
}

//创建先序线索树
void CreateInThreadTree(ThreadTree tree) {
	ThreadNode* pre = NULL;
	ThreadNode* p = tree;
	PreThread(p, pre);
	//最后一个结点的后续线索化
	pre->rchild = NULL;
	pre->rtag = 1;
}

//创建后序线索树
void CreateInThreadTree(ThreadTree tree) {
	ThreadNode* pre = NULL;
	ThreadNode* p = tree;
	PostThread(p, pre);
	//最后一个结点的后续线索化
	pre->rchild = NULL;
	pre->rtag = 1;
}

有朋友可能会好奇，为什么没有测试文件的代码？

这个问题，我们将留在下一个篇章进行说明，大家记得关注哦！！！