数据结构（C语言实现）——二叉树的概念及二叉树顺序结构和链式结构的实现（堆排序+TOP-K问题+链式二叉树相关操作）_c语言二叉树堆排序

1. 前言

前面学习了数据结构中线性结构的几种结构，顺序表，链表，栈和队列等，今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点，所以本文着重介绍二叉树的相关概念和性质，以及二叉树的应用。

2. 树的概念及结构

2.1 树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
注意事项：
1.树是递归定义的
2.树形结构中，子树之间不能有交集，否则就不是树形结构

2.2 树的相关概念

如果有一棵树如下图所示：

那么它有以下概念：

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

2.3 树的表示

树在存储时，既要保存数据，也要保存结点与结点之间的关系，而且实际中树有许多种表示方法，如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。下面我们就介绍最常用的孩子兄弟表示法。

typedef int TreeDataType;
struct TreeNode
{
	TreeDataType data;//结点的数据域
	struct TreeNode* FirstChild;//指向其第一个孩子结点
	struct TreeNode* NextBrother;//指向其下一个兄弟结点
};
1
2
3
4
5
6
7

3. 二叉树的概念

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

如下图所示就是一颗二叉树：

从上图我们可以看出：

1.二叉树不存在度大于2的结点
2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

3.1 特殊二叉树

二叉树中还有俩种特殊的二叉树：

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

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

3.2 二叉树的性质

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

4. 二叉树的顺序存储

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

4.1 堆的概念

所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

4.2 堆的实现

4.2.1 堆的结点定义

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
1
2
3
4
5
6
7
8

4.2.2 堆的打印和销毁

打印：

void HeapPrint(HP* php)
{
	assert(php);
	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10

销毁：

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

4.2.3 堆的插入

先插入一个数据到数组的尾上，再进行向上调整算法，直到满足大根堆或者小根堆。
向上调整算法：以小根堆来举例，从该结点开始向上找父结点，如果该结点小于父结点，就把该结点和父结点交换，继续向上调整，直到满足小根堆。

插入：

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*)malloc(sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("malloc");
			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

向上调整算法：

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;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

交换：

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
1
2
3
4
5
6

4.2.4 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
向下调整算法：以小根堆来举例，从该结点开始向下找子结点，如果子结点小于该结点，就把子结点和该结点交换，再继续向下调整，直到满足小根堆

删除：

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

向下调整算法：

void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && (a[child + 1] < a[child]))
		{
			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

4.2.5 取堆顶数据

堆顶元素就是数组下标为0的元素

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
1
2
3
4
5
6

4.2.6 堆的判空

size为0即为空

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

4.2.7 堆的数据个数

size的大小就是数据个数

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

4.3 堆的应用

4.3.1 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：
1.建堆
升序：建大堆
降序：建小堆
2.利用堆删除思想来进行排序

void HeapSort(int* arr, int size)
{
	//排升序建大堆，排降序建小堆
	//向上调整建堆O(N*logN)
	//int i = 0;
	//for (i = 1; i < size; i++)
	//{
	//	AdjustUp(arr, i);
	//}

	//向下调整建堆O(N)
	int i = 0;
	for (i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, size, i);
	}

	int end = size - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}
}

int main()
{
	int arr[10] = { 23,45,48,123,12,49,80,15,5,35 };
	HeapSort(arr, 10);
	int i = 0;
	for (i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
	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

4.3.2 TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
思路：
1.用数据集合中前K个元素来建堆
求前k个最大的元素，则建小堆
求前k个最小的元素，则建大堆
2.用剩余的N - K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N - K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

void PrintTopK(int* a, int n, int k)
{
	//1.建堆--用a中前k个元素建堆
	int* kMaxHeap = (int*)malloc(sizeof(int)*k);
	assert(kMaxHeap);
	int i = 0;
	for (i = 0; i < k; i++)
	{
		kMaxHeap[i] = a[i];
	}
	for (i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kMaxHeap, k, i);
	}

	//2.将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	int j = 0;
	for (j = k; j < n; j++)
	{
		if (a[j] > kMaxHeap[0])
		{
			kMaxHeap[0] = a[j];
			AdjustDown(kMaxHeap, k, 0);
		}
	}
	for (i = 0; i < k; i++)
	{
		printf("%d ", kMaxHeap[i]);
	}
}

void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	for (int i = 0; i < n; i++)
	{
		a[i] = rand() % 1000000;
	}
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	PrintTopK(a, n, 10);
}

int main()
{
	TestTopk();
	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

5. 二叉树的链式存储

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

5.1 链式二叉树的结点定义

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;
1
2
3
4
5
6
7
8

5.2 结点创建

BTNode* CreatBTNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	assert(node);
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
1
2
3
4
5
6
7
8
9

由于二叉树的创建比较复杂，所以下面我们来手动模拟一个简单的二叉树，便于后边操作的实现

5.3 模拟创建二叉树

BTNode* CreatBinaryTree()
{
	BTNode* node1 = CreatBTNode(1);
	BTNode* node2 = CreatBTNode(2);
	BTNode* node3 = CreatBTNode(3);
	BTNode* node4 = CreatBTNode(4);
	BTNode* node5 = CreatBTNode(5);
	BTNode* node6 = CreatBTNode(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

5.4 二叉树的遍历

二叉树的遍历有：前序/中序/后序/层序的递归结构遍历：
1.前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2.中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3.后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
4.层序遍历(Level Traversal)——从所在二叉树的根结点出发，首先访问第一层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

5.4.1 前序遍历

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}

	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12

5.4.2 中序遍历

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12

5.4.3 后序遍历

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}
1
2
3
4
5
6
7
8
9
10
11
12

5.4.4 层序遍历

层序遍历稍微复杂一点，需要队列来实现，我们这里就之前使用之前创建好的队列，不再过多展示，核心思路是：先判断该结点是不是空，如果不是就进队，再判断队是不是空，如果不是先打印出此时队头元素，然后删除队头元素，接下来再分别判断打印的队头元素的左孩子和右孩子是不是为空，不是空就继续入队。这样循环迭代即层序遍历。

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	QueueDestroy(&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

5.5 二叉树结点个数及高度等操作

5.5.1 二叉树的结点个数

因为二叉树的左子树和右子树都可以分别看成单独的二叉树，所以核心思路是递归计算左子树和右子树的结点个数，最后返回再加1就是该二叉树的结点个数。

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

5.5.2 二叉树叶子结点的个数

左右子树都为空的结点就是叶子结点，这里也采用递归的思路，把二叉树分为左子树和右子树，左子树也可以分为左子树和右子树，递归计算并返回即可求的整棵树的叶子结点个数。

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5.5.3 二叉树第k层的结点个数

这里的思路是，求根结点的第k层的结点个数，可以转换成求该结点的左孩子的第k-1层的结点个数+该结点的右孩子的第k-1层的结点个数，递归下去，结束后返回的即为根结点第k层的结点个数。

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

	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

5.5.4 查找二叉树中值为x的结点

这里的思路是，如果该结点就是要求的结点，直接返回该结点，如果不是就递归查找该结点的左子树和右子树，找到就返回。

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5.5.5 计算二叉树的深度

二叉树的深度就是该二叉树的左子树和右子树的最大深度再+1，这里的思路是，递归计算左子树的深度和右子树的深度，每次返回都是以某个结点为根的二叉树的深度，最后返回的就是该二叉树的深度。

int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int LeftDepth = BinaryTreeDepth(root->left);
	int RightDepth = BinaryTreeDepth(root->right);

	return LeftDepth > RightDepth ? LeftDepth + 1 : RightDepth + 1;

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

5.5.6 判断是否为完全二叉树

这里也要用到队列，核心思路是利用完全二叉树的性质，完全二叉树的非空结点一定是连在一起的，一旦出现空结点，则空结点后面的所有结点都应该为空，如果还有非空结点，就不是完全二叉树。

int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
		else
		{
			break;
		}
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}
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

6. 结尾

到这里，二叉树的概念及二叉树顺序结构和链式结构的实现和应用就介绍完了，二叉树作为数据结构中的重点和难点需要反复学习，理解透彻，非常考验大家的理解能力和基本功，本人也是一个初学者，文中难免有很多地方出现错误和纰漏，此文仅供大家学习和参考。如果本文对大家学习二叉树有帮助的话，博主感到非常荣幸。
最后，感谢各位大佬的耐心阅读和支持，觉得本篇文章写的不错的朋友可以三连关注支持一波，如果有什么问题或者本文有错误的地方大家可以私信我，也可以在评论区留言讨论，再次感谢各位。