【数据结构】二叉树-堆（下）-链式二叉树

个人主页~

二叉树-堆（上）
栈和队列

---

四、堆的代码实现

Heap.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;
// 堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
void AdjustUp(HPDataType* a, int child); 
//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);

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

Heap.c

#include "Heap.h"

void Swap(HPDataType* n1, HPDataType* n2)
{
	HPDataType* tmp = *n1;
	*n1 = *n2;
	*n2 = tmp;
}

void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if(hp->capacity == hp->size)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size - 1);
}

void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown(hp->a, hp->size, 0);
}

HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->a[0];
}

int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}

int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

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

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[parent], &a[child]);
			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
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

test.c

#include "Heap.h"

int main()
{
	Heap h;
	HeapInit(&h);
	HeapPush(&h, 1);
	HeapPush(&h, 4);
	HeapPush(&h, 7);
	HeapPush(&h, 2);
	HeapPush(&h, 5);
	HeapPush(&h, 9);
	printf("%d\n", HeapTop(&h));

	HeapPop(&h);
	printf("%d", HeapTop(&h));

	HeapDestory(&h);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

五、堆的应用

堆排序思想进行排序

我们在上面实现了堆，如果想要升序数组就建大堆，降序数组就建小堆
但建堆并不意味着建完就可以了，想要升序/降序数组的话，建完大堆/小堆后用向下调整算法将堆调整成小堆/大堆，这样调整出来的堆就是一个升序/降序数组

在排序当中，堆排序是一种时间复杂度较低的排序，要远优于冒泡排序，在使用堆排序时，要使用向下调整算法，这样我们就可以最大限度的减少时间的使用

在堆排序中有一个很经典的问题就是TopK问题，即一堆数据，个数为n（n>>k）,求这堆数据中最大/最小的k个数据
如果是求前k个最大的元素，则用前k个元素建小堆
如果是求前k个最小的元素，则用前k个元素建大堆
然后再用剩下的n-k个元素一次与堆顶元素来比较，不满足则替换堆顶元素
也就是说，我们用求前k个最大数据来举例，我们先将整组数据的前k个元素建一个小堆，小堆的根是整个堆里最小的，用它来和剩余的n-k个元素比较，如果剩余的元素中的某一个比小堆根大，那么就替换掉，再用向下调整算法调整，这样一来，最大的数据都沉底了，堆中最小的数据继续与剩余的数据比较，重复上述步骤，当所有剩余元素都比完了之后，剩下的这个小堆就是前k个最大数

六、二叉树链式结构的实现

BTree.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef char BTDataType;

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

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode* root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(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

BTree.c

#define _CRT_SECURE_NO_WARNINGS

#include "BTree.h"

BTNode* BuyNode(BTDataType x)
{
	BTNode* new = (BTNode*)malloc(sizeof(BTNode));
	if (new == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	new->data = x;
	new->left =  NULL;
	new->right = NULL;

	return new;
}

BTNode* BinaryTreeCreate(BTDataType* a,int n, int* pi) 
{
    if (*pi >= n || a[*pi] == '#')
	{ 
		// 如果到达数组末尾或遇到#，则返回NULL  
        (*pi)++;
        return NULL;
    }

	BTNode* node = BuyNode(a[*pi]);
    (*pi)++; // 移动到下一个节点  

    node->left = BinaryTreeCreate(a, n, pi); // 递归创建左子树  
    node->right = BinaryTreeCreate(a, n, pi); // 递归创建右子树  

    return node;
}

void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

int BinaryTreeSize(BTNode* root)
{
	//return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
	if (root == NULL)
		return 0;
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

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);
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data = x)
		return root;
	BTNode* ret1 = BinaryTreeFind(root->left, x);

	if (ret1)
		return ret1;

	BTNode* ret2 = BinaryTreeFind(root->right, x);

	if (ret2)
		return ret2;

	return NULL;
}

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

}

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

}

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	BinaryTreeInOrder(root->left);
	BinaryTreeInOrder(root->right);
	printf("%c ", 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
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

test.c

#define _CRT_SECURE_NO_WARNINGS

#include "BTree.h"


int main()
{
	int i = 0;
	BTDataType val[] = { "ABD##E#H##CF##G##" };

	BTNode* tree = BinaryTreeCreate(val, 17, &i);
	BinaryTreePrevOrder(tree);
	printf("\n");
	BinaryTreeInOrder(tree);
	printf("\n");
	BinaryTreePostOrder(tree);
	printf("\n");
	
	printf("%d\n", BinaryTreeSize(tree));

	printf("%d\n", BinaryTreeLeafSize(tree));

	printf("%d\n", BinaryTreeLevelKSize(tree,3));


	BinaryTreeDestory(tree);
	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

---

下一篇我们来详细剖析链式二叉树的实现~