数据结构之树 --- 二叉树＜堆＞

1. 树是什么？

1.1 树的表示

2. 二叉树

2.1 二叉树的概念

2.2 特殊的二叉树

2.3 二叉树的性质

2.4 二叉树的存储结构

2.4.1 顺序存储

2.4.2 链式存储

3. 二叉树顺序结构的实现 <堆>

3.1 二叉树的顺序结构

编辑 3.2 堆的概念及结构

编辑 3.3 堆的实现（以小堆为例）

3.3.1 堆结构的定义

3.3.2 向下调整算法 <此处向下调整代码以整棵树的根节点为例 >

概念

代码展示

3.3.3 向上调整算法

概念

代码展示 <此处向上调整代码以最后一个节点为例 >

3.3.4 堆的插入

堆的插入示例图

代码展示

3.3.5 堆的删除

堆的删除示例图

3.4 堆的代码实现

1. 树是什么？

数据结构中的树是一种非线性数据结构。树这个概念用来描述具有层级关系的结构。

树的数据结构的主要特征和概念包括：

- 节点(Node):树中信息的基本单位。

- 根节点(Root Node):树中位于最顶层的节点，没有父节点。

- 子节点(Child Node):相对于父节点而言的下级节点。

- 父节点(Parent Node):相对于子节点而言的上级节点。

- 叶节点(Leaf Node):没有子节点的节点。

- 分支(Branch):连接节点的边。

- 枝(Edge):连接两个节点的关系。

- 子树(Subtree):以某个节点为根的树形结构。

- 树的高度(Height):从根节点到最远叶节点的最长路径上的边数。

- 树的度(Degree):一个节点的子节点数目。

常见的树数据结构包括二叉树、B树、平衡树、哈夫曼树等。它们通过节点和边构成了一个包含层级关系的抽象数据模型，广泛应用于文件系统、网络协议、表达式求值等领域。

树的数据结构相对线性表而言，支持有效地表达具有分层关系的结构化数据。它是理解递归和分治算法的重要基础。

如下图就是一个树结构。

切记树形结构中，子树之间不能有交集。

1.1 树的表示

树结构相对于线性表复杂很多，我们不但要保存树结构每一个节点的值，还要保存节点之间的关系。

例如我们使用孩子兄弟表示法：

2. 二叉树

2.1 二叉树的概念

二叉树是一个节点构成的有限集合，该集合：

1.或者为空；

2.或者由一个根节点与两棵别称为左子树和右子树的二叉树组成。

由其概念可知，二叉树不存在度大于2的节点，且二叉树分为左右子树，不能颠倒，是有序树。因而二叉树可分为以下几种情况：

2.2 特殊的二叉树

满二叉树：

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

完全二叉树：

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

话不多说，上图：

2.3 二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)个结点。
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^h-1。
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有 n0=n2+1;
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log^(n+1)。 (ps：log^(n+1) 是log以2为底，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否则无右孩子

2.4 二叉树的存储结构

二叉树的存储结构也分为顺序存储与链式存储。

2.4.1 顺序存储

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

2.4.2 链式存储

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

左右孩子表示法：

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* pLeft; // 指向当前节点左孩子
struct BinTreeNode* pRight; // 指向当前节点右孩子
BTDataType data; // 当前节点值域
}

3. 二叉树顺序结构的实现 <堆>

3.1 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

完全二叉树使用数组存储不会由空间浪费。

而非完全二叉树将会造成大量的空间浪费。

3.2 堆的概念及结构

概念：

堆是一种重要的数据结构，主要特点如下：

堆是一棵完全二叉树。

堆分为大堆和小堆。

最大堆：每个节点的值都大于或等于其子节点的值。

最小堆：每个节点的值都小于或等于其子节点的值。

堆的根节点分别为最大值(最大堆)或最小值(最小堆)。

堆支持两种基本操作：插入一个元素和删除根节点。

插入：新元素添加到叶子节点，然后不断与父节点比较交换位置，直到符合堆的性质。时间复杂度O(logN)。

删除根节点：将最后一个叶子节点移到根，然后与子节点比较交换位置重建堆。时间复杂度也是O(logN)。

堆常用于优先级队列，支持快速获取最大/最小元素，以及插入和删除操作。

所以总结来说，堆是一种特殊的完全二叉树结构，能够快速支持获取最大/最小元素和插入/删除操作，广泛应用于优先级队列等数据结构中。它通过维护节点值的堆积性质来实现高效操作。

3.3 堆的实现（以小堆为例）

3.3.1 堆结构的定义

typedef struct Heap
{
	HPDataType* a;//存放数据的数组
	int size;//数组内的元素个数
	int capacity;//数组的容量
}Heap;

要实现堆，我们就必须对向下调整算法和向上调整算法有一个明确的认知。

3.3.2 向下调整算法 <此处向下调整代码以整棵树的根节点为例 >

概念

从上向下调整，以某个节点为根节点，比较其左孩子与右孩子的大小，选择其中小的和父节点相比，如果小于父节点，则交换值，更新父节点与子节点，循环往复。

大堆则寻找最大值。

代码展示

void ADjustdown(Heap* hp)
{
	int parent = 0;//以根节点为始
	int child = parent * 2 + 1;//求该节点的孩子，此刻计算的为左孩子
//后续比较左孩子与右孩子的大小，谁小谁做孩子
	while (child<hp->size)//左孩子存在
	{
	
		if (child + 1 < hp->size && hp->a[child + 1] < hp->a[child])//右孩子存在且小于左孩
		{
			child = child + 1;//将右节点赋值给孩子几点
		}
		if (hp->a[child] < hp->a[parent])//孩子节点的值小于父节点
		{
			swap(&hp->a[child], &hp->a[parent]);//交换父节点与孩子节点data
			parent = child;//更新父节点的下标位置
			child = parent * 2 + 1;//计算下一轮孩子节点的下标
		}
		else
			break;
	}
}

3.3.3 向上调整算法

概念

从下向上调整，以某个节点为子节点，比较该节点与父节点的大小，如果小于父节点，则交换并更新父子节点。大堆则相反。

代码展示 <此处向上调整代码以最后一个节点为例 >

void ADjustup(Heap* hp)
{
	int child = hp->size - 1;//size是元素个数，所以最后一个元素的下标为size-1
    //以最后一个元素为始
	int parent = (child - 1) / 2;//求其父节点
	while (child > 0)//孩子节点存在
	{
		if (hp->a[child] < hp->a[parent])//如果父节点大于子节点，则交换，并更新父子结点
		{
			swap(&(hp->a[child]), &(hp->a[parent]));
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
			break;
	}
}

3.3.4 堆的插入

堆的插入是在堆尾插入，然后借用向上调整算法，直到满足堆。

堆的插入示例图

代码展示

void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	assert(hp->a);

	if (hp->size == hp->capacity)//如果堆已满，则进行扩容
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = realloc(hp->a, sizeof(HPDataType) * newcapacity);
		assert(tmp);
		hp->a = tmp;
		hp->capacity = newcapacity;
	}

	hp->a[hp->size] = x;
	hp->size++;
	ADjustup(hp);//向上调整
}

3.3.5 堆的删除

堆的删除是删除堆的根节点，即交换堆顶与堆尾元素，然后删除堆尾，再进行向下调整算法。

堆的删除示例图

代码展示

void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);
	swap(&(hp->a[0]), &(hp->a[hp->size - 1]));
	hp->size--;
	ADjustdown(hp);
}

3.4 堆的代码实现

Heap.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;

// 堆的构建
void HeapCreate(Heap* hp, int n);

// 堆的销毁
void HeapDestory(Heap* hp);

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

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

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

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

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

Heap.c

#include"heap.h"
void HeapCreate(Heap* hp, int n)
{
	assert(hp);
	hp->size = 0;
    hp->capacity = n;
	hp->a = (HPDataType*)malloc(sizeof(HPDataType) * hp->capacity);
}

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	assert(hp->a);
	free(hp->a);
	hp->a = NULL;
}

void swap(HPDataType* a, HPDataType* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void ADjustup(Heap* hp)
{
	int child = hp->size - 1;
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (hp->a[child] < hp->a[parent])
		{
			swap(&(hp->a[child]), &(hp->a[parent]));
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
			break;
	}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	assert(hp->a);

	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = realloc(hp->a, sizeof(HPDataType) * newcapacity);
		assert(tmp);
		hp->a = tmp;
		hp->capacity = newcapacity;
	}

	hp->a[hp->size] = x;
	hp->size++;
	ADjustup(hp);
}

void ADjustdown(Heap* hp)
{
	int parent = 0;
	int child = parent * 2 + 1;
	while (child<hp->size)
	{
	
		
		if (child + 1 < hp->size && hp->a[child + 1] < hp->a[child])
		{
			child = child + 1;
		}
		if (hp->a[child] < hp->a[parent])
		{
			swap(&hp->a[child], &hp->a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;

	}
}
// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);
	swap(&(hp->a[0]), &(hp->a[hp->size - 1]));
	hp->size--;
	ADjustdown(hp);
}

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->size>0);
	return hp->a[0];
}

// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}

// 堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

本篇文章就到这里啦，下期我们与链树相会！