【数据结构】二叉树

本篇我们来说一下数据结构中的树。

1.树的概念及结构

1.1 概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树可以拆成根和子树，子树又可以拆成根和子树...所以又说，树是递归定义的。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构。如下。

1.2 结构

• 结点的度：一个结点含有的子树的个数称为该结点的度； 如上图：A的为6
• 叶结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、H、I...等结点为叶结点
• 非终端结点或分支结点：度不为0的结点； 如上图：D、E、F、G...等结点为分支结点
• 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点
• 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点
• 兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点
• 树的度：一棵树中，最大的结点的度称为树的度； 如上图：树的度为6
• 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
• 树的高度或深度：树中结点的最大层次； 如上图：树的高度为4
• 堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点
• 结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先
• 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
• 森林：由m（m>0）棵互不相交的树的集合称为森林；

1.3 树的表示（详解）

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了， 既然保存值域，也要保存结点和

结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及

孩子兄弟表示法等。我们这里就简单的了解其中最常用的 孩子兄弟表示法。

struct TreeNode
{
	int val;
	struct TreeNode* leftchild; //左孩子
	struct TreeNode* rightbrother; //右兄弟
};

左孩子的意思是，无论父节点有多少孩子，leftchild只指向父节点左边开始的第一个孩子。

右兄弟的意思是，挨着指向父节点右边的兄弟节点，没有兄弟节点指向空。具体分析如下。

A有两个孩子，A的child指向A左边的第一个孩子B，A没有兄弟节点，A的brother指向空。

B有三个孩子，B的child指向B左边的第一个孩子D，B有兄弟节点C，B的brother指向C。

D没有孩子，D的child指向空，D有兄弟，D的brother指向右边的兄弟E；C有一个孩子，C的child指向这个孩子G，C没有兄弟，C的brother指向空。

E有两个孩子，E的child指向E的左边第一个孩子H，E有兄弟，E的brother指向右边的兄弟F；G现在没有孩子也没有兄弟，都指向空。

H没有孩子，H的child指向空，H有兄弟，H的brother指向右边的兄弟I。F没有兄弟也没有孩子，都指向空。

I没有兄弟也没有孩子，I的child和brother都指向空。

此时整个树就连接完成了，这个设计非常巧妙。

2.二叉树

2.1 二叉树的概念

一棵二叉树是结点的一个有限集合，该集合 : 1. 或者为空 2. 由一个根结点加上两棵别称为左子树和右子树的二叉树组成

从上图可以看出： 1. 二叉树 不存在度大于2 的结点 2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

2.2 特殊二叉树

二叉树里有两个特殊的二叉树：满二叉树、完全二叉树。

满二叉树 ：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K ，且结点总数是2^k - 1，则它就是满二叉树。

完全二叉树 ：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K的，有n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至n的结点一一对应时称之为完全二叉树。

要注意的是满二叉树是一种特殊的完全二叉树。

2.3 二叉树的存储结构

2.3.1 顺序存储

顺序结构存储就是使用 数组来存储，一般使用数组只适合表示 完全二叉树、满二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，堆后面才会说。

非完全二叉树会存在空间浪费的情况。

如果不空出来，下面的父子关系就直接混乱了。

2.3.2 父子关系

假设父节点在数组的下标为i： 左孩子在数组的下标：2*i + 1；右孩子在数组的下标：2*i + 2；

假设子节点在数组中的下标为j： 父节点在数组中的下标：(j - 1) / 2；

2.3.3 链表存储

二叉树的链式存储结构是指，用 链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成， 数据域和 左右指针域，左右指针分别用来给出该结点 左孩和右孩子所在的链结点的 存储地址 。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
 struct BinTreeNode* left; // 指向当前结点左孩子
 struct BinTreeNode* right; // 指向当前结点右孩子
 BTDataType data; // 当前结点值域
}

2.4 二叉树的性质

• 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有

2^{^{i-1}}

个结点

• 若规定根结点的层数为1，则深度为h的二叉树的最大结点数是

2^{^{h}}-1

• 对任何一棵二叉树, 如果度为0其叶结点个数为

n_{0}

，度为2的分支结点个数为

n_{2}

，则有

n_{0}=n_{2}+1

• 若规定根结点的层数为1，具有n个结点的满二叉树的深度，h =

\log_{2}(n+1)

2.5 相关练习

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）

A 不存在这样的二叉树

B 200

C 198

D 199

答案：B 度为2的有199个，就是

n_{2}=199

，因为

n_{0}=n_{2}+1

，所以叶子节点有200个。

2. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）

A n

B n+1

C n-1

D n/2

答案：A 假设度为2的节点个数有

n_{2}

个，度为1的有

n_{1}

个，叶子节点有

n_{0}

个，2n =

n_{2}

n_{1}

n_{0}

，而

n_{0}=n_{2}+1

，所以2n =

n_{1}

+ 2

n_{0}

- 1；在完全二叉树中，度为1的

n_{1}

的个数，要不就是1，要不就是0；由于2n一定是偶数，只有当

n_{1}

为1时，

n_{1}

+ 2

n_{0}

- 1的结果才为偶数；所以这个式子最后化简为2n = 2

n_{0}

，

n_{0}

就是叶子节点个数，为n。

3.一棵完全二叉树的结点数位为531个，那么这棵树的高度为（ ）

A 11

B 10

C 8

D 12

答案：B 完全二叉树的节点个数范围如下。

所以把选项往

2^{^{h-1}}

和

2^{h}-1

里带，发现h为10时，531在这个范围内。

3.堆

堆是一颗完全二叉树。

堆的详解在【数据结构】堆的概念、结构、模拟实现以及应用

4.二叉树的链式结构

4.1 二叉树的遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次。

4.1.1 前序、中序、后序遍历

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历

• 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。（根 左子树 右子树）
• 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。（左子树 根 右子树）
• 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。（左子树 右子树 根）

可以发现，这三种遍历的特点其实是递归遍历。

4.1.2 层序遍历

层序遍历就是一层一层遍历访问。

4.2 二叉树的遍历的代码实现

首先我们手搓一个二叉树出来。

#include <stdio.h>
#include <stdlib.h>

typedef char BTDataType;
typedef struct BTNode //节点，用结构体封装
{
	BTDataTypeval;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;

BTNode* CreatNode(BTDataType x) //创建节点
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return;
	}
	node->val = x;  
	node->left = NULL;
	node->right = NULL;
	return node;
};

int main()
{
	BTNode* node0 = CreatNode('A'); //创建节点
	BTNode* node1 = CreatNode('B');
	BTNode* node2 = CreatNode('C');
	BTNode* node3 = CreatNode('D');
	BTNode* node4 = CreatNode('E');
	BTNode* node5 = CreatNode('F');
	BTNode* node6 = CreatNode('G');
    //链接
	node0->left = node1;    
	node0->right = node2;
	node1->left = node3;
	node1->right = node4;
	node2->left = node5;
	node2->right = node6;
	
	return 0;
}

这里的链接和前面的图一致。

三种遍历方式的实现都是用了递归，递归的知识在这里不多说，不太懂得的建议先弄懂递归。

4.2.1 前序遍历

void Preorder(BTNode* node) //前序：根 左 右
{
	if (node == NULL)
		return;       //为空时直接返回

	printf("%c ", node->val);//根
	Preorder(node->left);    //左
	Preorder(node->right);   //右
}

我们传根节点过去。

Preorder(node0);

和我们前面分析的结果一样。

4.2.2 中序遍历

同样是递归实现，顺序不同。

void Inorder(BTNode* node) //中序：左 根 右
{
	if (node == NULL)
		return;       //为空时直接返回

	Inorder(node->left);     //左
	printf("%c ", node->val);//根
	Inorder(node->right);    //右
}

同样直接传根节点过去。

Inorder(node0);  //中序

和前面的分析结果一致。

4.2.3 后序遍历

后序遍历同理。

void Postorder(BTNode* node) //后序：左 右 根
{
	if (node == NULL)
		return;       //为空时直接返回

	Postorder(node->left);    //左
	Postorder(node->right);   //右
	printf("%c ", node->val); //根
}

直接传根节点过去。

Postorder(node0);//后序

和前面推理的结果一致。

4.2.4 层序遍历

层序遍历我们要结合队列来实现。根节点进队列，出队列的时候带着自己的“孩子”进队列。

到这一步之后，D出队列，D没有孩子，队列就不用进数据，E、F、G同理。

当队列为空时，数据全部出完，层序遍历完成。

C语言中没有队列的库，不过我们之前用C语言自己实现过队列：【数据结构】队列的概念、结构和实现详解

我们把自己实现的队列放进当前工程。

然后在二叉树的.c文件中包含队列的头文件。

#include "queue.h" //队列头文件

队列存放的数据是二叉树节点，所以我们还要在 queue.h 里改一下类型，只需要改动一句代码。

//typedef BTNode QDataType;  //不可以这样写
typedef struct BTNode* QDataType; //要用原生类型

现在就可以代码实现层序遍历了。

void Leveloder(BTNode* node) //层序遍历
{
	Queue q;
	QueueInit(&q); //队列初始化
	if (node)
		QueuePush(&q, node);
	while (!QueueEmpty(&q))
	{
		BTNode* temp = QueueFront(&q);//取队头数据
		printf("%c ", temp->val);

		QueuePop(&q); //根出

		//有子就入
		if (temp->left)
			QueuePush(&q, temp->left);
		if (temp->right)
			QueuePush(&q, temp->right);
	}
	QueueDestroy(&q); //队列销毁
}

拿前面的二叉树做测试。

Leveloder(node0);
printf("\n");

4.3 节点个数及高度等

4.3.1 节点个数

节点个数最好的求法就是递归，任意一棵树的节点个数都可以看成：左子树个数+右子树个数+1

int BTSize(BTNode* node)  //节点个数
{
	if (node == NULL)
		return 0;
	else
		return BTSize(node->left) + BTSize(node->right) + 1;
}

这个代码可以用一个三目操作符进行简化。

int BTNodeSize(BTNode* node)  //节点个数
{
	return node == NULL ? 0 :
		BTNodeSize(node->left) + BTNodeSize(node->right) + 1;
}

验证一下代码，传根节点过去。

printf("BTNodeSize:%d\n", BTNodeSize(node0));

​

4.3.2 叶子节点个数

求叶子结点的个数同理，递归表示，求法为左节点的叶子节点个数+右节点的叶子节点个数。

int BTLeafSize(BTNode* node) //叶子节点个数
{
	if (node == NULL)
		return 0;
	if (node->left == NULL && node->right == NULL)
		return 1;
	return BTLeafSize(node->left) + BTLeafSize(node->right);
}

验证一下代码，传根节点过去。

printf("BTLeafSize:%d\n", BTLeafSize(node0));

​

4.3.3 二叉树的高度（深度）

求二叉树的高度，左子树和右子树谁更高，更高的那边+1就是树的高度了，每一棵树都按照这种方法计算，同样用到了递归。

int BTHeight(BTNode* node)  //树的高度
{
	if (node == NULL)
		return 0;
	int BTleft = BTHeight(node->left);  //左子树高度
	int BTright = BTHeight(node->right);//右子树高度

	return BTleft > BTright ? BTleft + 1 : BTright + 1;//返回大的高度+1
}

验证一下代码，传根节点过去。

printf("BTHeight:%d\n", BTHeight(node0));

​

4.3.4 第k层节点个数

求第k层的节点个数，可以看做求子节点的k-1层的节点个数。比如下图，求k=3层的节点个数，对第一层来说，k=3，对于第二层来说，k=2，对于第三层来说，k=1。

​

这里用递归来解决，代码如下。

int BTkSize(BTNode* node, int k)
{
	if (node == NULL) //为空就是没有节点
		return 0;
	if (k == 1) //求第一层，第一层就一个节点
		return 1;
	return BTkSize(node->left, k - 1) + BTkSize(node->right, k - 1);
}

我们用前面的二叉树来检测。

//求第三层节点个数
printf("BTHeight:%d\n", BTkSize(node0, 3));

​

4.3.5 查找值为x的结点

查找值为x的节点，我们可以选择前序遍历，前序遍历是最方便的。如果在根节点找到了，直接返回，不用再去左右子树找，如果根节点没找到，取左子树找，在左子树找到了就不用再去右子树找了，如果左右子树都没找到，返回NULL。

BTNode* BTFindx(BTNode* node, BTDataType x)
{
	if (node == NULL)
		return NULL;
	if (node->val == x)
		return node;
	BTNode* temp1 = BTFindx(node->left, x);
	if (temp1)
		return temp1;
	BTNode* temp2 = BTFindx(node->right, x);
	if (temp2)
		return temp2;
	return NULL;
}

我们用前面的二叉树验证一下。

//查找F
BTNode* ret = BTFindx(node0, 'F');
if (ret)
	printf("x:%c\n", ret->val);
else
	printf("Didn't find!\n");

​

//查找不存在的k
BTNode* ret = BTFindx(node0, 'k');
if (ret)
	printf("x:%c\n", ret->val);
else
	printf("Didn't find!\n");

​

4.4 二叉树的创建和销毁

4.4.1 销毁

二叉树的销毁要走后序遍历，根节点最后释放，如果先把根节点释放了，子节点就找不到了。

void BTDestroy(BTNode* node)
{
	if (node)
		return;
	BTDestroy(node->left);
	BTDestroy(node->right);
	free(node);
}

4.4.2 创建

假设要求通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树。先画图分析。

​

B的左子树就复原完了，现在复原B的右子树。

​

B复原完之后，也就是A的左子树全部复原完了，现在剩下的就是A的右子树。

​

现在我们思路就很清晰了。

//通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* CreateBT(BTDataType* a, int* pi)
{
	if (a[*pi] == '#')
		return NULL;
	BTNode* node = CreatNode(a[*pi]);
	(*pi)++;
	node->left = CreateBT(a, pi);  //建左节点
	(*pi)++;
	node->right = CreateBT(a, pi); //建右节点
	return node;
}

a是数组，pi是下标，要传地址过去。CreateNode是最开始写的一个创建节点的函数。

我们用前序打印一下这个二叉树。

int main()
{
	char arr[] = {"ABD##E#H##CF##G##"};
	int i = 0;
	BTNode* Tree = CreateBT(&arr, &i);

	Preorder(Tree); //前序
	printf("\n");

	return 0;
}

​

也可以试试中序、后序、层序遍历。

​

本次分享就到这里，我们下篇见~