【数据结构】基础：二叉树

【数据结构】基础：二叉树基础

摘要：本文将会介绍二叉树的基础内容，首先引入树的概念，了解树的基本概念与性质，再对二叉树的概念和性质进行分析，最后对其方法进行实现，最重要的是理解对于二叉树方法实现的分治思想。

---

一、树的概述

1.1 树的概念

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

有一个特殊的结点，称为根结点，根节点没有前驱结点，除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继，因此，树是递归定义的。

注意：

• 子树是不相交的，树形结构中，子树之间不能有交集，否则就不是树形结构
• 除根节点外，每个结点有且仅有一个父节点
• 一棵N个节点的数有N-1条边

1.2 树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度；

叶节点或终端节点：度为0的节点称为叶节点；

非终端节点或分支节点：度不为0的节点；

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；

兄弟节点：具有相同父节点的节点互称为兄弟节点；

树的度：一棵树中，最大的节点的度称为树的度；

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次；

堂兄弟节点：双亲在同一层的节点互为堂兄弟；

节点的祖先：从根到该节点所经分支上的所有节点；

子孙：以某节点为根的子树中任一节点都称为该节点的子孙；

森林：由m（m>0）棵互不相交的树的集合称为森林；

1.3 树的表示方法

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。以下通过来介绍一下孩子兄弟表示法：

typedef int DataType;
struct Node{
	struct Node* _firstChild1; // 第一个孩子结点
	struct Node* _pNextBrother; // 指向其下一个兄弟结点
	DataType _data; // 结点中的数据域
};
1
2
3
4
5
6

二、二叉树概述

2.1 二叉树的概念

一棵二叉树是结点的一个有限集合，该集合要么为空，要么由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

注意：

• 二叉树不存在度大于2的结点
• 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

2.2 特殊的二叉树

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

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

2.3 二叉树的性质

• 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2 ^(i - 1)个结点

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

• 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为n2 ,则有 n0＝ n2＋1

• 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log(n+1) (ps： 是log以2为底，n+1为对数)

• 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有

  若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

  若2i+1=n否则无左孩子

  若2i+2=n否则无右孩子

2.4 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构

• 顺序存储

  顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，堆的内容可以参考博客http://t.csdn.cn/VsaOe。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

• 链式存储

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

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode{
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

三、二叉树方法实现

3.1 概述

二叉树的实现方式主要有两种，分别为通过顺序结构与链式结构实现。

对于顺序结构来说普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费，而完全二叉树更适合使用顺序结构存储，实际上通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段，堆的主要实现可以参考博客：http://t.csdn.cn/VsaOe。

而本文主要介绍链式结构的实现，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。而二叉树的结构设计，是采用了分治的方法管理的，每一个节点管理着链接自身的子树，因此对于递归的思想，在二叉树实现中非常重要。

3.2 前置准备

在实现二叉树前，先不对直接实现对二叉树的创建难度是比较大的，因此在此先写死一个二叉树的创建，通过对二叉树的部分功能实现后，再对二叉树的创建进行实现。在创建之前，为了方便节点的创建，先封装成一个函数，如下是二叉树节点结构体与节点创建的代码：

typedef int BTDataType;
struct BinaryTreeNode {
	BTDataType val;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
};
typedef struct BinaryTreeNode BinaryTreeNode;
1
2
3
4
5
6
7

BinaryTreeNode* BuyBinaryTreeNode(BTDataType val) {
	BinaryTreeNode* ptemp = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
	if (ptemp == NULL) {
		perror("malloc BinaryTreeNode failed");
		exit(1);
	}
	ptemp->val = val;
	ptemp->right = NULL;
	ptemp->left = NULL;

	return ptemp;
}
1
2
3
4
5
6
7
8
9
10
11
12

现在通过代码写死一棵二叉树，图示与代码如下：

BinaryTreeNode* Test_CreateBinaryTree() {
	BinaryTreeNode* node1 = BuyBinaryTreeNode(1);
	BinaryTreeNode* node2 = BuyBinaryTreeNode(2);
	BinaryTreeNode* node3 = BuyBinaryTreeNode(3);
	BinaryTreeNode* node4 = BuyBinaryTreeNode(4);
	BinaryTreeNode* node5 = BuyBinaryTreeNode(5);
	BinaryTreeNode* node6 = BuyBinaryTreeNode(6);
	BinaryTreeNode* node7 = BuyBinaryTreeNode(7);
	BinaryTreeNode* node8 = BuyBinaryTreeNode(8);

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node3->left = node6;
	node3->right = node7;
	node4->left = node8;

	return node1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.3 遍历

所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。

前、中、后序遍历

前中后序指的是对于根访问的顺序，而对于左右子树的顺序，是左子树优先于右子树，因此对其中的总结如下：

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

如下图所示，我们对其前中后序排列进行举例：

而对于通过前中后序遍历的实现，可以利用树的结构来实现，以前序遍历举例，先访问根，再访问左右子树，而对于左右子树而言，也是同样的思路，因此我们可以将其进行分治，使用递归实现，而递归结束的标志是没有节点在继续访问，因此当下一个子树为空时，就不再进行访问，对于代码的实现如下：

void PreOrder(BinaryTreeNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	// do something
	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
	return;
}

void InOrder(BinaryTreeNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	// do something
	printf("%d ", root->val);
	InOrder(root->right);
	return;
}

void PostOrder(BinaryTreeNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	// do something
	printf("%d ", root->val);
	return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

层级遍历

二叉树的层序遍历需要通过队列数据结构来实现，首先将根节点放入，进入循环，当队列不为空时，出队列，获取队头元素，并将其子节点推入队列中，以此类推，直到队列中没有元素。其中的原理是，在访问结点时会将子节点推到队尾，而在其之前的节点早已建立了相应的顺序，可以实现层序遍历。在此对齐进行一个小改进，就是使其可以一层一层的访问，在函数中增添一个参数，统计每一层的节点数量，当参数不断自减，当为零时表示访问完毕并对下一层访问，代码实现如下：

void BinaryTreeLevelOrder(BinaryTreeNode* root) {
	int levelSize = 0;
	Queue* queue = (Queue*)malloc(sizeof(Queue));
	if (queue == NULL) {
		perror("Queue: malloc failed!");
		exit(1);
	}
	QueueInit(queue);
	if (root == NULL) {
		return;
	}
	QueuePush(queue, root);
	levelSize = 1;
	while (!isQueueEmpty(queue)) {
		while (levelSize--){
			BinaryTreeNode* cur = QueueFront(queue);
			QueuePop(queue);
			//do something
			printf("%d ", cur->val);
			if (cur->left != NULL) {
				QueuePush(queue, cur->left);
			}
			if (cur->right != NULL) {
				QueuePush(queue, cur->right);
			}
		}
		levelSize = QueueSize(queue);
		printf("\n");
	}
	QueueDestory(queue);
	return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

3.4 节点个数

对于统计二叉树的节点个数，很多人第一反应是安装遍历的思路逐个遍历，计数即可，但实际上在细节上很多人会忽略函数栈帧的问题，因此建立临时变量进行统计，可实际上当函数栈帧销毁是，局部变量退出作用域后回销毁，因此无法达到计数的目的。为此会有对此改进，进行一个全局变量的设置，不过当有多个统计节点函数同时调用时，容易出现错误。在此采用另一种思路，同样采取分治的策略，对于每个子树的根来说，统计的是左右子树的节点个数。从根开始，逐级递归统计左右子树的节点数目，当遇到空子树时返回0并结束递归，当返回时返回左右子树节点之和以及自身，代码示例如下：

int BinaryTreeSize(BinaryTreeNode* root) {
	return root == NULL ?
		0 : BinaryTreeSize(root->right) + BinaryTreeSize(root->left) + 1;
}
1
2
3
4

3.5 叶子结点个数

同样采用分治的策略，对于每棵子树都统计其左右子树的叶节点的个数，当遇到空子树时返回0，当遇到叶子节点时返回1，代码示例如下：

int BinaryTreeLeafSize(BinaryTreeNode* root) {
	if (root == NULL) {
		return 0;
	}
	if (root->right == NULL && root->left == NULL) {
		return 1;
	}
	return BinaryTreeLeafSize(root->right) + BinaryTreeLeafSize(root->left);
}
1
2
3
4
5
6
7
8
9

3.6 树的高度

同样采用分治策略，分别统计左右子树高度，返回最深者，当遇到空树时返回0，否则返回最大高度与这身高度之和。需要注意的是，这里要将统计好的高度保存下来，否则会出现重复运算的问题，对于递归算法来说，时间复杂度是较大的，因此要尽量避免重复计算情况。以下将会提供错误写法与正确写法：

int BinaryTreeHeight(BinaryTreeNode* root) {
	if (root == NULL) {
		return 0;
	}
	int leftTreeHeight = BinaryTreeHeight(root->left);
	int rightTreeHeight = BinaryTreeHeight(root->right);
	return leftTreeHeight > rightTreeHeight ? leftTreeHeight + 1 : rightTreeHeight + 1;
}
// 错误写法
int BinaryTreeHeight(BinaryTreeNode* root) {
	if (root == NULL) {
		return 0;
	}
	return  BinaryTreeHeight(root->left) > BinaryTreeHeight(root->right)
		? BinaryTreeHeight(root->left) + 1 : BinaryTreeHeight(root->right) + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.7 第k层的节点个数

同样采用分治的策略，如果要统计某k层的节点数，需要从根节点出发，分治给下层节点统计某 k -1 层的节点数，以此类推，直到为1层数时，进行统计，空节点算0，其他节点算1，代码示例如下：

int BinaryTreeLevelKSize(BinaryTreeNode* root, int k) {
	if (root == NULL)
		return 0;
	if (k == 1) {
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
1
2
3
4
5
6
7
8

3.8 方法总结

对于二叉树的各种方法实现，使用到最多的就是递归，换句话说就是使用了分治的思想，因此面对其他问题实现时，可以考虑能否使用二叉树的链式结构特点，通过将问题转换为子方法实现与父方法整合的方向，从而实现递归解决。

---

补充：

1. 代码将会放到：C++/C/数据结构代码链接 ，欢迎查>看！
2. 欢迎各位点赞、评论、收藏与关注，大家的支持是我更新的动力，我会继续不断地分享更多的知识！