【数据结构】万字二叉树与堆

了解完二叉树的性质之后，我们不妨来做几道选择题：

1.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199

答案：B。n0 = n2+1，既n0=199+1 = 200
2.下列数据结构中，不适合采用顺序存储结构的是（ ）
A 非完全二叉树
B 堆
C 队列
D 栈

答案：A。

3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2

答案：A。总结点数n = n0+n1+n2;又n2 = n0-1,既n=n0+n1+n0-1,在完全二叉树中，n1只有0个或者1个，代入选A

4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12

答案：B

5.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386

答案：B。类似于第3题，总结点n = n0+n1+n0-1;n1为0或者1,代入能整除的选B

2.4二叉树的存储结构

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

1. 顺序存储
   顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，下面我们会说到。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树

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

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

3.1二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结
构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储。

3.2堆的概念

如果有一个关键码的集合K ={K0,K1,K2,…Kn-1};把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足:Ki<=K2i+1并且Ki<=K2i+2,i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

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

我们来做一道选择题试一试：

下列关键字序列为堆的是：（）
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

解析：这里没有明确说明是大堆还是小堆，我们直接在草稿上简单画一下就知道答案了：

3.3堆的实现

Heap.h

#include 
#include 
#include 
#include 
#include 

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
//初始化堆
void HeapInit(HP* php);
//销毁堆
void HeapDestory(HP* php);
//打印堆
void HeapPrint(HP* php);
//插入X继续保持堆形态
void HeapPush(HP* php,HPDataType x);
//删除堆顶元素
void HeapPop(HP* php);
//判断是否为空
bool HeapEmpty(HP* php);
//返回堆顶元素
HPDataType HeapTop(HP* php);
//返回堆的元素大小
int HeapSize(HP* 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

这就是一些要实现的接口，下面通过Heap.c对以上接口进行说明。

Heap.c

初始化

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

插入X并保持堆

插入之前是小根堆（假设堆已经创建好，后面会说到堆的创建，不要急，先看这一部分，便于理解，后面堆的创建就简单多了），我们是在尾部把X插入的，然后再进行向上调整（原来必须是大堆或者小堆了）。

比如先插入一个10到数组的尾上 ，再进行向上调整算法，直到满足堆 ：

最后一个位置是：php->size-1.要找到父节点：(child-1)/2,如此我们去比较大小进行交换调整，就能够实现我们的向上调整：

//交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向上调整（这里是小堆）
void AdjustUp(HPDataType* a,int child)
{
	//父亲结点
	int parent = (child - 1) / 2;

	//终止条件：孩子等于0，大于0就继续调整
    //不要拿父亲作为条件,父亲和孩子都等于0的时候，paretn = (0-1)/2还是0，死循环了
    //while(parent>=0)
	while (child > 0)
	{
		//孩子小于父亲——小堆
        //如果要建大堆的话直接反过来就行了
		if (a[child] < a[parent])
		{
			//交换
			Swap(&a[child], &a[parent]);
			//继续往上迭代
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//插入X继续保持堆形态
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 (NULL == tmp)
		{
			perror("malloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	//插入
	php->a[php->size] = x;
	php->size++;
	//向上调整，最后一个位置
	AdjustUp(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
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

我们不妨来测试一下这段代码：

删除堆顶元素

开始之前，想想删除堆顶元素能干什么❓可以找出次大获知次小

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	//最小的默认为左孩子
	int minchild = 2 * parent + 1;
	while (minchild <n)
	{
		//找出小的那个孩子
		if (minchild+1<n&&a[minchild + 1] < a[minchild])
		{
			minchild++;
		}
		if (a[minchild] < a[parent])
		{
			Swap(&a[minchild], &a[parent]);
			parent = minchild;
			minchild = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
//删除堆顶元素——找出次大或者次小
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	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
31
32
33
34
35
36

判断是否为空

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
1
2
3
4
5

取堆顶元素

//返回堆顶元素
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	return php->a[0];
}
1
2
3
4
5
6
7

元素个数

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
1
2
3
4
5

打印

void HeapPrint(HP* 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

销毁

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

3.4堆的应用

3.4.1 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆
   升序：建大堆（如果建小堆的话，小堆不一定有序，只是堆顶最小，那下一个最小的数呢？如何依次选最小的数据？就算是选出来了之后，结点之间的关系就全乱了，无法继续利用优势，只能重新建堆O(N)，选出次小的数据，效率太低了）建大堆直接交换堆顶和最后一个，进行向下调整即可

   降序：建小堆

2. 堆利用堆删除思想来进行排序

   建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。回顾一下向下调整的过程：

这里的建堆，是直接用数组进行建堆，可以用向上调整算法进行建堆，也可以利用向下调整建堆，有什么区别？我们先来看代码的实现：

//建堆——a，利用向上调整建堆——O（N*longN）
	//直接插入
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/
	//建完堆之后无序，我们排个序


	//建堆——向下调整建堆(从最后一个节点的父亲开始,开始向下调整，直到根)——O(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

两种的时间复杂度不一样：向上调整建堆的时间复杂度是O（N*longN）;向下调整建堆的时间复杂度是O（N）。所以我们选用的是向下调整算法进行建堆，关于向下调整算法时间复杂度的推导过程：

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

关于向上调整算法时间复杂度的推导过程（注意红色部分，这就是这两种的区别）：

了解完以后，我们来实现堆排序：

//O(N*longN)
//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	//最小的默认为左孩子
	int minchild = 2 * parent + 1;
	while (minchild <n)
	{
		//找出小的那个孩子
		if (minchild+1<n&&a[minchild+1] < a[minchild])
		{
			minchild++;
		}
        //小堆
		if (a[minchild] < a[parent])
		{
			Swap(&a[minchild], &a[parent]);
			parent = minchild;
			minchild = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	//建堆——a，利用向上调整建堆
	//直接插入
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/
	//建完堆之后无序，我们排个序


	//建堆——向下调整建堆(从最后一个节点的父亲开始,开始向下调整，直到根)
	for (int i = (n-1-1)/2; i>=0; i--)
	{
		AdjustDown(a, n, i);
	}
	//选数
	int i = 1;
	while (i < n)
	{
		Swap(&a[0], &a[n - i]);
		AdjustDown(a, n - i, 0);
		i++;
	}

}


int main()
{
	int a[] = { 15,1,19,25,8,34,65,4,27,7 };
	HeapSort(a, sizeof(a) / sizeof(int));

	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	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

这里建的是小堆自然是降序。

3.4.2 TOP-K

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大 有人说：简单啊，排个序（NlogN），选出前K个即可。但是：如果数据量非常大，排序就不太可取了 (可能数据都不能一下子全部加载到内存中 )

最佳的方式就是用堆来解决：

1. 用数据集合中前K个元素来建堆

   前k个最大的元素，则建小堆(建大堆呢，有什么区别)

   前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

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

代码实现（这里采用前面学的文件的一些函数）：

//创建一个文件，并且随机生成一些数字
void CreateDataFile(const char* filename, int N)
{
	FILE* Fin = fopen(filename, "w");
	if (Fin == NULL)
	{
		perror("fopen fail");
		exit(-1);
	}
	srand(time(0));
	for (int i = 0; i < N; i++)
	{
		fprintf(Fin, "%d ", rand()%10000);
	}
}

//建堆，选前K个最大的数并且打印
void PrintTopK(const char* filename, int k)
{
	assert(filename);
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		exit(-1);
	}
	//小堆
	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//读前K个元素
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minHeap[i]);
	}

	//建k个数的堆
	for (int j = (k - 1 - 1) / 2; j >= 0; j--)
	{
		AdjustDown(minHeap, k, j);
	}


	//读取后N-k个
	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");

	free(minHeap);

	fclose(fout);
}

int main()
{
	int N = 10000;
	const char* filename = "Data.txt";
	int k = 10;
	CreateDataFile(filename, N);
	PrintTopK(filename, 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
71
72
73
74
75
76
77

随机生成10000以内的数字，至此，TOP-K代码的实现到这里结束。下面，我们可以来做一道OJ题目：

OJ题

最小K个数

点我

一看就是上面说的TOP-k问题，直接上手代码：

void Swap(int*p1,int*p2)
 {
     int*tmp =*p1;
     *p1 = *p2;
     *p2 = tmp;
 }
 void AdjustDown(int*a,int n,int parent)
 {
     int minchild = parent*2+1;
     while(minchild<n)
     {
         if(minchild+1<n&&a[minchild+1]>a[minchild])
         {
             minchild++;
         }
         if(a[minchild]>a[parent])
         {
             Swap(&a[minchild],&a[parent]);
             parent = minchild;
             minchild = parent*2+1;
         }
         else
         {
             break;
         }
     }
 }
int* smallestK(int* arr, int arrSize, int k, int* returnSize){
    if(k==0)
    {
        *returnSize = 0;
        return NULL;
    }
    int *minHeap = (int*)malloc(sizeof(int)*(k));
    for(int i = 0;i<k;i++)
    {
        minHeap[i] = arr[i];
    }
    //前K个数建大堆
    for(int j = (k-1-1)/2;j>=0;j--)
    {
        AdjustDown(minHeap,k,j);
    }
    //后N-K个数进入
    for(int i = k;i<arrSize;i++)
    {
        if(arr[i]<minHeap[0])
        {
            minHeap[0] = arr[i];
            AdjustDown(minHeap,k,0);
        }
    }
    *returnSize = k;
    return minHeap;
}
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

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

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。为了降低学习成本，此处手动快速创建一棵简单的二叉树，这里以简单的实现为主。后续在来讨论其创建方式：

以这颗树为例子：

#include 
#include 
#include 
typedef int BTDataType;

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


BTNode* CreatTree()
{
	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
	assert(n1);
	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
	assert(n2);
	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
	assert(n3);
	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
	assert(n4);
	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
	assert(n5);
	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
	assert(n6);

	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;
	n5->data = 5;
	n6->data = 6;

	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n2->right = NULL;
	n3->left = NULL;
	n3->right = NULL;
	n4->left = n5;
	n4->right = n6;
	n5->left = NULL;
	n5->right = NULL;
	n6->left = NULL;
	n6->right = NULL;

	return n1;
}

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

这就大概搭建起了二叉树的框架，下面，来说一说其操作：

4.1遍历操作

先序、中序、后序遍历递归操作：

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

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

//后序
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
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

我们不难发现，二叉树的遍历操作通过递归实现非常地简单，实现并不难，但是函数怎么执行的（我们这里以前序遍历为例）

前序遍历递归图解：

出去这三种遍历的方式，还有层序遍历

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

层序遍历后面会说，这里先暂时不展开了，这篇博客先说一些比较基础的知识。

4.2其他操作

结点个数

int TreeSize(BTNode* root)
{
	if (root == NULL)
		return;
	return TreeSize(root->left) +
		TreeSize(root->right) + 1;
}
1
2
3
4
5
6
7

叶结点个数

//叶子结点个数
int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
1
2
3
4
5
6
7
8
9

高度

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

求第K层结点个数

//求第K层结点个数
int TreeKLevel(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return TreeKLevel(root->left, k - 1) +
		TreeKLevel(root->right, k - 1);
}
1
2
3
4
5
6
7
8
9
10
11

返回x所在的结点

//返回X所在的结点
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

通过主函数来调用测试上面的几个函数接口：

int main()
{
	BTNode* root = CreatTree();
	PreOrder(root);
	printf("\n");

	InOrder(root);
	printf("\n");

	PostOrder(root);
	printf("\n");

	printf("Size:%d\n", TreeSize(root));

	printf("LeafSize:%d\n", TreeLeafSize(root));

	printf("TreeHeight:%d\n", TreeHeight(root));

	printf("TreeKLevel:%d\n", TreeKLevel(root,1));

	printf("Tree Find:%p\n", TreeFind(root, 6));
	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

5.总结

我们从树的概念开始，了解了树的相关知识、以及引出了二叉树的概念，了解二叉树的一些性质，通过二叉树的顺序存储，我们又认识了堆，堆的主要算法是向上调整算法以及向下调整算法，以及说了堆的应用，堆排序以及TOP-K问题，以及根据TOP-K解决实际的OJ题。最后还说了二叉树的遍历操作以及一些函数接口，在这个地方，我们并没有说得那么详细，对于二叉树的了解还是比较基础的。后面会把这一部分内容补充完整。同时，对于二叉树有了一定的了解之后，我们可以去多做一些OJ题目了，没事就去多刷刷题目。这次博客就先到这里结束了。🌹