---

1.树概念及结构

1.1 树的概念

树是一种非线性的数据结构，它是由n(n>=0)个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一颗倒挂的树，也就是说它是根朝上，而叶朝下的。
有一个特殊的节点，称为根节点，根节点没有前驱节点。
除根节点外，其余节点被分成M(M>0)个互不相交的集合T1、T2…Tm,其中每一个集合Ti(1 <= i <= m)又是一棵结构与树类似的子树。每棵子树的根结构有且只有一个前驱，可以有1个或多个后继。
因此，树是递归定义的。

树与非树的区分
下述皆不是树
树应满足下述条件：
子树是不相交的；
除了根节点外，每个节点有且仅有一个父节点；
一棵N个节点的树有N-1条边；

树的相关概念

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

1.2树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法，孩子兄弟表示法等等。我们这里简单的了解其中最常用的孩子兄弟表示法。

typedef int DataType;
struct Node
{
	struct Node* _child;//第一个孩子节点
	struct Node* _brother;//指向下一个兄弟节点
	DataType _data;//数据域
};
1
2
3
4
5
6
7

1.3树在史记中的运用

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

2. 二叉树概念及结构

2.1 概念

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

二叉树的特点：
1.每个节点最多有两棵子树，即二叉树不存在度大于2的节点；
2.二叉树的子树有左右之分，其子树的次序不能颠倒，因此二叉树是有序树。

注意：任何二叉树都由以下几种情况复合而成：

2.2 特殊的二叉树

1.满二叉树：一个二叉树，如果每一个层的节点总数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数是K,且节点总数是(2^K)-1,则它就是满二叉树。
2.完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。要注意的是满二叉树是一种特殊的完全二叉树。

注意：在判断是否是完全二叉树时，应该保证最下层的节点都是从左到右依次排列的！下面举个经典例子：

2.3二叉树的存储结构

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

二叉树的性质

1.若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个节点。
2.若规定根节点的层数为1，则深度为h的二叉树的最大节点数是2^h - 1
3.对任何一棵二叉树，如果度为0其叶节点个数为n0，度为2的分支节点个数为n2，则有n0 = n2 + 1
4.若规定根节点的层数为1，具有n个节点的满二叉树的深度，h = Log(n+1)(ps:Log(n+1)是log以2为底，n+1为对数）
5.对于具有n个节点的完全二叉树，如果按照从上至下从左到右的数组顺序对所有节点从0开始编号，则对于序号为i的节点有：
1.若i>0,i位置节点的双亲节点序号：(i-1)/2；i = 0, i为根节点编号，无双亲节点
2.若2i+1=n ,则无左孩子
3.若2i+2 < n，右孩子序号为2i+2；如果2i+2 >= n，则无右孩子

2.3.1 顺序存储

顺序结构存储就是使用数组存储，一般使用数组只适合表示完全二叉树，因此不是完全二叉树会有空间的浪费。二叉树顺序存储在物理上是一个数组，在逻辑上一棵二叉树。

2.5.2 链式存储

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

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

3.1 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆（一种二叉树）使用顺序结构的数组存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

3.2堆的概念及结构

如果有一个关键码的集合K = {k0,k1,k2,…,kn-1},把它的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= 2Ki + 1（父节点小于左孩子）且 Ki <= 2Ki+2（父节点小于右孩子）或者 Ki >= 2Ki +1 且Ki >= 2Ki + 2，i = 0，1，2…,则称为小堆（或大堆）。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树；

3.3堆的实现

3.3.1 堆的结构定义

堆既然是顺序存储的，那么肯定也是要按顺序表的的方式来定义

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;//动态开辟存储数据的数组
	int size;//当前元素个数
	int capacity;//数组容量
}Heap;
1
2
3
4
5
6
7

3.3.2堆的打印

堆的本质是数组，我们就按数组的形式打印即可。

//堆的打印
void HeapPrint(Heap* php)
{
	assert(php);
	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

3.3.3 堆的插入与创建

假设有一个已经建成大堆的数组，现在要插入一个数据，插入数据后仍然要保持堆的结构不变，那么应该如何做呢？
我们这里给出一个算法：向上调整算法。
由于插入的数据可能会破坏堆结构，我们就可以利用向上调整来修复堆。
向上调整算法思想（大堆为例）：
1.将最后一个叶子节点（即刚插入的元素）与其父亲进行比较：
如果比父亲要大，则交换父节点与子节点，并把交换后的父节点当成子节点继续向上调整，直到到达堆顶停止；
如果比父亲小，则停止调整，此时就已经是大堆了；

我们先用图来看看是如何实现的：

小堆的向上调整：

大堆向上调整的代码实现：

void swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}

//堆的向上调整
//child为插入的元素下标
//建大堆
void AdjustUp_greater(HPDataType* a, int child)
{
	//利用父子节点的公式求父亲
	int parent = (child - 1) / 2;
	
	//当插入的值为根节点时停止调整
	while (child > 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
26
27
28
29
30
31
32
33
34
35

小堆向上调整代码实现：
小堆和大堆实现起来基本相同，判断时与大堆相反即可。

//小堆的向上调整
void AdjustUp_less(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 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

堆的插入代码实现：
在了解了堆的向上调整算法后，堆的插入就变得十分简单了，我们只需要将数据插入堆中，插入后要再进行调整即可。注意：堆的物理结构是数组，需要进行扩容操作！

//堆的插入
void HeapPush(Heap* php, HPDataType val)
{
	assert(php);
	//检查扩容
	if (php->capacity == php->size)
	{
		int new_capacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType)*new_capacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = new_capacity;
	}
	//插入数据
	php->a[php->size] = val;
	php->size++;

	//向上调整算法
	//选择建大堆
	//此时插入的元素下标为(size-1) ！！！ 
	AdjustUp_greater(php->a, 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

实现效果：
注意与前面的图进行对比！！

发现没有，我们并没有按照大堆的数组顺序去插入数据，但是我们却把堆建立起来了！这都得益于在插入的时候进行了向上调整！下面是建堆的具体过程：



总结：
在进行堆的插入时，就已经是在进行堆的创建了！

3.3.4 堆的删除

堆的删除是取堆顶元素进行删除的；现在，我们先想一想可不可以直接删除掉堆顶元素，如果不可以，那还有什么办法能删除吗？
根据堆的性质，我们是不能直接删除堆顶元素的，直接删除会造成父不父，子不子的现象，如果要继续维持堆的特性，就需要重新建堆，这样代价太大；删除堆顶元素后出现下列现象：

我们这里引出一个算法：向下调整算法
思路：先交换首元素和尾元素的值，再删除尾元素（变相删除堆顶元素），最后在进行向下调整算法使其恢复成堆。
向下调整算法思想（大堆为例）：
1.从根结点处开始，选出左右孩子中值较大的孩子。
2.让大的孩子与其父亲进行比较：
若大的孩子比父亲还大，则该孩子与其父亲的位置进行交换。并将原来大的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
若大的孩子比父亲小，则不需处理了，调整完成，整个树已经是大堆；
注意：向下调整的使用前提必须是左右子树皆为堆（只有根不满足堆）。
下面用图解释具体过程：

注意：删除堆顶元素时，只有根节点可能不满足大堆或小堆的特性，其余子树仍然满足大堆或小堆的特性。所以，我们在进行向下调整时，只需要判断左右孩子的大小是否能与父亲的大小形成堆即可。

向下调整的代码实现（大堆）：

//向下调整算法
//size为当前元素个数
//parent为当前堆顶下标
void AdjustDown_greater(HPDataType* a, int size, int parent)
{
	//先假设大的孩子为左孩子
	int child = parent * 2 + 1;

	//在数组范围内有效
	while (child < size)
	{
		//如果左孩子小于右孩子(右孩子存在)
		if (child + 1 < size && a[child] < a[child + 1])
		{
			child++;//右孩子变为大的孩子
		}
		//如果大的孩子比父亲大，进行调整
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;//父亲来到孩子的下标位置
			child = parent * 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

堆的删除的代码实现

//堆的删除
void HeapPop(Heap* php)
{
	//保证有数可删
	assert(php && php->size > 0);

	//交换首尾元素
	//尾部要被删除，可以直接忽略
	php->a[0] = php->a[php->size - 1];

	//删除尾部元素
	php->size--;
	
	//向下调整
	AdjustDown_greater(php->a, php->size, 0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.4 堆的接口函数总代码

由于堆重点在于向上调整与向下调整算法，这里其余接口就不在一一讲解，直接给代码。

3.4.1 Heap.h

#pragma once
#include
#include
#include
#include

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;//动态开辟存储数据的数组
	int size;//当前元素个数
	int capacity;//数组容量
}Heap;

//堆的初始化
void HeapInit(Heap* php);
//堆的打印
void HeapPrint(Heap* php);
//大堆的向上调整
void AdjustUp_greater(HPDataType* a, int child);
//小堆的向上调整
void AdjustUp_less(HPDataType* a, int child);
//堆的插入
void HeapPush(Heap* php, HPDataType val);
//堆的删除
void HeapPop(Heap* php);
//大堆的向下调整
void AdjustDown_greater(HPDataType* a, int size, int parent);
//取堆顶数据
HPDataType* HeapTop(Heap* php);
//判空
bool HeapEmpty(Heap* php);
//取堆的元素个数
int HeapSize(Heap* php);
//堆的销毁
void HeapDestory(Heap* php);
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

3.4.2 Heap.c

#include"Heap.h"

//堆的初始化
void HeapInit(Heap* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

//堆的打印
void HeapPrint(Heap* php)
{
	assert(php);
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

void swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}

//堆的向上调整
//child为插入的元素下标
//建大堆
void AdjustUp_greater(HPDataType* a, int child)
{
	//利用父子节点的公式求父亲
	int parent = (child - 1) / 2;
	
	//当插入的值为根节点时停止调整
	while (child > 0)
	{
		//孩子比父亲大，不满足大堆，交换
		if (a[child] > a[parent])
		{
			//交换父子的值
			swap(&a[child], &a[parent]);
			//儿子来到父亲的下标位置
			child = parent;
			//新的父亲的下标
			parent = (child - 1) / 2;
		}
		//如果孩子比父亲小，满足大堆，结束调整
		else
		{
			break;
		}
	}
}

//小堆的向上调整
void AdjustUp_less(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//小堆与大堆相反，父亲必须比儿子小，否则需要进行调整
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//堆的插入
void HeapPush(Heap* php, HPDataType val)
{
	assert(php);
	//检查扩容
	if (php->capacity == php->size)
	{
		int new_capacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType)*new_capacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = new_capacity;
	}
	//插入数据
	php->a[php->size] = val;
	php->size++;

	//向上调整算法
	//选择建大堆
	//此时插入的元素下标为(size-1) ！！！ 
	AdjustUp_greater(php->a, php->size - 1);
}

//向下调整算法
//size为当前元素个数
//parent为当前堆顶下标
void AdjustDown_greater(HPDataType* a, int size, int parent)
{
	//先假设大的孩子为左孩子
	int child = parent * 2 + 1;

	//在数组范围内有效
	while (child < size)
	{
		//如果左孩子小于右孩子(右孩子存在)
		if (child + 1 < size && a[child] < a[child + 1])
		{
			child++;//右孩子变为大的孩子
		}
		//如果大的孩子比父亲大，进行调整
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;//父亲来到孩子的下标位置
			child = parent * 2 + 1;//新的左孩子
		}
		else
		{
			break;
		}
	}
}

//堆的删除
void HeapPop(Heap* php)
{
	//保证有数可删
	assert(php && php->size > 0);

	//交换首尾元素
	//尾部要被删除，可以直接忽略
	php->a[0] = php->a[php->size - 1];

	//删除尾部元素
	php->size--;
	
	//向下调整
	AdjustDown_greater(php->a, php->size, 0);
}

//取堆顶数据
HPDataType* HeapTop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	
	return php->a[0];
}

//判空
bool HeapEmpty(Heap* php)
{
	assert(php);

	return php->size == php->capacity;
}

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

	return php->size;
}

//堆的销毁
void HeapDestory(Heap* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
}
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

4.堆排序

堆排序是八大排序中的一种，其效率十分之快，它的本质就是利用堆来进行排序的。下面，我们将从堆的实现，如何选数，时间复杂度来进行讲解。

4.1 堆的实现

都叫堆排序了，那肯定就离不开建堆，那么我们该如何来建堆呢？
我们前面已经实现了一个堆，那么我们是否可以利用这个堆来对数组进行建堆呢？
很遗憾！我们并不能使用我们实现的堆进行建堆！
因为这样的效率十分的低下，且实现起来太过复杂！(需要重新开辟一个数组，再将数组元素一个一个以堆的形式插入，并且还得自己完成堆的接口)。
但是，我们可以利用堆的特性，在原数组自身进行建堆。堆的实现离不开向上调整与向下调整，我们先讲如何使用向上调整来进行建堆。

4.1.1 向上调整建堆

原理：
模拟堆插入：将下标从1开始的数组元素模拟插入到堆中，然后每个元素都进行向上调整。

代码实现：

//模拟插入进行向上调整
//size为元素个数
for (int i = 1; i < size; i++)
{
	AdjustUp_greater(a, i);
}
1
2
3
4
5
6

图解：

4.1.2向下调整建堆

思路：
向下调整算法完成建堆要求我们每棵树除去根外其余子树都必须满足堆特性，我们可以利用这个特性，从最后一棵树开始进行调整，依次将每棵子树都调整到满足堆特性。由于最后一个树为叶子节点，所以我们将开始调整的树锁定到第一个非叶子节点。

代码实现：

//向下调整
//size为元素个数
//size-1为最后一个叶子节点的下标
//((size-1)-1)/2 为最后一个叶子节点的父亲，也就是第一个非叶子节点
for (int i = ((size - 1) - 1) / 2; i >= 0; i--)
{
	AdjustDown_greater(a, size, i);
}
1
2
3
4
5
6
7
8

图解：

4.1.3向上调整建堆与向下调整建堆的区别

先来讲讲向下调整：
我们从倒数第一个非叶子节点开始，依次对后面的节点进行向下调整。我们画图来看看每一层节点需要调整的次数(最坏情况下)：

既然我们有了这个规律，那么求出它的时间复杂度就不是问题。下面给出时间复杂度的公式推导：

所以，我们可以得到向下调整建堆的时间复杂度为O(N)，这得益于我们将最下面一层的所有节点都忽略掉，不需要调整

再来看看向上调整：
我们从正数第2个节点开始进行调整，直到最后一个节点调整结束才结束。注意向上调整需要调整完最后一层所有节点。我们同样用图的形式来看看每一层的每个节点需要调整的次数：

我们可以根据上述规律，得出其时间复杂度。下面是推导公式：

总结：
1.向上调整建堆的时间复杂度是O(N*LogN)，向下调整建堆的时间复杂度是O(N);
2.向下调整建堆比向上调整建堆效率高的原因是：向上调整建堆需要最后一层的节点全部向上调整高度次，向下调整则不需要，而最后一层的节点几乎占了总节点的一半，这导致了最后一层的向上调整严重地影响了效率；
3.向下调整建堆越往上调整次数越多，越往下调整次数越少；向上调整建堆越往上调整次数越少，越往下调整次数越多；

4.2堆的选数

这里先抛出两个问题：
1.如果要排一个升序数组，该建大堆还是小堆？
2.该如何将数排到正确的地方？

分析：
我们先选择建小堆，然后将堆顶的数据写入到新数组中，这样是否可行呢？
这个操作是不是似曾相识，它很像之前提到过的堆的删除操作，这样的操作在前面也提到过它是不可行的，这会造成：父不父，子不子的情况；那么该如何进行选择呢？
我们可以借鉴堆的删除操作，将堆顶的数据与堆尾的数据进行交换，此时堆顶的数据就会来到尾节点，此时，尾节点就存储着原先堆顶的数据，由于我们选择的是升序，所以越靠后面的节点就需要存储越大的数，那么我们就得选择大堆来进行选数（大堆堆顶数据是当前最大值），并且每次交换首尾都得让尾部节点下标后退一步，让次大的数存储在该节点位置。又由于交换首尾破坏了堆的特性，我们就需要使用向下调整来选出次大的数调整堆，我们需要持续这个操作直到无数可选。

代码实现：

//升序
//建大堆选数
for (int i = 1; i < size; i++)
{
	//将堆顶的数选到正确位置
	swap(&a[0], &a[size - i]);
	//向下调整
	AdjustDown_greater(a, size - i, 0);
}
1
2
3
4
5
6
7
8
9

4.3总体代码实现

void HeapSort(int* a, int size)
{
	//向下调整
	//size为元素个数
	//size-1为最后一个叶子节点的下标
	//((size-1)-1)/2 为最后一个叶子节点的父亲，也就是第一个非叶子节点
	for (int i = ((size - 1) - 1) / 2; i >= 0; i--)
	{
		AdjustDown_greater(a, size, i);
	}

	//升序
	//建大堆选数
	for (int i = 1; i < size; i++)
	{
		//将堆顶的数选到正确位置
		swap(&a[0], &a[size - i]);
		//向下调整
		AdjustDown_greater(a, size - i, 0);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

实现效果：

4.4时间复杂度的分析

1.建堆的时间复杂度：O(N)；
2.选数：对N-1个数进行向下调整，每次向下调整的时间复杂度为O(LogN），总共的向下调整的时间复杂度为O(N*LogN)；
3.总计时间复杂度为O(N + N * LogN），取大为O(N*LogN）；

5. TopK问题

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

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于TopK问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了（可能数据都不能一下子全部加载到内存中）。最佳的方式就是用堆来解决。

假设有N个数据，要选择前K个大的数据。
那么应该建大堆进行选数还是选小堆进行选树数呢？
我们先选择建大堆进行选数，这样我们只需要在建完堆后Pop掉前K个数据即可；时间复杂度：建堆O(N)，Pop前K个数据需要进行K次向下调整，效率为O(K*LogN），总的时间复杂度为O(N + K * LogN )；效率还是非常高的；但是：如果N非常大，可能会存在这么一个情况：没有足够的内存让你建这个大堆！ 这样就只能使用小堆来进行排序了。

5.1 建小堆解决TopK问题

思想：
1.先用前K个数，创建一个存放K个数据的小堆。
2.依次遍历后续N-K个数，比堆顶的数据大，就替换掉堆顶数据（相当于替换掉堆中最小的数），然后进行向下调整。遍历结束后，这个小堆就存储着前K大的数据。

由于只需要在内存中建立K个数据的小堆，就不存在内存不够的问题，N-K个数据可在硬盘中读取。下面用代码演示下在硬盘中读取前K大的数据。

//TopK问题
void CreateDataFile(const char* name, int N)
{
	FILE* fin = fopen(name, "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		return;
	}
	srand(time(0));//随机数种子
	//写1w个随机数进文件中
	for (int i = 0; i < N; i++)
	{
		fprintf(fin, "%d ", rand());
	}

	fclose(fin);
}

void GetK_File(const char* name, int K)
{
	FILE* fout = fopen(name, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}
	
	int* ans = (int*)malloc(sizeof(int) * K);
	//读取前K个数
	for (int i = 0; i < K; i++)
	{
		fscanf(fout, "%d", &ans[i]);
	}
	//向下调整建小堆
	for (int i = ((K - 1) - 1) / 2; i >= 0; i--)
	{
		AdjustDown_less(ans, K, i);
	}
	//遍历N-K个数比堆顶大的替换
	int val = 0;
	while (fscanf(fout, "%d", &val) != EOF)
	{
		if (val > ans[0])
			ans[0] = val;

		AdjustDown_less(ans, K, 0);
	}
	
	//打印前K个数
	for (int i = 0; i < K; i++)
	{
		printf("%d ", ans[i]);
	}
	printf("\n");
	fclose(fout);
}

int main()
{
	const char* p = "data.txt";
	int N = 10000;//写一万个数据
	int K = 5;//取前5大的数据
	//写数据到文件中
	CreateDataFile(p,N);
	//从文件中读取前K大的数
	GetK_File(p, K);

	return 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

先观察写入文件的数据：

为了便于观察，我们在这其中添加5个大于10w的数字（rand()生成的随机数最大为32767)；然后屏蔽掉CreateDataFile(p,N)，查看结果。

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

6.1 前置说明

在学习二叉树的基本操作前，需要先创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，为了降低学习成本，此处手动快速创建一棵简单的二叉树，来快速进入二叉树的操作学习。

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType val)
{
	BTNode* new_node = (BTNode*)malloc(sizeof(BTNode));
	if(new_node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	new_node->data = val;
}

//创建简易二叉树
void CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);	
	BTNode* node4 = BuyNode(4);	
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

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

	return node1;
}
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

注意：上述代码并不是创建二叉树的方式，真正创建二叉树的方式后面再重点讲解。

再看二叉树基本操作前，再回顾下二叉树的概念，二叉树是：
1.空树
2.非空：根节点，根节点的左子树，根节点的右子树组成。
从概念中可以看出，二叉树是递归式的，因此后续基本操作中基本都是按照该概念实现的。

6.2 二叉树的遍历

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

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
1.前序遍历（先序遍历）：访问根节点的操作发生再遍历其左右子树之前。（根->左子树->右子树）
2.中序遍历：访问根节点的操作发生在遍历其左右子树中间。（左子树->根->右子树）
3.后序遍历：访问根节点的操作发生在遍历其左右子树之后（左子树->右子树->根）；

//二叉树前序遍历
void PreOrder(BTNode* root);
//二叉树的中序遍历
void InOrder(BTNode* root);
//二叉树的后序遍历
void PostOrder(BTNode* root);
1
2
3
4
5
6

下面主要分析前序递归遍历，中序与后序图解类似。


代码实现：

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12

层序遍历在下面只给出代码实现，这里不过多进行讲解；

6.3 二叉树的其余操作

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%d ", root->data);
	BinaryTreeInOrder(root->right);
}

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%d ", root->data);

}

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;

	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}


// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;

	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

//二叉树中的查找
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	
	if (root->data == x)
		return root;
	
	BTNode* left = TreeFind(root->left, x);
	if (left != NULL)
		return left;
	
	BTNode* right = TreeFind(root->right, x);
	if (right != NULL)
		return right;

	return NULL;
}

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	
	Queue q;
	QueueInit(&q);
	QueuePush(&q,root);
	int i = 0;
	int count = 0;
	while (!QueueEmpty(&q))
	{
		BTNode* tmp = QueueFront(&q);
		if (tmp == NULL)
			printf("NULL ");
		else
		{ 
			printf("%d ", tmp->data);
			QueuePush(&q, tmp->left);
			QueuePush(&q, tmp->right);
		}
		count++;
		if (count == pow(2, i))
		{
			printf("\n");
			i++;
			count = 0;
		}
		QueuePop(&q);
	}

	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
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124