【数据结构】— 二叉树之「堆」的实现

 ꧁   各位大佬们好！很荣幸能够得到您的访问，让我们一起在编程道路上任重道远！꧂

☙ 博客专栏：【数据结构初阶】❧

⛅ 本篇内容简介：数据结构初阶中二叉数的详解以及利用二叉树去实现「堆」结构。

⭐ 了解作者：励志成为一名编程大牛的学子，目前正在升大二的编程小白。

✍励志术语：编程道路的乏味，让我们一起学习变得有趣！

文章目录

 树的概念及结构

 树的概念

 树的相关概念

 树的表示

 树在实际中的运用（表示文件系统的目录树结构）

  二叉树概念及结构

 概念

  现实中的二叉树

  特殊的二叉树

 1. 满二叉树

  2. 完全二叉树

 堆的概念及结构

  堆的性质

 堆的实现

 堆的结构

  堆的初始化

 堆的销毁

 堆的打印

 获取堆顶部的数据

 堆的数据个数

 堆的判空

 堆的插入（向上调整算法）

 堆的删除（向下调整算法）

 堆实现的测试

  实现堆的源代码

 Heap.h文件

 Heap.c文件

 Test.c文件

 结束语

 树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合，把它叫做树是因为它看起来像一棵倒挂的树，也就是说它的根朝上，而叶朝下。

 

⬝ 有一个特殊的结点，称为根结点，根结点没有前驱结点。

⬝ 除根结点外，其余结点被分为M（M>0）个互不相交的集合T1，T2，.......，Tm，其中每一个集合Ti（1<=i<=m）又是一棵结构与树类似的子树。每棵子树的根结点有且只有只有一个前驱，可以有0个或者多个后继。

⬝ 因此，树是递归定义的。

       现实结构的树：                                                                                        逻辑结构的树：

 注意：树形结构中，子树之间不能有交集，否则就不能算是树形结构。（我们称这种为：图）

 像这种的我们就不能称为树：

 注意：

⧆  子树是不相交的。

⧆  除了根结点外，每个结点有且仅有一个父结点。

⧆  一棵N个结点的树有（N-1）条边。

 树的相关概念

 

 带✅的为重点理解对象;

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：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）棵互不相交的树的集合称为森林。

 树的表示

树的结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方法，如：双亲表示法，孩子表示法，孩子双亲表示法以及孩子兄弟表示法等，这里我介绍其中最常用的孩子兄弟表示法：

我们先看图，再来用代码表示：

 代码实现：

typedef int DataType;

struct Node
{
	struct Node* child;//左边孩子结点
	struct Node* brother;//右边兄弟结点
	DataType Data;//数据域
};

 树在实际中的运用（表示文件系统的目录树结构）

 这是Linux操作系统中的树状目录结构（逻辑结构），下图是实际中的Linux目录：

---

  二叉树概念及结构

 概念

一棵二叉树是结点的一个有限集合，该集合：

➀  或者为空

➁ 由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

 从上图可以看出：

❶  二叉树不存在度大于2的结点。

❷  二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

注意：对于任意的二叉树都是由以下几种情况复合而成的：

  现实中的二叉树

  特殊的二叉树

 1. 满二叉树

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

  2. 完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的，对于深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一   一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。而完全二叉树不一定是满二叉树。完全二叉树结点数量的范围为【2^(k-1),2^k-1】。

 堆的概念及结构

如果有一个关键码的集合k={k0，k1，k2，......，k(n-1)}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki<=K(2*i+1)且Ki<=K(2*i+2)（Ki>=K(2*i+1)且Ki>=K(2*i+2)）i=0,1,2,......，称为小堆（或者大堆）。将根节点的最大的堆叫做最大堆或者大根堆，根节点最小的堆叫做最小堆或小根堆。

  堆的性质

⓵  堆中某个节点的值总是不大于或不小于其父节点的值。

⓶  堆总是一棵完全二叉树。

我们来看看什么是大根堆以及小根堆，以及父子关系的公式：

 所以我们可以推出一个父子关系的公式：

leftchild=parent*2+1           rightchild=parent*2+2

parent=(child-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

 所以我们利用画图工具，可以知道这题选A。

 堆的实现

在实现堆的过程中我们重点讲一下堆的插入与删除，其他的接口我们在实现顺序表的时候以及讲解过了。

 堆的结构

typedef int HPDataType;

//利用顺序表实现堆
typedef struct Heap
{
	HPDataType* arr;//存放数据的数组
	int size;//数据的有效个数
	int capacity;//数组的容量
}Heap;

---

  堆的初始化

//堆的初始化
void HeapInit(Heap* php);

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

---

 堆的销毁

//堆的销毁
void HeapDestroy(Heap* php);

//堆的销毁
void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->arr);
	php->arr = NULL;
	php->capacity = php->size = 0;
}

---

 堆的打印

//堆的打印
void HeapPrint(Heap* php);

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

---

 获取堆顶部的数据

注意：堆顶部的数据是size==0的位置的数据。

//获取堆顶的数据
HPDataType HeapTop(Heap* php);

//获取堆顶的数据
HPDataType HeapTop(Heap* php)
{
	assert(php);
	//对堆进行判空
	assert(!HeapEmpty(php));

	return php->arr[0];
}

---

 堆的数据个数

//堆的数据个数
int HeapSize(Heap* php);

//堆的数据个数
int HeapSize(Heap* php)
{
	assert(php);

	return php->size;
}

---

 堆的判空

//堆的判空
bool HeapEmpty(Heap* php);

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

	return php->size == 0;//等于0为真，取反就是有数据
}

---

 堆的插入（向上调整算法）

//堆的插入
void HeapPush(Heap* php, HPDataType x);

假设要插入一个10，我们先把这个数据插入到数组的尾上，再进行向上调整算法，直到满足一个堆的形式。

图解思路：

 代码实现：

//交换函数
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
	assert(arr);

	int parent = (child - 1) / 2;
	while (child > 0)//循环停止条件
	{
		if (arr[parent] > arr[child])
		{
			//进行交换
			Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}


//堆的插入
void HeapPush(Heap* php, HPDataType x)
{
	assert(php);
	//检查扩容
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		Heap* tmp = (Heap*)realloc(php->arr, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			//扩容失败
			perror("realloc fail");
			exit(-1);//直接结束
		}
		//扩容成功
		php->capacity = newcapacity;
		php->arr = tmp;
	}
	//在尾部插入数据
	php->arr[php->size] = x;
	php->size++;

	//向上调整    数组和这个位置
	AdjustUp(php->arr, php->size - 1);
}

---

 堆的删除（向下调整算法）

//堆的删除
void HeapPop(Heap* php);

删除堆就是删除堆顶的数据，将堆顶的数据跟最后一个数据交换，如何删除最后一个数据，再进行向下调整算法。

图解思路;

代码实现：

//向下调整算法
void AdjustDown(HPDataType* arr, int n, int parent)
{
	assert(arr);
	//假设左边的孩子小
	int minchild = 2 * parent + 1;
	while (minchild  arr[minchild])
		{
			Swap(&arr[parent], &arr[minchild]);
			parent = minchild;
			minchild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


//堆的删除
void HeapPop(Heap* php)
{
	assert(php);
	//判空
	assert(!HeapEmpty(php));

	//交换数据
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;

	//向下调整算法
	AdjustDown(php->arr, php->size, 0);
}

---

 堆实现的测试

先插入一个数组元素，再插入一个元素，判断是否为堆。

数组为：int arr[] = { 27,15,19,18,28,34,65,49,25,37 };

int main()
{
	Heap hp;
	HeapInit(&hp);
	//测试插入
	int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		HeapPush(&hp, arr[i]);
	}

	HeapPush(&hp, 10);
	HeapPrint(&hp);

	//测试删除
	HeapPop(&hp);
	HeapPrint(&hp);

	//销毁
	HeapDestroy(&hp);

	return 0;
}

测试结果：

---

  实现堆的源代码

 Heap.h文件

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

typedef int HPDataType;

//利用顺序表实现堆
typedef struct Heap
{
	HPDataType* arr;//存放数据的数组
	int size;//数据的有效个数
	int capacity;//数组的容量
}Heap;

//堆的初始化
void HeapInit(Heap* php);

//堆的销毁
void HeapDestroy(Heap* php);

//堆的打印
void HeapPrint(Heap* php);

//堆的插入
void HeapPush(Heap* php, HPDataType x);

//堆的删除
void HeapPop(Heap* php);

//获取堆顶的数据
HPDataType HeapTop(Heap* php);

//堆的数据个数
int HeapSize(Heap* php);

//堆的判空
bool HeapEmpty(Heap* php);

---

 Heap.c文件

#include"Heap.h"

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

//堆的销毁
void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->arr);
	php->arr = NULL;
	php->capacity = php->size = 0;
}

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

//获取堆顶的数据
HPDataType HeapTop(Heap* php)
{
	assert(php);
	//对堆进行判空
	assert(!HeapEmpty(php));

	return php->arr[0];
}

//堆的数据个数
int HeapSize(Heap* php)
{
	assert(php);

	return php->size;
}

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

	return php->size == 0;//等于0为真，取反就是有数据
}

//交换函数
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
	assert(arr);

	int parent = (child - 1) / 2;
	while (child > 0)//循环停止条件
	{
		if (arr[parent] > arr[child])
		{
			//进行交换
			Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}


//堆的插入
void HeapPush(Heap* php, HPDataType x)
{
	assert(php);
	//检查扩容
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		Heap* tmp = (Heap*)realloc(php->arr, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			//扩容失败
			perror("realloc fail");
			exit(-1);//直接结束
		}
		//扩容成功
		php->capacity = newcapacity;
		php->arr = tmp;
	}
	//在尾部插入数据
	php->arr[php->size] = x;
	php->size++;

	//向上调整    数组和这个位置
	AdjustUp(php->arr, php->size - 1);
}

//向下调整算法
void AdjustDown(HPDataType* arr, int n, int parent)
{
	assert(arr);
	//假设左边的孩子小
	int minchild = 2 * parent + 1;
	while (minchild < n)
	{
		//找最小的孩子
		if (minchild + 1 < n && arr[minchild + 1] < arr[minchild])
		{
			minchild++;
		}
		if (arr[parent] > arr[minchild])
		{
			Swap(&arr[parent], &arr[minchild]);
			parent = minchild;
			minchild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


//堆的删除
void HeapPop(Heap* php)
{
	assert(php);
	//判空
	assert(!HeapEmpty(php));

	//交换数据
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;

	//向下调整算法
	AdjustDown(php->arr, php->size, 0);
}

---

 Test.c文件

#include"Heap.h"

int main()
{
	Heap hp;
	HeapInit(&hp);
	//测试插入
	int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		HeapPush(&hp, arr[i]);
	}

	HeapPush(&hp, 10);
	HeapPrint(&hp);

	//测试删除
	HeapPop(&hp);
	HeapPrint(&hp);

	//销毁
	HeapDestroy(&hp);

	return 0;
}

---

 结束语

各位大佬好，二叉树的初步讲解就到这里了，以及如何利用顺序表去实现二叉树中的堆的数据结构，当然二叉树的部分非常重要，这也只是讲解了其中的百分之60，剩下的部分知识在以后的博客会更新哦，想了解后续，那就关注博主叭！！！

 
学计算机的大学生都关注它了