二叉树专题（有关二叉树的相关学习）

二叉树

1.数概念及结构

1.1树的结构

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因

为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 有一个特殊的结点，称为根结点，根节点没有前驱结点

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

• 因此，树是递归定义的

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

1.2树的相关概念

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

1.3树的表示

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

的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

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

其实也可以叫做左孩子右兄弟法

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

1.4 树在实际中的运用

表示文件系统的目录树结构

还有就是我们window系统的C盘D盘之类的也是目录树结构

2.二叉树概念及结构

2.1概念

一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空

2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

由图中我们可以知道：

1. 二叉树不存在度大于2的结点

2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

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

2.2特殊的二叉树

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

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

完全二叉树简单概括来说就是：前k-1层都必须是满的，第k层的所有节点从左到右一定得是连续的，可以不满。

满二叉树是完全二叉树的其中一种情况，完全二叉树又是二叉树的其中一种情况，二叉树又是数的其中一种情况。

2.3二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个节点
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h - 1个结点
3. 对任何一棵二叉树, 如果叶结点个数为n0，度为2的分支节点个数是n2，那么有公式n0 = n2 + 1

如图所示：

• 左边满二叉树的叶结点为8个，度为2的分支节点是7个 。 8 = 7 +1。
• 右边的完全二叉树，叶节点是5个，度为2的分支节点是4个。5 = 4 + 1。

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

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

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

• 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子

• 若\2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

我们来看几个选择题：

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

A 不存在这样的二叉树

B 200

C 198

D 199
1
2
3
4
5
6
7
8
9

这道题用前面我们总结的性质可以解决 n0 = n2 + 1。

2.下列数据结构中，不适合采用顺序存储结构的是（）

A 非完全二叉树

B 堆

C 队列

D 栈
1
2
3
4
5
6
7
8
9

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

A n

B n+1 

C n-1 

D n/2
1
2
3
4
5
6
7
8
9

我们知道n0 = n2 + 1。 我们设叶节点个数为x，那么度为2的节点个数为x -1，这里又是完全二叉树，可能会存在一个度为1的分支节点，但是总个数又是2n，是偶数，因此这里的度为1的分支结点肯定存在，因此最后的公式就是：x + x - 1 + 1 = 2n

如图所示，完全二叉树可能存在度为1的分支节点

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

A 11

B 10

C 8

D 12
1
2
3
4
5
6
7
8
9

根据二叉树的节点数和层数对应的公式就可以解决 ，如果前9层是满的，即2^9 - 1个 = 255个，第10层可以容纳 2^(10-1)个结点，也就是最多512个结点。因此剩下的，531-255 = 276个结点都放在第10层了。

5.一个具有767个节点的完全二叉树，其叶子节点个数为（）

A 383

B 384

C 385

D 386
1
2
3
4
5
6
7
8
9

由于是完全二叉树，节点总数又是奇数，因此不存在度为1的分支节点。我们设叶结点个数为 x， 则度为2的分支节点的个数是 x -1. 因此：x + x - 1 = 767.

x = 384。

答案：B A A B B
1

2.4 二叉树的存储结构

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

2.4.1顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

如图所示

如果我们用数组来表示树，我们需要将树的节点的通过下标来记载到数组中，但是如果不是完全二叉树的话，数组就会浪费非常多的空间。数组必须有很多空着不用的空间，代表这个地方没有数节点。

如果是完全二叉树的话，就会非常高效，不仅仅是数组的空间上没有浪费，而且数组的下标非常有规律，很好找到二叉树对应的树节点

• 父亲的节点下标是 i
• 该父亲节点的左孩子的节点的下标是 2 * i + 1 。
• 该父亲节点的右孩子的节点的下标是 2 * i + 2 。

不仅可以通过父亲节点下标算孩子节点下标，还可以通过孩子节点下标算父亲节点的下标。

• 孩子的节点下标是 i
• 父亲的节点下标是 (i - 1) / 2 【这样两个孩子都能找到自己的父亲】

2.4.2链式存储

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

我们来和这两个结构“打个招呼”。

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
15
16

3.二叉树的顺序结构及实现

3.1二叉树的顺序结构

前面我们也提到过，普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

这里需要知道，堆的逻辑结构是完全二叉树，是非线性的，但是堆的底层是用数组实现的，因此物理结构上是线性的

我们来看一个图片，可以更好的理解在数组中存储的完全二叉树：

但是这个数组里面存储的是一个完全二叉树，但是它不是堆、数组建堆主要依靠的就是——向下调整算法【前提是左右子树是对应的堆】

3.2堆的概念及结构

堆的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值
• 堆 总是一个完全二叉树

我们来看看大堆和小堆的图：

知道了堆的相关知识后，我们可以来做点选择题：

1.下列关键字序列为堆的是：（）
A 100,60,70,50,32,65
B 60,70,65,50,32,100
C 65,100,70,32,50,60
D 70,65,100,32,50,60
E 32,50,100,70,65,60
F 50,100,70,65,60,32

2.已知小根堆为8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次
数是（）。
A 1
B 2
C 3
D 4

3.一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为
A(11 5 7 2 3 17)
B(11 5 7 2 17 3)
C(17 11 7 2 3 5)
D(17 11 7 5 3 2)
E(17 7 11 3 5 2)
F(17 7 11 3 2 5)

4.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是（）
A[3，2，5，7，4，6，8]
B[2，3，5，7，4，6，8]
C[2，3，4，5，7，8，6]
D[2，3，4，5，6，7，8]

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

答案是：

A C C C
1

3.3堆的实现

我们这里实现的是 ----小堆-----

#pragma once
#define  _CRT_SECURE_NO_WARNINGS 1
# include<stdio.h>
# include<stdlib.h>
# include<assert.h>
# include<string.h>

// 这里我们实现的是  小堆


// 定义堆的结构
typedef int HPDatatype;
typedef struct Heap
{
	HPDatatype* _a; // 堆是用数组存储的(这里用动态顺序表)
	int _size;
	int _capacity; 
}Heap;


// 堆的接口

// 树节点的调换
void Swap(HPDatatype* child, HPDatatype* parent);

// 堆向下调整算法
void AdjustDown(HPDatatype* a, int n, int root);

// 堆的初始化
void HeapInit(Heap* php, HPDatatype* a, int n);// HPDatatype* a就是一个存放数据的数组的指针

// 堆的排序
void HeapSort(HPDatatype* a, int n);

// 堆的销毁
void HeapDestory(Heap* php);

// 向上调整算法
void AdjustUp(HPDatatype* a, int n, int child);

// 堆的插入
void HeapPush(Heap* php, HPDatatype x);

// 堆的删除 【这里删除的数据是要删除堆顶的数据】
void HeapPop(Heap* php);

// 堆的打印
void HeapPrint(Heap* php);

// 获取堆顶的数据
HPDatatype HeapTop(Heap* php);

// 获取堆的数据个数
int HeapSize(Heap* php);

// 判断堆是否为空
int HeapEmpty(Heap* php); // 是空的就返回1 不是空的就返回0
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

在实现堆之前，我们要先学习堆向下调整算法，才能实现堆。

我们这里实现的是小堆

3.3.1堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};
1

由于我们实现的是小堆，我们假设堆顶的数据是27，那么他就会去和左孩子去对比，假如比左孩子大，那么就会互换位置，然后再去和左孩子去对比 。以此类推…

那我们来看看这个算法和思路要如何通过代码实现呢？

如图所示，我们虽然是在对树进行操作，但是实际上我们是在对数组进行操作。因此我们需要通过操作数组的下标来实现我们的堆向下调整算法。

而前面我们学习过，在完全二叉树中，想找到父节点的左孩子的和右孩子都是有对应的公式的。 那就是 父节点下标 * 2 + 1 或者 父节点下标 * 2 + 2，对应找到左孩子和右孩子

我们来看看代码如何实现：

void Swap(HPDatatype* child, HPDatatype* parent)
{
	HPDatatype tmp = *parent;
	*child = *parent;
	*parent = tmp;
}

// 前提：左右子树都是小堆
void AdjustDown(HPDatatype* a, int n, int root) // root是传进来结点的下标, n是数组的元素个数
{
	int parent = root; // 既然要向下调整，那传进来的节点就是父节点，让其和孩子节点去对比
	int child = parent * 2 + 1; // 默认是左孩子

	// 交换可能要交换很多次，因此只要孩子节点的下标没有超出最后一个节点的下标，就不能退出循环
	while (child < n)
	{
		// 判断左右孩子谁更小  
		if (child + 1 < n && a[child] > a[child + 1]) // 要注意如果只有左孩子没有右孩子，那么要小心child + 1会越界，因此需要child + 1也小于n
		{
			child++;// 如果右孩子小，那就让孩子更改成右孩子
		}
		
		// 现在要让父节点和孩子节点对比
		// 现在孩子节点是左右孩子节点中最小的，让其和父节点进行对比
		if (a[parent] > a[child])
		{
			// 如果父节点大，就交换
			Swap(&a[child], &a[parent]);

			// 由于不止交换一次，因此需要迭代，更新child和parent节点
			parent = child; // 交换完之后父亲节点交换到孩子节点了。
			child = child * 2 + 1;  // 让孩子节点指向新的孩子节点， 默认左孩子 
		}
		else
		{
			// 走这里说明父节点小于孩子节点，那就不用再交换了。
			break;
		}
	}

}
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
36
37
38
39
40
41

但是，我们知道，使用这个算法的前提是：左右子树都是小堆。

因此我们还需要将左右子树先搞成小堆先

3.3.2堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆

其实原始一点的思路是这样的，我们既然知道要将左右子树都弄成堆，但是左右子树又有可能有下一个左右子树，因此不如直接从数组的最后一个元素下标开始调整，也就是从叶子结点开始调整【其实不用调整】，这样走到第一个父节点就可以顺利使用堆向下调整算法，以此类推。 我们可以来看一个图：

这样子我们在调整倒数的子树的时候其左右子树都是堆的形式出现。就可以保证前提：左右子树都是堆

这样思路下的代码是这样的：

	// 建堆
	for (int i = n - 1; i >= 0; i--) 
	{
		// 从最后一个子树开始调整 【叶节点可以看做是一个度为0的子树】
		AdjustDown(a, n, i);
	}
1
2
3
4
5
6

但是我们发现，对叶节点进行堆向下调整算法，是没有意义的，因此我们可以通过找到倒数第一个父节点，也就是从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆

我们来看看代码是如何实现的：

	// 构建堆（向下调整算法[前提是：左右子树都是小堆]）
	// 因此我们要先把左右子树搞成小堆  如何搞呢？ 其实从树中最小的子树开始调整就行
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) // (n - 1 - 1) / 2 找到的就是倒数第一个父节点
	{
		AdjustDown(php->_a, n, i); // 从倒数第一个子树开始调整成小堆，让每一个子树都变成小堆
	}

1
2
3
4
5
6
7

我们现在已经知道了一个堆要如何创建出来了，那我们来看看堆的初始化代码。

先知道堆的创建过程，再去看初始化过程，会比较好理解。

3.3.3堆的初始化代码：

// 堆的初始化
void HeapInit(Heap* php, HPDatatype* a, int n) // HPDatatype* a就是一个存放数据的数组的指针
{
	// 给数组开辟n个大小为HPDatatype的空间 
	php->_a = (HPDatatype*)malloc(sizeof(HPDatatype) * n);
	if (php->_a == NULL)
	{
		perror("HeapInit():malloc()");
		exit(-1);
	}

	// 往堆中存放数据
	memcpy(php->_a, a, sizeof(HPDatatype) *n);// 意思是说从a这个指针处，传递sizeof(HPDatatype)* n个字节到php->_a处
	php->_size = n;
	php->_capacity = n;

	// 这个时候只是把数据放进了数组中，但是还不是堆
	// 不仅仅要把数据存放进去，还要将里面的数据变成堆的形式去存放
	
	// 构建堆（向下调整算法[前提是：左右子树都是小堆]）
	// 因此我们要先把左右子树搞成小堆  如何搞呢？ 其实从树中最小的子树开始调整就行
	for (int i = (n - 1 - 1) / 2; i >= 0; --i) // (n - 1 - 1) / 2 找到的就是倒数第一个父节点
	{
		AdjustDown(php->_a, php->_size, i); // 从倒数第一个子树开始调整成小堆，让每一个子树都变成小堆
	}

}
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

测试代码：

int main()
{
    // 给一个完全二叉树
	int array[] = { 27,15,19,18,28,34,65,49,25,37 };
	Heap hp;
	HeapInit(&hp, array, sizeof(array) / sizeof(array[0]));

	return 0;
}
1
2
3
4
5
6
7
8
9

经过调试，该二叉树已经变成了小堆。如图所示：

哪怕是给一个很乱的完全二叉树，也能实现小堆的创建。

用这样方式会更加直观：

3.3.4堆栈的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的是近似值，多几个节点不影响最终结果

	// 构建堆（向下调整算法[前提是：左右子树都是小堆]）
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) 
	{
		AdjustDown(php->_a, n, i); // 从倒数第一个子树开始调整成小堆，让每一个子树都变成小堆
	}
1
2
3
4
5

这里的时间复杂度？
如果树有N个节点，树的高度就是：logN （以2为底）
那么一次向下调整算法的时间复杂度就是 logN
但是要注意 这里的时间复杂度不是 N*logN

如果是AdjustDown(a, n, 0);就是N * logN 因为从根结点开始

实际的时间复杂度需要我们来计算和分析：

我们假设一个节点调用向下调整算法的移动步数取决于当前所处的高度。

因此：建堆的时间复杂度为O(N)

3.3.5堆的排序

对上面的建堆有了一定的了解和学习之后，我们现在已经能够构建出一个堆了。

但是这个堆还不是有序的，那我们如果想搞一个有序的小堆或者是大堆要怎么做呢

我们可以通过让每一个节点都去建堆，这样每一个节点都是当前树的最小值/最大值，这样就可以实现升序/降序。

但是这样的时间复杂度就是 O（N^2）。 每次建堆的时间复杂度是： O（N），让每个节点都去建堆。就是O（N^2）

因此我们可以采用一个方法，效率较高的：

我们先看图：

经过一次这样的处理，我们可以选出一个次小的数，然后让次小的数换到倒数第二个位置，堆的大小变成n-2.

然后继续处理，以此类推。这样我们的数组存放的就是降序的堆、

这里我们是通过向下调整算法去选出一个树里面最小的数的，因为向下调整的树是小堆，小堆的堆顶是该子树的最小数字。

我们也知道向下调整算法的时间复杂度是O(logN)，因此通过这个方式我们的时间复杂度是 O(N * logN)。因为我们一共需要调整N次。

比时间复杂度O（N^2）的效率高了非常多。

N越大，优势就会越大。

代码实现：

	
void HeapSort(HPDatatype* a, int n)
{
	// 构建堆（向下调整算法[前提是：左右子树都是小堆]）
	// 如果树有N个节点，树的高度就是：logN （以2为底）
	// 那么一次向下调整算法的时间复杂度就是 logN
	// 可以通过计算得知这里的时间复杂度是： O（N）
	for (int i = (n-1 - 1) / 2; i >= 0; i--) // (n-1 - 1) / 2 找到的就是倒数第一个父节点 第一个n-1是其孩子节点下标
	{
		AdjustDown(a, n, i); // 从倒数第一个子树开始调整成小堆，让每一个子树都变成小堆
	}

	// 走到这里数组a存储的完全二叉树已经是一个小堆了。
	// 此时的堆还不是有序的
	
    // 排序
	int end = n - 1; // end表示倒数第一个节点的下标
	while (end > 0)
	{
		// 交换，把堆顶（最小的数）放到最后面去，然后忽略掉
		Swap(&a[end], &a[0]);

		// 调用堆向下调整算法
		AdjustDown(a, end, 0); // 让堆顶（下标为0）变成次小的数
		// 这里的end是当做a数组的元素个数传进去的，最后一个元素不会参与比较

		end--; // 忽略掉最后面那个最小的数
	}
	// 由于我们的堆构建，构建的是小堆，因此这里的堆排序排出来是降序
	// 如果我们想要排升序，就构建大堆就行了。

}
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

测试代码：

int main()
{
	int array[] = { 27,15,19,18,28,34,65,49,25,37 };

	HeapSort(array, sizeof(array) / sizeof(array[0]));
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
    // 
    // 构建小堆 排降序：65 49 37 34 28 27 25 19 18 15 
    // 构建大堆 排升序：15 18 19 25 27 28 34 37 49 65
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

构建大堆只需要在向下调整算法的时候，把两个小于号改成大于号就好了

if (child + 1 < n && a[child] < a[child + 1]) 
{
	child++;
}
// 现在要让父节点和孩子节点对比
// 现在孩子节点是左右孩子节点中最大的，让其和父节点进行对比
if (a[parent] < a[child])
{
	// 如果父节点小，就交换
	Swap(&a[child], &a[parent]);

	// 由于不止交换一次，因此需要迭代，更新child和parent节点
	parent = child; 
	child = child * 2 + 1;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这样就行了，其他地方不需要有任何的变化~

3.3.6堆的销毁

我们需要将我们申请的动态内存空间释放掉，也就是数组的空间。

代码如下：

void HeapDestory(Heap* php)
{
	assert(php); // 如果php是NULL还怎么销毁

	free(php->_a);
	php->_a = NULL;
	php->_size = php->_capacity = 0;

}
1
2
3
4
5
6
7
8
9

3.3.7堆的插入

堆的插入，不能是头插，不仅效率低下【因为是数组实现】，而且会导致父亲节点和孩子节点的关系全乱了。

因此我们需要尾插到堆中，但是堆既然称之为堆，那就是因为堆有其性质，因此插入数据之后不能不管它，我们需要去调整它，保证我们堆的性质不变。

插入数据会有两种情况：

• 第一种就是插入后，数据刚好不会改变堆的性质，比如小堆，插入的数据，刚好比父亲节点大，那么此时无需改变
• 第二种，就是插入后数据改变了堆的性质，比如，在小堆插入的数据，比父亲节点小，这个时候我们就需要去调整它

既然如此，我们就需要先编写一个向上调整算法。

3.3.7.1向上调整算法

如图所示，就是让这个插入节点去和父亲节点对比，如果小于父亲节点就交换，一直交换到符合小堆的性质为止。

代码如下:

// 向上调整算法
void AdjustUp(HPDatatype* a, int n, int child)
{
	// 找父亲节点
	int parent = (child - 1) / 2;

	while (child > 0) // 当孩子节点 == 0 的时候，就说明已经交换到堆顶了，无需在比较了
	// 注意这里的条件不能是 parent >= 0 因为parent永远不可能 < 0。因为parent是int类型 当child = 0的时候，parent = (child - 1) / 2 还是等于0
	{
		// 判断父亲节点和孩子节点谁大
		if (a[child] < a[parent])
		{
			// 孩子节点小就交换
			Swap(&a[child], &a[parent]);
			// 迭代，更新孩子节点和父亲节点的下标
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}

}
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

知道了向上调整算法之后，我们来看看堆的插入

3.3.7.2 堆的插入

代码如下：

// 堆的插入
void HeapPush(Heap* php, HPDatatype x)
{
	assert(php);

	// 先将其插入到数组的最后一个位置。也就是尾插到堆内，让完全二叉树多出一个叶结点
	// 要先判断是否有足够的空间
	if (php->_capacity == php->_size)
	{
		// 增容 (增2倍)
		int newcapacity = php->_capacity == 0 ? 4 : php->_capacity * 2;
		HPDatatype* tmp = (HPDatatype*)realloc(php->_a, sizeof(HPDatatype) * newcapacity);
		if (tmp == NULL)
		{
			perror("HeapPush():realloc()");
			exit(-1);
		}

		// 更新
		php->_a = tmp;
		php->_capacity = newcapacity;
	}

	// 走到这里空间足够插入了
	// 插入
	php->_a[php->_size] = x; // php->_size如果空间不够是会越界的
	php->_size++;

	// 插入数据之后，不能不管，我们还要保持这个堆的性质。
	// 这个数据插入进去可能刚好还是小堆，也有可能导致不是小堆了
	// 因此这里需要一个 向上调整算法 【如果插入的数很小，就要让其往上走[因为我们实现的是小堆]】

	AdjustUp(php->_a, php->_size, php->_size - 1);//php->_size - 1 是插入数据的下标
	
}
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

测试代码：

	// 堆的插入
	HeapPush(&hp, 10);
	HeapPush(&hp, 11);
	HeapPush(&hp, 12);
	//HeapSort(hp._a, hp._size);
	for (int i = 0; i < hp._size; i++)
	{
		printf("%d ", hp._a[i]);
	}
	printf("\n");
1
2
3
4
5
6
7
8
9
10

测试代码执行结果如下：

10 15 11 25 18 12 65 49 27 37 28 34 19
1

这样看更加清晰，我们的堆在插入数据之后仍然是小堆，虽然不是有序，但是想让其有序，只需要调用一次堆排序函数就行。

3.3.8 堆的打印

这个非常简单，根据堆自带的size，去打印就行

代码如下：

// 堆的打印
void HeapPrint(Heap* php)
{
	assert(php);
	assert(php->_size > 0); // 没有数据，还打印个集贸

	for (int i = 0; i < php->_size; i++)
	{
		printf("%d ", php->_a[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

3.3.9堆的删除

这里的堆的删除，指的是将堆的堆顶的数据删除。

但是不能直接让数组后面的数据往前面覆盖，因为这样子不仅时间复杂度是O(N),而且会导致父节点和孩子节点的关系全部打乱！

因此这里我们采取和堆排序类似的思路

• 首先让堆顶数据和堆最后的数据交换
• 然后size–，这样就相当于删除
• 然后对堆顶使用一次堆向下调整算法

知道了思路之后，我们来看看代码是如何实现的：

// 堆的删除
void HeapPop(Heap* php)
{
	assert(php);
	assert(php->_size > 0); // 如果堆都没有数据，还删除个dan

	// 交换堆顶和最后一个节点
	Swap(&php->_a[0], &php->_a[php->_size - 1]); // php->_size - 1 就是最后一个数据的下标

	// 删除堆顶数据
	php->_size--;

	// 对堆顶使用堆向下调整算法
	AdjustDown(php->_a, php->_size, 0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

测试代码：

	//10 15 11 25 18 19 65 49 27 37 28 34	
	// 堆的删除
	HeapPop(&hp);
	HeapPop(&hp);
	HeapPrint(&hp); // 15 18 19 25 28 34 65 49 27 37
1
2
3
4
5

可以看到删除了10 和 11 说明删除的都是堆顶的数据，并且每删除一次，到堆顶上去的数据都是次小的数据

3.3.10堆顶数据的获取

这个也非常简单。代码如下：

// 获取堆顶的数据
HPDatatype HeapTop(Heap* php)
{
	assert(php);
	assert(php->_size > 0);

	return php->_a[0];
}
1
2
3
4
5
6
7
8

• 这里有个拓展问题，堆的TopK问题。

3.3.11堆的数据个数

很简单，代码如下：

// 获取堆的数据个数
int HeapSize(Heap* php)
{
	assert(php);

	return php->_size;
}

1
2
3
4
5
6
7
8

3.3.12堆的判空

很简单，代码如下：

// 判断堆是否为空
int HeapEmpty(Heap* php) // 是空的就返回1 不是空的就返回0
{
	if (php->_size == 0)
		return 1;
	else
		return 0;
}
1
2
3
4
5
6
7
8

3.4堆的应用

3.4.1堆的排序

在前面的3.3.5讲的很清楚是如何实现的。

3.4.2堆的TopK问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

意思就是选出堆的 前K个 最小的/最大的 数。

第三个思路的时间复杂度是 O(N+ logK) 如果k很小，那近似于O(N)

其实就是建一个k个数的大堆或者小堆，

• 如果我们要找最大的前k个数，那就要建小堆
• 如果我们要找最小的前k个数，那就要建大堆

这个非常重要，假设我们要找最大的前k个数，那么我们建k个数的小堆，然后让数去进堆，能进去的说明肯定比堆顶大。因此最后留在这个k个数的小堆里面的数，就是最大的k个数，堆顶的是就是第k大的数。

假设我们要找最小的前k个数，我们就要建k个数的大堆，让数去和堆顶判断，只要比堆顶小，那我就进堆，这样子的话，最小的前k个数最后都会留在这个大堆中，堆顶就是第k小的数。

我们来看一道有关TopK的面试题：

面试题 17.14. 最小K个数

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]
1
2

提示：

• 0 <= len(arr) <= 100000
• 0 <= k <= min(100000, len(arr))

思路就是我们前面所讲的思路

代码如下:

void AdjustDown(int* a, int n, int root)
{
    // 找到孩子节点和父节点
    int parent = root;
    int child = parent*2 + 1; //默认是左孩子最大

    // 可能不止比较一次
    while(child < n)
    {
        // 判断是右孩子大还是左孩子大
        if(child + 1 < n && a[child + 1] > a[child])
        {
            child++;
        }

        // 让父节点去和最大的孩子去比较
        if(a[parent] < a[child])
        {
            // 孩子比父亲大，那就交换
            int tmp = a[child];
            a[child] = a[parent];
            a[parent] = tmp;

            // 迭代。
            parent = child;
            child = parent * 2 + 1; // ，默认左孩子
        }
        else
        {
            break;
        }
    } 
}

int* smallestK(int* arr, int arrSize, int k, int* returnSize)
{
    *returnSize = k;
    // 如果k是0 就说明不再需要操作了
    if(k == 0)
        return NULL;

    int* retArr = (int*)malloc(sizeof(int) * k); 
    // 首先我们先传k个数据到我们的数组中
    for(int i = 0; i < k; i++)
    {
        retArr[i] = arr[i];
    }

    // 这个时候的数据还不是堆
    // 由于我们要找最小的前k个数，因此我们需要建立一个大堆
    for(int i = (k-1 - 1)/2; i >= 0; i--)//  (k-1 - 1)/2是倒数第一个父节点
    {
        AdjustDown(retArr, k, i);
    }

    // 此时retArr是一个大堆。但是里面还不是arr里面最小的前k个数
    // 我们让后面的数据不断的去和我们retArr的堆顶去比较，一旦比堆顶小，那就进堆
    // 这样最后的堆里面剩下的，就是最小的k个数
    for(int i = k; i< arrSize; i++)
    {

        // 让arr里面的数据和 我们的大堆的堆顶去比较
        if(arr[i] < retArr[0])
        {
            // 比堆顶小就进堆
            retArr[0] = arr[i];
            // 但是这个数据成为堆顶之后，可能会破坏大堆
            // 因此我们需要让其保持大堆 让小的往下走
            AdjustDown(retArr, k, 0);
        }
    }

    // 走到这里，最小的前k个数就已经被我们选出来了

    return retArr;

}
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

4.二叉树链式结构的实现

#pragma once
#define  _CRT_SECURE_NO_WARNINGS 1
# include<stdio.h>
# include<stdlib.h>
# include<assert.h>


// 我们使用链式结构实现二叉树
// 定义一个二叉树节点的结构体

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;


// 申请二叉树的节点
BTNode* BTNodeCreate(BTDataType x);

// 二叉树前序遍历
void PreOrder(BTNode* root);

// 二叉树中序遍历
void InOrder(BTNode* root);

// 二叉树后序遍历
void PostOrder(BTNode* root);


// 层序遍历 (借助队列)
void LevelOrder(BTNode* root);


// 获取二叉树节点个数
int BinaryTreeSize(BTNode* root);

// 获取二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);

// 获取二叉树的深度
int BinaryTreeDepth(BTNode* root);

// 获取二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

// 判断二叉树是否是完全二叉树 （是就返回1 不是就返回0）
int BinaryTreeComplete(BTNode* root);

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi);

// 二叉树销毁
void BinaryTreeDestory(BTNode* root);
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

4.1前置声明

此处手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

申请二叉树节点的函数：

// 申请二叉树的节点
BTNode* BTNodeCreate(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("BTNodeCreate():malloc()");
		exit(-1);
	}

	newnode->_data = x;
	newnode->_left = NULL;
	newnode->_right = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

创建一颗伪树：

int main()
{

	// 我们这里创建一颗伪树 这里的代码并不是创建二叉树的方式
	BTNode* A = BTNodeCreate('A');
	BTNode* B = BTNodeCreate('B');
	BTNode* C = BTNodeCreate('C');
	BTNode* D = BTNodeCreate('D');
	BTNode* E = BTNodeCreate('E');

	// 将其链接起来成为一颗树
	A->_left = B;
	B->_left = D;
	B->_right = E;
	A->_right = C;

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

4.2二叉树的遍历

4.2.1前序、中序以及后序遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

如图所示，我们先来看看前序遍历：

前序遍历的顺序是： 根——左子树——右子树

遍历的思路是：

先访问A这个根结点，然后去找A结点的左子树，找到了B这个根结点，然后去找B的左子树，找到了D这个根结点，再去找D的左子树，发现找不到就退回去，然后去找D的右子树，然后也找不到，这个时候B的左子树访问完了。要去访问B的右子树，找到了E这个根结点，然后去找E的左子树，找不到，找E的右子树还是找不到，B的右子树访问完了。此时A的左子树也访问完了，这个时候访问A的右子树，找到C这个根节点，去找C的左子树，找不到，找右子树，找不到。此时A的左子树右子树都访问结束。

遍历结束

A——B——D——NULL——NULL——E——NULL——NULL——C——NULL——NULL

ABDEC

我们来看前序的代码实现：

// 二叉树前序遍历 [根 左子树 右子树]
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->_data); // 访问根
	PreOrder(root->_left); // 访问左子树
	PreOrder(root->_right); // 访问右子树
	// 多路递归，这里是 2路递归
}
1
2
3
4
5
6
7
8
9
10
11
12
13

代码中使用递归的过程如下图所示：

中序遍历和后序遍历：

中序遍历的顺序是： 左子树——根——右子树

遍历思路是这样的：

要想访问A这个根节点，需要先访问根的左子树，找到了B节点，但是要访问B节点要先访问B的左子树，找到了D结点，但是要先访问D节点的左子树

没找到节点，就访问D节点，然后访问D结点的右子树，没找到。此时B结点的左子树访问完了，那就访问B节点，然后去找B节点的右子树，找到了E节点，但是访问E节点之前，要先访问E节点的左子树，没找到，访问E节点，然后访问E节点的右子树，没找到，此时B结点的右子树访问完了。也是A节点的左子树访问完了

访问A节点，然后访问A节点的右子树，找到了C节点，访问C节点之前，要访问C节点的左子树，没找到，访问C节点，然后访问C节点的右子树，没找到，此时A节点的右子树访问完毕。

结束遍历.

NULL——D——NULL——B——NULL——E——NULL——A——NULL——C——NULL

DBEAC

中序的代码实现：

// 二叉树中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->_left);// 访问左子树
	printf("%c ", root->_data); // 访问根
	InOrder(root->_right);// 访问右子树
}
1
2
3
4
5
6
7
8
9
10
11
12
13

中序的调用思路如图所示：

后序遍历的顺序是：左子树——右子树——根

遍历思路是这样的：

想要访问A这个节点就要先访问A节点的左子树和右子树，先访问左子树，找到了B节点，要访问B节点就要先访问B节点的左子树，找到了D节点，要访问D节点就要先访问D节点的左子树，没找到，就访问D节点的右子树，没找到，这个时候才访问D节点。

这个时候B节点的左子树访问完了，访问B节点的右子树，找到了E节点，要访问E节点，就要先访问E节点的左子树，没找到，就访问E节点的右子树，没找到，访问E节点，这个时候B结点的左子树和右子树都访问完了，也是A节点的左子树访问完了。

这个时候要访问A节点的右子树，找到了C节点，要访问C节点，就要访问C节点的左子树和右子树，访问左子树，没找到，访问右子树，没找到，这个时候访问C节点，这个时候A节点的右子树访问完毕，访问A节点.

结束遍历。

NULL——NULL——D——NULL——NULL——E——B——NULL——NULL——C——A

DEBCA

后序的代码实现：

// 二叉树后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->_left);// 访问左子树
	PostOrder(root->_right);// 访问右子树
	printf("%c ", root->_data);// 访问根

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

后序的调用思路和前面两个是大同小异的，都是递归的运用。

总结：

这三个遍历都是深度优先的遍历

4.2.2层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

举个例子：

如图所示，如果是层序遍历，那遍历顺序是：

A——B——C——D——E——F——G——NULL——NULL——NULL——H——NULL——NULL——NULL——NULL。

思路：（借助队列）

1. 其实层序遍历二叉树，就不是用递归实现了，和之前的前序、中序、后序就没有什么关系了
2. 层序遍历需要借助队列的先进先出的特性。将根结点放进去，根结点出来的时候，要把其左右孩子依次放入队列。
3. 直至遍历到队列为空，此时二叉树就遍历完毕了

有关层序中借助的队列的定义和实现：

Queue.h

#pragma once
#define  _CRT_SECURE_NO_WARNINGS 1
# include<stdio.h>
# include<assert.h>
# include<stdlib.h>

// 这里的队列的底层数据结构是单链表
// 定义节点的结构体

#include"BinaryTree.h";

typedef BTNode* QDataType; // 以二叉树节点的指针作为数据存储类型
typedef struct QueueNode
{
	QDataType _data;
	struct QueueNode* _next;
}QueueNode;

// 和单链表不一样的是队列最好要有指向第一个节点和尾节点的指针
typedef struct Queue
{
	QueueNode* _head;
	QueueNode* _tail;
}Queue;


// 队列的接口（也就是函数） 
// 为什么这里的接口和单链表的时候不一样，不需要传二级指针呢，因为我们把指针放到了结构体内部，传的是结构体指针
// 通过结构体指针找到结构体，再从结构体内部拿到节点的指针，再从这个节点指针找到节点，这里起到的作用就类似于二级指针

// 队列的初始化
void QueueInit(Queue* pq);

// 队列的销毁
void QueueDestory(Queue* pq);

// 入队
void QueuePush(Queue* pq, QDataType x);

// 出队
void QueuePop(Queue* pq);

// 获取队头的数据
QDataType QueueFront(Queue* pq);

// 获取队尾的数据
QDataType QueueBack(Queue* pq);

// 判断队列是否为空  [返回1就是空，返回0就是非空]
int QueueEmpty(Queue* pq);

// 获取队列的数据个数
int QueueSize(Queue* pq);
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

层序中用到的接口的代码实现:

#include "Queue.h"

// 队列的初始化
void QueueInit(Queue* pq)
{
	assert(pq);//pq不能为NULL

	// 初始化
	pq->_head = NULL;
	pq->_tail = NULL;

}

// 队列的销毁
void QueueDestory(Queue* pq)
{
	assert(pq);

	// 遍历队列，删除每一个节点
	QueueNode* cur = pq->_head;
	while (cur) 
	{
		QueueNode* next = cur->_next;
		free(cur);
		cur = next;
	}

	pq->_head = pq->_tail = NULL;
}

// 入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	// 入队其实就是让新节点尾插到链表中
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("QueuePush():malloc()");
		exit(-1);
	}

	newnode->_data = x;
	newnode->_next = NULL;

	// 判断列队是否为空
	if (pq->_head == NULL)
	{
		pq->_head = pq->_tail = newnode;
	}
	else
	{
		// 尾插
		pq->_tail->_next = newnode;
		pq->_tail = newnode;
	}

}

// 出队
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->_head); // 队列是空的怎么出队

	// 头删
	QueueNode* next = pq->_head->_next; // 把第一个节点的下一个节点存储起来
	free(pq->_head);
	pq->_head = next;

	// 这里有个问题，当最后一个节点删除完之后，pq->_head = NULL
	// 但是pq->_tail 就变成野指针了
	if (pq->_head == NULL)
	{
		pq->_tail = NULL;
	}

}

// 获取队头的数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->_head);// 队列为空怎么获取队头数据

	return pq->_head->_data;
}

// 获取队尾的数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->_tail); // 等价于assert(pq->_head); 头为空，尾也肯定为空，

	return pq->_tail->_data;
}

// 判断队列是否为空 [返回1就是空，返回0就是非空]
int QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->_head == NULL ? 1 : 0;
}
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

层序的代码实现：

// 层序遍历(借助队列)
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	// 一开始根节点就是NULL就返回
	if (root == NULL)
		return;

	QueuePush(&q, root); //把根结点插入队列中
	while (!QueueEmpty(&q))
	{
		// 获取队头节点
		BTNode* frontnode = QueueFront(&q);
		QueuePop(&q); // 弹出队头

		printf("%c ", frontnode->_data);

		// 遍历完队头节点，要把该节点的左右子树依次插入队列
		// 如果左右子节点是NULL 就不放进去 层序遍历不打印NULL
		if (frontnode->_left) 
			QueuePush(&q, frontnode->_left);

		if (frontnode->_right)
			QueuePush(&q, frontnode->_right);
	}
	printf("\n");

	// 销毁队列
	QueueDestory(&q);
}
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

测试代码：

	// 层序遍历(借助队列)
	LevelOrder(A); // A B C D E
1
2

层序的遍历是广度优先的遍历

学习了二叉树的遍历之后，我们可以来做几个题来巩固一下：

1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（ ）
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA
    
2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为（）
A E
B F
C G
D H
    
3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。
A adbce
B decab
C debac
D abcde
    
4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列
为
A FEDCBA 
B CBAFED
C DEFCBA
D ABCDEF
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

答案是： A A D A 
1

4.3二叉树的节点个数

这里需要注意，由于我们是通过递归来实现的，因此之前的常规思路是不能实现的。

常规思路代码如下：

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	
	int size = 0;
	size++;

	BinaryTreeSize(root->_left);
	BinaryTreeSize(root->_right);

	return size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试代码如下：

	// 获取二叉树节点个数
	printf("%d\n", BinaryTreeSize(A)); // 1
	printf("%d\n", BinaryTreeSize(A)); // 1
1
2
3

因为每递归一次都会重新定义一次size，因此每次++加的都不是同一个size，是不同层数的递归函数内重新定义的size

因此要实现这个思路，我们需要定义一个全局变量。

代码如下：

// 二叉树节点个数
int size = 0;
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	
	size++;

	BinaryTreeSize(root->_left);
	BinaryTreeSize(root->_right);

	return size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试代码：

	// 获取二叉树节点个数
	printf("%d\n", BinaryTreeSize(A)); // 5
	printf("%d\n", BinaryTreeSize(A)); // 10
1
2
3

虽然这样确实是可以统计出二叉树的节点个数，但是由于是全局变量，我们会发现，调用完一次之后，不会消失，而是会累加，这样除非我们手动再去重置，不然再调用该函数就会出错。这样也不好。

既然如此，我们可以考虑指针的方式，传一个int 类型的指针，让其在函数内部不断改变，因为不是全局变量，调用完一次函数也会销毁。

代码如下：

// 二叉树节点个数
void BinaryTreeSize(BTNode* root, int* psize)
{
	if (root == NULL)
		return 0;
	else
		(*psize)++;


	BinaryTreeSize(root->_left, psize);
	BinaryTreeSize(root->_right, psize);

}
1
2
3
4
5
6
7
8
9
10
11
12
13

测试代码：

	// 获取二叉树节点个数
	int sizeA = 0;
	BinaryTreeSize(A, &sizeA);
	printf("%d\n", sizeA); // 5
	printf("%d\n", sizeA); // 5
1
2
3
4
5

这样确实可以解决问题，但是这样调用不方便呀。我们都觉得调用这个函数接口，你应该直接给我返回这个二叉树的节点个数，怎么还需要我去定义一个变量去使用呢？

因此我们用下面这个代码的思路，可以直接返回二叉树节点的个数。

• 二叉树的节点个数 = 根节点 + 左子树的节点个数 + 右子树的节点个数

代码如下：

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{	
	// 先看看是不是空树，并且判断root是否遍历到了NULL
	if (root == NULL)
		return 0;
	// 二叉树的节点个数 = 根节点 + 左子树的节点个数 + 右子树的节点个数
	else
		return 1 + BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right);
}
1
2
3
4
5
6
7
8
9
10

测试代码：

	// 获取二叉树节点个数
	printf("%d\n", BinaryTreeSize(A)); // 5
	printf("%d\n", BinaryTreeSize(A)); // 5
	printf("%d\n", BinaryTreeSize(B)); // 3
1
2
3
4

4.4二叉树叶子节点个数

关于这个叶子节点个数的获取，我们还是要通过递归的思想。

• 一个二叉树的叶子节点的个数 = 左子树的叶子节点个数 + 右子树的叶子节点个数

代码如下：

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	// 先判断是否是空树
	if (root == NULL)
		return 0;

	// 判断root是否是叶子结点，如果是，那么左右子树都是NULL
	if (root->_left == NULL && root->_right == NULL)
		return 1;

	// 一个根节点的叶子节点的个数相当于 左子树的叶子节点个数 + 右子树的叶子节点个数
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试代码如下：

	// 获取二叉树叶子节点个数 
	printf("%d\n", BinaryTreeLeafSize(A)); // 3
	printf("%d\n", BinaryTreeLeafSize(B)); // 2
1
2
3

4.5二叉树的深度

思路：

• 求出左子树的深度和右子树的深度，判断谁大， 大的就 + 1

代码如下：

// 获取二叉树的深度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;

	// 求出左子树 右子树 的深度
	int leftdepth = BinaryTreeDepth(root->_left);
	int rightdepth = BinaryTreeDepth(root->_right);

	// 判断谁大，谁大就 + 1
	return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试代码：

	// 获取二叉树最大深度
	printf("BinaryTreeDepthA:%d\n", BinaryTreeDepth(A)); // 3
	printf("BinaryTreeDepthB:%d\n", BinaryTreeDepth(B)); // 3
1
2
3

4.6二叉树第K层节点个数

思路：

当前树的第k层 可以转化成左右子树的第k - 1层， 当层数 == 1的时候，就不分解，返回1。

代表这里有一个节点，如果是NULL 就返回0.

代码：

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	// 如果传进来的根节点是NULL 直接返回0 代表没有节点
	if (root == NULL)
		return 0;

	// 判断是否分离到最后一层
	if (k == 1)
		return 1;

	// 当前树的第k层 可以转化成左右子树的第k - 1层
	// 第k层的节点个数 就是第k-1层的左右子节点个数,那我们就统计 k - 1层的左右子节点个数 
	// k = 1 的时候就说明此时层数 就是第k - 1层的左右子节点的层数 也就是我们要求的第k层
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

测试代码：

	// 获取二叉树第k层节点个数
	printf("BinaryTreeLevelKSize2:%d\n", BinaryTreeLevelKSize(A, 2)); // 2
	printf("BinaryTreeLevelKSize3:%d\n", BinaryTreeLevelKSize(A, 3)); // 2
1
2
3

4.7二叉树查找值为x的节点

思路：

• 遍历二叉树，查找x是否存在x的节点就行，有就返回该节点，没有返回NULL

代码：

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	// 前序遍历二叉树
	if (root->_data == x)
		return root;

	// 如果根结点没找到，就去左子树找
	BTNode* node = BinaryTreeFind(root->_left, x);
	if (node)// node没找到就是NULL  找到了就不是NULL
		return node;

	// 左子树也没找到就去右子树找
	node = BinaryTreeFind(root->_right, x);
	if (node)
		return node;

	// 走到这里就说明没找到
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

测试代码：

	// 二叉树查找值为x的节点
	BTNode* node = BinaryTreeFind(A, 'C');
	if (node)
		printf("BinaryTreeFind:%c\n", node->_data);// BinaryTreeFind:C
	else
		printf("NULL\n");
1
2
3
4
5
6

4.8二叉树基础oj练习

1. 单值二叉树。单值二叉树

2. 检查两颗树是否相同。相同的树

3. 对称二叉树。对称二叉树

4. 二叉树的前序遍历。 二叉树的前序遍历

5. 二叉树中序遍历 。二叉树的中序遍历

6. 二叉树的后序遍历 。二叉树的后序遍历

7. 另一颗树的子树。另一棵树的子树

具体解析看另外一篇博客，链接：

二叉树基础oj练习【11道题】-CSDN博客

4.9二叉树的创建与销毁

4.9.1二叉树的创建

二叉树构建和遍历

这道leetcode的题可以当做参考

思路：

1. 判断传进来的数组元素是否是# 也就是是否为空
2. 如果不为空，通过前序遍历构建出这个二叉树

代码：

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
	// 判断传进来的数组元素是否是# 也就是是否是空
	if (a[(*pi)] == '#')
	{
		(*pi)++;
		return NULL;
	}
	else
	{
		// 如果不是空 那就要前序构建二叉树  
		BTNode* root = (BTNode*)malloc(sizeof(BTNode)); // 构建节点
		root->_data = a[(*pi)];
		(*pi)++;

		// 前序构建二叉树
		root->_left = BinaryTreeCreate(a, pi);
		root->_right = BinaryTreeCreate(a, pi);

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

测试代码：

	// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
	char str[100] = "ABD##E#H##CF##G##";
	int i = 0;
	BTNode* root = BinaryTreeCreate(str, &i);
	PreOrder(root); // A B D NULL NULL E NULL H NULL NULL C F NULL NULL G NULL NULL
	printf("\n");
1
2
3
4
5
6

4.9.2二叉树的销毁

比较简单，直接看代码：

// 二叉树销毁
void BinaryTreeDestory(BTNode* root) // 也可以使用二级指针，为了接口一致性也可以用一级指针，看需求
{
	if (root == NULL)
		return;

	// 采用后序销毁二叉树，前序销毁要注意能否找到下一子节点的问题
	BinaryTreeDestory(root->_left);
	BinaryTreeDestory(root->_right);
	free(root);
}
1
2
3
4
5
6
7
8
9
10
11

4.10判断二叉树是否为完全二叉树

思路：

如图所示

• 如果我们层序遍历一个二叉树，如果这个二叉树是完全二叉树，那么最终打印的结构，二叉树的值和 NULL 是氛围两个阶段的
• 但是如果不是完全二叉树，那么NULL 和 值 就不是两段了。

因此我们可以利用这个特性来判断二叉树是否为完全二叉树

代码：

// 判断二叉树是否是完全二叉树 （是就返回1 不是就返回0）
int BinaryTreeComplete(BTNode* root)
{
	// 先层序二叉树，根据层序的结果来判断是否是完全二叉树
	Queue q;
	QueueInit(&q); // 初始化

	// 判断一开始的根结点是否是NULL
	if (root == NULL)
	{
		QueueDestory(&q);
		return 1; // 我们认为空树也是完全二叉树
	}

	// 层序二叉树 (这里的层序需要NULL进入队列)
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		// 获取队头
		BTNode* frontnode = QueueFront(&q);
		QueuePop(&q); // 弹出队头

		// 访问队头的数据
		if (frontnode == NULL) // 如果是空就判断队列中剩下的数据是否都是NULL
			break; // 跳出循环

		// 访问完之后要把该节点的左右子节点依次插入到队列当中
		QueuePush(&q, frontnode->_left);
		QueuePush(&q, frontnode->_right);
	}
	// 走到这里就判断队列中剩下的数据是否都是NULL
	// 因为如果是完全二叉树的层序，层序到NULL 就说明所有节点都层序完了
	// 如果都是NULL 就是完全二叉树
	while (!QueueEmpty(&q)) // 遍历队列中剩下的数据
	{
		BTNode* Frontnode = QueueFront(&q); // 获取队头
		QueuePop(&q); // 弹出队头

		// 判断队头是否是NULL
		if (Frontnode != NULL)
		{
			QueueDestory(&q);// 销毁队列
			return 0; // 只要不是NULL就不是完全二叉树
		}

	}

	// 走到这里说明 队列中剩下的数据都是NULL
	// 那就是完全二叉树

	QueueDestory(&q);// 销毁队列
	return 1;
}
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

5.总结

有关二叉树的学习，目前已经学习了大概2/5的样子，后面更加有难度的，比如搜索平衡二叉树，红黑树等知识，将在C++学习