C语言实现二叉树

导读

经过前面两篇内容的介绍，我相信大家对二叉树的基本操作已经比较熟悉了，并且能够自己通过C语言来实现这些基本操作。

不过比较可惜的是在前面的内容中我们并没有完整的实现一棵二叉树，因此我们在实现这些基本功能后，并没有对这些功能进行相应的测试。

那么为了弥补这个遗憾，在今天的内容中，我们将通过C语言来实现一棵二叉树，并对前面介绍的这些基本操作进行相应的测试。既然要实现一棵二叉树，那我们就需要完成对二叉树的创建、元素的添加、删除以及二叉树的销毁等基本操作，接下来我们就来开始进入今天的内容吧！！！

一、二叉树的数据类型

在今天的内容中，我们将会通过二叉链表来实现一棵二叉树，对应的代码如下所示：

typedef char ElemType;
typedef struct BiTreeNode {
	ElemType data;//数据域
	struct BiTreeNode* lchild, * rchild;//指针域
}BTN, * BTL;
//BTN——二叉树结点类型
//BTL——二叉树类型

经过前面内容的介绍，二叉链表相信大家都是比较熟悉的了，这里我就不再展开赘述；

二、二叉树的初始化

当我们对二叉树进行初始化时，实际上就是将其初始化为一棵空树，既然是通过链表来实现一棵二叉树，那么二叉链表的初始化与双链表的初始化相同，都有两种初始化方式：

• 带头结点的初始化：在初始化时创建一个头结点，该结点的左右指针都置为空；
• 不带头结点的初始化：在初始化时直接将链表头指针置为空指针；

这两种初始化方式都是可行的，不过要注意的是当我们通过带头结点的方式对二叉链表进行初始化时，我们需要注意插入根结点的位置：

• 当根结点插入到头结点的左孩子后，后续的结点都需要插入到头结点的左孩子后；
• 当根结点插入到头结点的右孩子后，后续的结点都需要插入到头结点的右孩子后；

如果我们在实际操作过程中，将结点分别插入到了头结点的左右孩子后，那此时就创建的不是一棵二叉树了，而是有两棵树的森林，这个一定要注意！！！当然我相信各位肯定不会出现这种失误的啦！

在今天的演示中，我会以不带头结点的方式对其进行初始化，代码如下所示：

//二叉树的初始化
void BTInit(BTL* T) {
	assert(T);
	*T = NULL;
	//BTL为一级指针类型，这里的参数T为二级指针类型，因此需要对其解引用
}

2.1 补充知识点——传址传参

在C语言中有一个点是需要大家注意的：

• 当我们在传参时需要对实参的内容进行修改，则需要进行取地址传参；

由于我们在实现时创建的是一个指向二叉链表的头指针，而我们在初始化之后需要能够修改指针的值，这时就需要通过取地址传参，对应的测试代码如下所示：

//二叉树基本操作的测试
void test1() {
	BTL T;//创建二叉链表
	BTInit(&T);//初始化二叉链表
}

2.2 补充知识点——指针传参

当我们在进行指针传参时需要注意几个点：

1. 一级指针进行传值传参时形参需要通过一级指针进行接收
2. 一级指针进行传址传参时形参需要通过二级指针进行接收
3. 当需要对形参进行解引用操作时，形参不能为空指针

大家如果有经常看我的C语言实现数据结构的内容的话，会发现在有些操作中我是通过assert对形参进行断言的方式来检查空指针，有些则是通过条件语句的方式来检测空指针，它们之间的区别在于函数中是否能够出现空指针：

• 通过assert断言进行检查空指针对应的功能是不能够出现空指针的情况，比如这里的初始化，我这里初始化的目的是为了将头指针置空避免出现野指针的情况，如果头指针本来就为空指针是不需要进行初始化的；
• 通过条件语句的方式来检查空指针对应的功能是可以出现空指针的情况，比如二叉树的判空操作，当我们以不带头结点的方式初始化头指针时，那二叉树的空树就是在头指针为空时二叉树为空，这时我们是需要用到这个空指针来实现函数的；

因此大家在自己实现对应的功能时一定要注意区分什么时候可以用assert进行断言，什么时候不能用assert进行断言。

三、二叉树的创建

我们要创建一棵二叉树有两种方式：

1. 通过添加结点创建BST
2. 给定一组结点序列创建二叉树

接下来我们将会介绍一下这两种创建方式。

3.1 通过添加结点创建BST

我们先简单的复习一下什么是BST：

BST(Binary Search Tree——二叉搜索树、二叉查找树、二叉排序树) BST中的结点满足左子树 < 根结点 < 右子树

简单的理解就是当我们初始化好一棵空树后，我们往树中添加的第一个结点为根结点，之后再往树中添加新的结点时，则需要根据该结点中数据的大小来确认其添加的位置：

• 当该结点的数据>根结点存储的数据，该结点添加到右子树中
• 当该结点的数据<根结点存储的数据，该结点添加到左子树中
• 当该结点的数据=根结点存储的数据，该结点不会添加到树中

当然BST中的每一棵子树都是BST，这样我们在创建时每一个结点才能找到自己应该存在的位置，如下所示：

上图就是一棵BST树的创建过程，不难想象如果需要通过算法实现的话，那肯定需要通过循环来遍历二叉树，在循环中需要根据根结点与插入结点的比较结果来选择往左子树遍历还是往右子树遍历。代码如下所示：

//二叉树的创建——创建BST
void CreatBST(BTL* T, ElemType x) {
	assert(T);
	BTN* p = (BTN*)calloc(1, sizeof(BTN));//创建结点
	if (!p) {
		perror("CreatBST calloc fail");//空间申请失败时报错
		return;
	}
	p->data = x;//将数据放入x中
	p->lchild = p->rchild = NULL;//将左右指针置空
	BTN* t = *T;//指向根结点的指针
	while (t) {
		if (t->data < p->data && t->rchild) //当根<该结点,且右子树不为空树时
			t = t->rchild;//继续向右子树遍历
		else if (t->data > p->data && t->lchild)//当根>该结点,且左子树不为空树时
			t = t->lchild;//继续向左子树遍历
		else if (t->data < p->data && !t->rchild)//当根结点<该结点并且右子树为空时
		{
			t->rchild = p;//将该结点插入右子树
			return;
		}
		else if (t->data > p->data && !t->lchild)//当根结点>该结点并且左子树为空时
		{
			t->lchild = p;//将该结点插入左子树
			return;
		}
		else {
			printf("树中已存在结点%d，插入失败\n", p->data);
			return;
		}
	}
	*T = p;//当未进入循环时，说明该树为空树，直接将该结点作为根结点插入树中
	return;
}

3.2 通过结点序列创建二叉树

通过结点序列来创建二叉树，这里的结点序列则有四种情况：

• 先序序列：通过先序遍历获取的结点序列
• 中序序列：通过中序遍历获取的结点序列
• 后序序列：通过后序遍历获取的结点序列
• 层序序列：通过层序遍历获取的结点序列

接下来我们将会分别介绍手算和计算两种方式来构建二叉树；

3.2.1 由遍历序列手算构建二叉树

我们在做题时会遇到需要通过遍历序列手算构建二叉树的题目，如：

已知一棵二叉树的后序序列为DABEC，中序序列为DEBAC，则先序序列为（） A. ACBED B. DECAB C. DEABC D. CEDBA

这种题目的解题思路并不难，只需要通过已知的结点序列将对应的二叉树构建出来后再获取题目要求的结点序列即可。

现在对我们来说比较陌生的就是如何通过结点序列来构建一棵二叉树了。当我们要构建一棵二叉树时，我们首先要做的第一件事就是确定根结点，因此如何通过结点序列确定根结点是我们需要关心的问题。要解决这个问题，我们需要先搞清楚四种序列的特点：

• 先序序列：由先序遍历：根结点—>左子树—>右子树可知，二叉树的根结点为序列的首元素
• 中序序列：由先序遍历：左子树—>根结点—>右子树可知，二叉树的根结点在序列的中间
• 后序序列：由先序遍历：左子树—>右子树—>根结点可知，二叉树的根结点为序列的尾元素
• 层序序列：由层序遍历：第一层—>第二层—>第三层可知，二叉树的根结点为序列的首元素

那是不是说只要找到了根结点的位置，那我随便通过哪一个序列都可以创建了呢？下面我们就来尝试一下能否通过遍历序列构建一棵二叉树，以先序序列ABCDE为例，如下所示：

可以看到如果我们通过先序序列确实可以创建二叉树，并且还可以创建出不同的二叉树，上图展示的仅仅只是其中的一部分。从这个例子中我们可以得到结论：

• 只通过先序序列可以创建二叉树，但是无法确定一棵唯一的二叉树。

同理以上四种序列如果只使用其中一种来创建二叉树都是无法确定一棵唯一的二叉树的，因此我们可以大胆推测，如果我们想要通过遍历序列来构建一棵唯一的二叉树的话，那我们至少需要知道两种序列。那现在问题来了，是不是任意两种都能获取呢？

从四种序列的特点我们不难看出先序遍历和层序遍历能够获取的根结点信息是相同的，因此如果只知道这两种序列肯定是无法确定一棵唯一的二叉树的；

由先序遍历和后序遍历的方式可知，它们获取的遍历序列中，左右子树是相邻的，仅仅是根结点从首元素换到了尾元素而已。在上图中的第一排左子树中左子树1和左子树4与第二排右子树中的右子树1和右子树4这四棵树的后序序列都是DECBA，也就是说如果只知道先序和后序两种序列的话我们也是无法确认一棵唯一的二叉树的；

在中序遍历中，根结点就如同分界限一样将左右子树给分隔开了，也就是说，当我们确认根结点的位置时，那位于根结点左侧的一定是左子树的部分，位于根结点右侧的一定是右子树部分，这样的话我们只需要通过前序、后序和层序的其中一种序列找到根结点，那我们就能确定一棵唯一的二叉树了。

3.2.1.1 构建步骤

从上述的分析中，我们可以大致得到通过遍历序列构建二叉树的步骤：

1. 通过先序序列、后序序列或层序序列三者中的一种获取二叉树的根结点；
2. 通过中序序列获取根结点的左右子树
3. 重复前面两步直到得到一棵完整的二叉树为止

那这个步骤具体可不可行，我们暂时还不清楚，下面我们就来通过题目来验证一下；

3.2.1.2 习题演练

已知一棵二叉树的后序序列为DABEC，中序序列为DEBAC，则先序序列为（） A. ACBED B. DECAB C. DEABC D. CEDBA

【解题分析】从后序序列可知，该二叉树的根结点为C，从中序序列可知，该二叉树只有左子树，因此我们可以得到二叉树的初步形态；

从后序序列的倒数第二个结点可知，E为左子树的根结点，从中序序列可知，该子树的左子树为D，该子树的右子树为BA，因此我们进一步得到二叉树的形态；

从后序序列的倒数第三个结点可知，B为右子树的根结点，从中序序列可知，A为该子树的右子树，因此我们就得到了该二叉树的最终形态；

当二叉树的形态确定后就可以求出对应的先序序列和层序序列了，也可以通过该形态求出其后序序列和中序序列来验证是否正确。整个分析流程如下图所示：

因此这一题的答案为 D.CEDBA。

3.2.1.3 小结

接下来我们就来对该知识点做个总结：

1. 由四种遍历序列的其中一种序列能够构建出不同的二叉树
2. 要确定唯一的一棵二叉树需要通过先序、后序或层序中的一种遍历序列与中序序列搭配
3. 构建唯一一棵二叉树的步骤如下：

• 第一步：通过先序、后序或层序序列来确定二叉树的根结点
• 第二步：通过中序序列来确定二叉树的左右子树
• 第三步：通过画图来明确已求的的二叉树
• 第四步：重复上述三步直到获取一棵完整的二叉树为止

PS：在整个数据结构的学习过程中，画图是帮助我们理解知识点的一个重要的途径，建议大家平时在练习时能过多动手画画图。

3.2.2 通过C语言实现结点序列构建二叉树

当我们需要通过C语言来构建一棵二叉树时，我们获取的结点序列可能与手算时有些许不同，比如先序序列"ABD##E#H##CF##G##"在这个序列中#代表的是空结点，这些字符代表的才是二叉树中对应的结点，因此我们不难得出该二叉树的形态：

在这种情况下我们如果要通过C语言来实现的话可以通过先序遍历的方式来创建二叉树，代码如下所示：

//二叉树的创建
BTN* BTCreat(ElemType* arr, int* pi) {
	//T为二级指针
	//arr为存放序列的数组
	//pi为数组下标
	assert(arr && pi);
	//限制条件
	if (!arr[*pi])//元素为'\0'时
		return NULL;//结束创建
	if (arr[*pi] == '#') {
		//当元素为'#'时，二叉树对应结点为空
		(*pi)++;//继续向后遍历
		return NULL;//返回空指针
	}
	//创建根结点
	BTN* p = (BTN*)calloc(1, sizeof(BTN));
	if (!p) {
		perror("BTCreat calloc fail");
		return;
	}
	p->data = arr[(*pi)++];//访问根结点
	p->lchild = BTCreat(arr, pi);//遍历创建左子树
	p->rchild = BTCreat(arr, pi);//遍历创建右子树
	return p;
}

四、二叉树的销毁

当我要销毁一棵二叉树时，我们则需要从二叉树的叶结点开始依次往上释放结点的内存空间，该操作的实现同样可以通过层序遍历和递归两种方式来实现，今天我们就简单一点，通过递归的方式来实现即可，代码如下所示：

//二叉树的销毁
void BTDestroy(BTL* T) {
	assert(T);
	if (!(*T))
		return;
	//通过后序遍历销毁二叉树
	BTDestroy(&((*T)->lchild));
	BTDestroy(&((*T)->rchild));
	free(*T);//释放叶结点的内存
	*T = NULL;
}

这里需要注意的是，我们既然要从叶结点开始进行销毁，那么对于叶结点所在的子树而言，我们需要先通过遍历确认其左右子树都为空，才能将该结点删除，而先遍历左右子树的方式刚好是后序遍历的方式，所以这里我们通过递归实现时是以后序遍历的方式来进行的销毁。

五、基本操作的测试

现在我们已经完成了创建和销毁两个基本操作了，接下来就可以通过创建二叉树后进行遍历、求树的深度、求总结点数、求第K层的结点数、求叶子结点数等功能的测试了。

5.1 通过结点序列创建二叉树

我们首先要测试的是通过结点序列创建的二叉树，结果如下所示：

从测试结果中可以看到，现在我们成功实现了通过遍历序列创建二叉树以及其它一系列的基本操作。测试中我们采用的例子就是前面介绍的例子ABD##E#H##CF##G##，大家可以尝试着通过遍历序列手算一下对应的二叉树，是否与前面咱们介绍时的一致，以此来验证算法的正确性。

5.2 创建BST

最后我们要测试的是创建一棵BST，测试结果如下所示：

在这次测试中输入的例子所对应的二叉树如下所示：

从这次测试的结果可以看到，此时算法很好的创建了上图中的二叉树，感兴趣的朋友可以根据算法获取的遍历序列来尝试着构建一下对应的二叉树。

结语

在今天的内容中，我们详细介绍了二叉树的创建——通过遍历序列手算创建二叉树，这一块的内容相对来说还是比较重要的，建议大家自己平时抽空多练习一下。

今天算是弥补了前面的遗憾，完成了二叉树基本功能的测试。可能有朋友会比较好奇，为什么今天的内容中没有介绍二叉树的删除？这个问题我们先进行保留，目前我们只需要了解并熟练掌握二叉树的遍历算法的基本思想即可。从这几篇内容我们不难发现，二叉树的基本操作的实现都是基于二叉树四种遍历的算法思想上进一步拓展得到的，因此在二叉树的篇章中，二叉树的遍历是一块非常重要的内容，大家一定要花时间多多练习与理解。