万字详解数据结构——树

三、完全二叉树：

3.1堆

  堆是一个树形结构，其实堆的底层是一棵完全二叉树，我们先来看一下完全二叉树，满二叉树是特殊的完全二叉树。

大堆：树中所有的父亲都大于等于孩子。

小堆：树中所有的父亲都小于等于孩子。

对于任何一个数组都可以看作是一颗完全二叉树但是不一定是堆

就比如下图，我们插入100，发现新插入的100比它的所有祖先都要大而且还是大堆，为了不改变大堆结构所以我们向上调整，来保持插入后还是大堆。

//向上调整大堆代码
void AdjustUp(HPDataType* a,int child)
{
	int parent=(child-1)/2;
    //while(parent>=0)   不好
    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 AdjustUp(HPDataType* a,int child)
{
	int parent=(child-1)/2;
    //while(parent>=0)   不好
    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

大堆：根是堆里面最大的数。

小堆：根是堆里面最小的数。

3.2堆的应用

1.排序

2.topK（N个数找最大/最小的前K个数）

3.2.1删除堆顶的数据

如果我们如下图直接删除堆顶数据：

1.其余数据必定挪动，时间复杂度就是O(n).

2.如果依次往前移我们发现之前堆的关系就变了

​ 比如：49 和34之前是兄弟结点，挪动之后49反而成了34的父亲结点，关系发生了改变.

​ 最严重的是已经不可以称之为堆了

向下调整必须保证左子树和右子树是堆。

  我们想要向下调整就是因为换上去的最后一个结点的数据太小，德不配位，所以需要重新调整，我们要将它的孩子中最大的一个和该结点进行交换，然后依次向下调整，最后就可以保证这个完全二叉树还是堆。

删除堆顶元素代码实现：

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		//孩子比父亲小就是大堆无需向下调整
		else
		{
			break; 
		}
	}
}
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

效果如下图：

堆的完整代码实现：

头文件Heap.h

#define _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include
#include
#include
#include


typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

// 堆的构建
void HeapCreate(HP* hp, HPDataType* a, int n);
void AdjustDown(HPDataType* a, int n, int parent);
void HeapPrint(HP* php);
void HeapInit(HP* php);
void HeapDestory(HP* php);

// 保持他继续是一个堆 O(logN)
void HeapPush(HP* php, HPDataType x);

// 删除堆顶的数据，并且保持他继续是一个堆 O(logN)
void HeapPop(HP* php);

HPDataType HeapTop(HP* php);

int HeapSize(HP* hp);
// 堆的判空
bool HeapEmpty(HP* hp);

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

功能实现文件Heap.c

#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include"Heap.h"
//构建堆
void HeapCreate(HP* php, HPDataType* a ,int n)
{
	assert(php);
	php->a = (HPDataType*)malloc(php->a, sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = php->capacity = n;
	//建堆算法
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);        
	}
}
void HeapPrint(HP* php)
{
	assert(php);
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}
void HeapDestory(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
 }
void AdjustUp(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(HP* php, HPDataType x)
{
	assert(php);
	if (php->size ==php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("reallic fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);
}
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		//孩子比父亲小就是大堆无需向下调整
		else
		{
			break; 
		}
	}
}
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 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
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

测试文件

#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include"Heap.h"
void TestHeap1()
{
	int arry[] = { 27.15,19.18,28,34,65,49,25,37 };
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(arry) / sizeof(int); ++i)
	{
		HeapPush(&hp, arry[i]);
	}
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	HeapDestory(&hp);
}
int main()
{
	TestHeap1();
	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

我们来看下面两个代码：

3.2.2堆的构建

//建堆算法1
void HeapCreate(HP* php, HPDataType* a ,int n)
{
	assert(php);
	php->a = (HPDataType*)malloc(php->a, sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = php->capacity = n;
	//建堆算法
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);        
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

堆的初始化

void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}
1
2
3
4
5
6

在这里必须提一下建堆算法：

  我们如果要建堆可以考虑将数组中的每个元素依次插入，每插入一个就向下调整，但是这样效率很低。我们向下调整的前提是左右子树都是堆，我们将根结点的左右子树不断的划分，如上图红色标出的只有1是堆，2是堆，4才可能是堆，然后我们不如从后面开始，最后一个结点37所在的子树要是堆，那么它的父亲结点和它之间就要符合堆的结构，然后我们从它的父亲开始向下调整，就可确保1部分是堆，然后i–，（因为数组是一层一层放的，28–就是它左边的数），去处理2部分，最后只需要5次向下调整就可以达到建堆的目的，次数明显减少，效率提高很多，代码为建堆算法1.

3.2.3向上/向下的建堆算法

void HeapSort(HPDataType* a,int n)
{	
    //向上调整建堆
	for (int i = 0; i < n; ++i)
	{
		AdjustUp(a, i);
	}
    //向下调整建堆
    for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);        
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

向上调整建堆的要求是：之前插入的是一个堆，插入之后还是一个堆

向下调整建队的要求是：左子树和右子树都是堆

但是向上建堆和向下建堆的时间复杂度是不一样的，我们分别来计算一下向下调整建堆和向上调整建堆的情况：

我们假设树的高度为h，然后从图中可以看出，层数越往上，向下调整的层数越多。

第一层只有1个结点，最坏的情况需要向下调整h-1次就可以到达树的叶子节点.

依次类推，层数越往下，调整的层数越少，我们只需要调整第1层到第h-1层即可。

我们利用数列的错位相减法就可以求出h层的树向下需要调整的总次数为 F(h)=（2^h)-1-h.

在二叉树中我们证明过树的高度和结点数之间的关系：(ps:h是树的高度 N是节点的个数)

即(2^h)-1=N,我们将F函数中的自变量由h变成N，结果是F(N)=N-log(N+1),它的时间复杂度是O(N).

3.2.4堆按升序排列

如果我们想要升序排列，那么建大堆还是小堆呢？

很多人都会先入为主认为升序的话应该建小堆，但是真的是这样吗？我们来分析一下：

  我们发现如果建小堆然后取出堆顶的数据后，关系就乱了，根本就不是堆了，我们为了继续升序排列就得重新建堆，然后效率特别低下。那么如果建大堆呢？我们来看看：

  我们按照大堆建堆，我们之前就讲过如果是大堆取出堆顶数据的话，它的左右子树都是堆，为了不改变关系，我们先让堆顶的数据和最后一个节点的数据交换，然后取出最后一个数据即取出最大的数据，这里我们想要升序，那么只需要将堆顶的数据和最后一个数据做交换，然后把最后一个结点不看做堆里面的，再对堆向下调整，同理选出次大的。

  然后就有人想，堆排序和冒泡排序插入排序时间复杂度差别大吗？下面来计算一下：

  假设都是要升序排列：

  冒泡排序和插入排序的时间复杂度是O(N^2),我们堆排序建大堆，时间复杂度是O(N*logN)

从上图中可以看出堆排序相比较其他排序时间效率真的很高。

代码如下：

void HeapSort(HPDataType* a, int n)
{
	//向上调整建堆   O(N*logN)
	/*for (int i = 0; i < n; i++)
	{
		AdjustUp(a, i);
	}*/
	//向下调整建堆     O(N)
	//升序，建大堆
	//for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	//{
	//	AdjustDown(a, n, i);
	//}
	//O(N*logN)
	int end =n - 1;
	while (end >0 )
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.2.5TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
  比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
  对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆
   前k个最大的元素，则建小堆
   前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素

千万切记如果去前K个最大的数那么一定只能建k个数的小堆。

  原因是如果建立大堆，假设第一个进去的数就是N个数中最大的数，那么这个数就会堵在堆顶，只有比他大才可以进入进入，但是它是最大的，所以这K个数的堆建立就会出现问题，只有建立小堆，保证K个数中最小的在上面，一旦有比他大的就替换他，然后向下调整保证这K个数的堆还是小堆。

void TestHeap5()
{
	// 造数据
	int n, k;
	printf("请输入n和k:>");
	scanf("%d%d", &n, &k);
	srand(time(0));
	FILE* fin = fopen("data.txt", "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		return;
	}

	int randK = k;
	for (size_t i = 0; i < n; ++i)
	{
		int val = rand() % 100000;
		fprintf(fin, "%d\n", val);
	}

	fclose(fin);

	/
	// 找topk
	FILE* fout = fopen("data.txt", "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}

	//int minHeap[5];
	int* minHeap = malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{
		perror("malloc fail");
		return;
	}

	for (int i = 0; i < k; ++i)
	{
		fscanf(fout, "%d", &minHeap[i]);
	}

	// 建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(minHeap, k, i);
	}

	int val = 0;
	while (fscanf(fout, "%d", &val) != EOF)
	{
		if (val > minHeap[0])
		{
			minHeap[0] = val;
			AdjustDown(minHeap, k, 0);
		}
	}

	for (int i = 0; i < k; ++i)
	{
		printf("%d ", minHeap[i]);
	}
	printf("\n");

	fclose(fout);
}
int main()
{
	TestHeap5();
	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
71
72
73
74

3.5链式二叉树

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

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

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

前序遍历代码实现：

void PrevOrder(BTNode* root)
{
	if (root==NULL)
	{
		printf("NULL");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11

中序遍历代码实现：

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11

后序遍历代码实现：

void PostOrder(BTNode* root)
{
	if (root==NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

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

那么我们怎么求二叉树的节点个数呢？

  还是利用递归的思想，设置一个全局变量size，每次size++都是改变全局变量size.

代码如下：

int size = 0;
void TreeSize1(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	size++;
	TreeSize1(root->left);
	TreeSize1(root->right);
}
int TreeSize2(BTNode* root)
{
	return root == NULL ? 0 : TreeSize2(root->left) + TreeSize2(root->right) + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

如何求叶子节点的个数呢？

  叶子节点个数要注意的是不仅要判断root有无左右子树，还要注意root是否为NULL。

  如何计算树的高度呢？

  我们先来看一下这个代码对不对，乍一看没什么问题，如果树的高度不大运行起来也没什么问题，但是真的是对的吗？

  我们发现这个代码其实存在很大的问题，就在于return语句，每次比较之后知道要返回左数还是右数的深度，但是深度是多少却又要再次计算，也就是说TreeHeight需要重复计算，树的深度太大程序就会崩溃。

  所以正确写法应该是这样：

int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
1
2
3
4
5
6
7
8
9
10

求第k层的节点个数K>=1

int TreeKLevelSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	//k>1子树的k-1
	return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1);
}
1
2
3
4
5
6
7
8
9

}

总结

  本篇博客涵盖了树的基本概念，二叉树的初阶知识，包括完全二叉树，满二叉树，二叉树的实现，二叉树的四种遍历，二叉树的顺序实现和二叉树的链式实现，同时还有堆的相关知识，大小堆的实现，向上调整，向下调整，topK问题等等，希望对大家有所帮助，欢迎大家交流~