【初阶数据结构08】——树的基本概念与堆的基本功能实现
文章目录
前言
在计算机科学中，树是一种非常重要的非线性数据结构，它以层次化的方式组织数据，广泛应用于文件系统、编译原理、数据库索引等领域。而堆作为一种特殊的完全二叉树，不仅实现了高效的优先队列，更是堆排序算法的核心。本文将带你从树的基础概念出发，逐步深入堆的实现，并最终掌握堆排序的原理与代码编写。
一、树的概念
1.1 树的定义
树（Tree）是由 n（n≥0）个有限结点组成的一个具有层次关系的集合。当 n=0 时，称为空树。在任意一棵非空树中：
- 有且仅有一个特定的结点称为根结点，根结点没有前驱结点。
- 除根结点外，其余结点可以分成 M（M>0）个互不相交的有限集合 T₁、T₂、...、Tₘ，其中每一个集合本身又是一棵树，称为根结点的子树。
树的定义是递归的：树由根和若干互不相交的子树构成，而子树本身也是一棵树。
1.2 树的相关术语
- 结点的度：一个结点拥有的子树个数。
- 叶结点（终端结点）：度为 0 的结点。
- 分支结点（非终端结点）：度不为 0 的结点。
- 父结点与子结点：若结点 A 有孩子 B，则 A 是 B 的父结点，B 是 A 的子结点。
- 兄弟结点：具有相同父结点的结点。
- 树的度：树中所有结点的度的最大值。
- 结点的层次：从根开始定义，根为第 1 层，根的子结点为第 2 层，以此类推。
- 树的高度（深度）：树中结点的最大层次。
- 森林：由 m（m≥0）棵互不相交的树组成的集合。
1.3 树的表示
在实际编程中，我们需要用某种数据结构来存储树。树有多种表示方法，如双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法等。最常用的是孩子兄弟表示法（也称为左孩子右兄弟表示法）。这种表示法可以将任意一棵树转化为二叉树的形式，从而方便地使用二叉树的算法进行处理。
孩子兄弟表示法的结点结构如下：
typedef int DataType; struct Node { struct Node* firstChild; // 指向第一个孩子结点 struct Node* pNextBrother; // 指向下一个兄弟结点 DataType data; // 结点中的数据域 };
1.4 树在实际中的应用
树结构在计算机中应用广泛，最典型的例子就是文件系统的目录树结构。根目录类似于树的根结点，子目录和文件则对应分支结点和叶结点。通过树形结构，我们可以高效地组织和管理文件。
二、二叉树概念及结构
2.1 二叉树的定义
二叉树（Binary Tree）是每个结点最多有两个子树的树结构，并且子树有左右之分，次序不能颠倒。二叉树的定义也是递归的：
- 要么为空树；
- 要么由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。
2.2 现实中的二叉树
2.3 特殊的二叉树
- 满二叉树：如果一棵二叉树的每一层结点数都达到最大值，即深度为 k 的满二叉树有 2^k - 1 个结点，那么它就是满二叉树。满二叉树的特点是所有分支结点都有左右子树，且叶结点都在最底层。
- 完全二叉树：对于深度为 k 的二叉树，如果其结点与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应（即从上到下、从左到右编号），则称为完全二叉树。完全二叉树的特点是：
- 叶结点只可能出现在最后两层；
- 最后一层的叶结点都靠左排列；
- 若某个结点没有左孩子，则一定没有右孩子。
满二叉树是特殊的完全二叉树。
2.4 二叉树的性质
二叉树具有以下重要性质（假设根结点层数为 1）：
- 第 i 层最多结点数：在二叉树的第 i 层上，最多有 2^(i-1) 个结点（i ≥ 1）。
- 深度为 h 的最大结点数：深度为 h 的二叉树最多有 2^h - 1 个结点。
- 叶子结点数与度为 2 的结点数的关系：对任意非空二叉树，若叶子结点数为 n₀，度为 2 的结点数为 n₂，则 n₀ = n₂ + 1。这一性质可以通过总边数关系推导得出：
- 总结点数 N = n₀ + n₁ + n₂
- 总边数 = N - 1 = n₁ + 2n₂
- 联立得 n₀ = n₂ + 1
- 具有 n 个结点的完全二叉树深度：h = ⌊log₂(n)⌋ + 1（或 h = ⌈log₂(n+1)⌉）。
- 完全二叉树结点编号特性：若对完全二叉树按从上到下、从左到右从 0 开始编号，则对于编号为 i 的结点：
- 若 i > 0，其父结点编号为 (i-1)/2；
- 若 2i+1 < n，其左孩子编号为 2i+1，否则无左孩子；
- 若 2i+2 < n，其右孩子编号为 2i+2，否则无右孩子。
2.5 二叉树的存储结构
二叉树有两种常用的存储方式：顺序存储和链式存储。
1. 顺序存储
顺序存储使用数组来存放二叉树的结点。对于完全二叉树，这种存储方式非常高效，因为结点在数组中的位置可以直接反映其逻辑关系（利用上述编号特性）。但对于非完全二叉树，数组会浪费大量空间，因此通常只用于完全二叉树（如堆）。
2. 链式存储
链式存储使用结点结构体，每个结点包含数据域以及指向左孩子和右孩子的指针。这是最常用的二叉树存储方式，结构如下：
typedef int BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; // 指向当前结点左孩子 struct BinaryTreeNode* right; // 指向当前结点右孩子 BTDataType data; // 当前结点值域 } BTNode;三、堆的概念与结构
3.1 堆的定义
如果有一个关键码的集合 K = {k₀, k₁, k₂, ..., kₙ₋₁}，将其所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：
- 大堆（大根堆）：任意结点的值都大于或等于其左右孩子结点的值，即 Kᵢ ≥ K₂ᵢ₊₁ 且 Kᵢ ≥ K₂ᵢ₊₂。
- 小堆（小根堆）：任意结点的值都小于或等于其左右孩子结点的值，即 Kᵢ ≤ K₂ᵢ₊₁ 且 Kᵢ ≤ K₂ᵢ₊₂。
堆具有以下性质：
- 堆中某个结点的值总是不大于或不小于其父结点的值。
- 堆总是一棵完全二叉树。
3.2 堆的存储结构
堆通常使用顺序存储，即用一个一维数组来存储堆中的所有结点。由于堆是完全二叉树，数组下标可以自然映射结点位置：
- 若根结点下标为 0，则对于下标为 i 的结点：
- 父结点下标：(i - 1) / 2
- 左孩子下标：2 * i + 1
- 右孩子下标：2 * i + 2
四、堆的基本功能实现
下面我们以小堆为例，实现一个动态增长的堆。我们将提供以下接口：
typedef int HeapdataType; typedef struct Heap { HeapdataType* arr; int size;//这里的size指向最后一个元素的下一个位置，初始化时置为0 int capacity; }Hp; void HeapInit(Hp* hp); void HeapDestroy(Hp* hp); void Swap(HeapdataType* n1, HeapdataType* n2); void AdjustUp(HeapdataType* arr,int child); void HeapPush(Hp* hp, HeapdataType x); void AdjustDown(HeapdataType* arr, int size, int parent); void HeapPop(Hp* hp); HeapdataType HeapTop(Hp* hp); int HeapSize(Hp* hp); bool HeapEmpty(Hp* hp);4.1 辅助函数：向上调整和向下调整
堆的核心操作是插入和删除，它们依赖于两个关键调整算法：向上调整和向下调整。
4.1.1 向上调整（AdjustUp）
插入数据后如果堆的结构被破坏，那么就需要进行向上调整观察原堆的结构，如果插入之前是小堆,那么就将小的向上调整如果插入之前是大堆，那么将向上调整的代码中的>改为<。我们这里都是小堆.
void AdjustUp(HeapdataType* arr,int child) { 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; } } } 4.1.2 向下调整（AdjustDown）
删除堆顶元素时，通常先将堆顶与最后一个元素交换，然后删除最后一个元素（即原堆顶），再从新的堆顶开始向下调整：与左右孩子中较小（小堆）或较大（大堆）的交换，直到满足堆序或成为叶子。
void AdjustDown(HeapdataType* arr, int size, int parent) { //因为我们要找出左右孩子中较小的那一个进行交换 //我们先假设左孩子是较小的那一个 int child = 2 * parent + 1; while (child < size) { if (child + 1 < size && arr[child + 1] < arr[child]) { child++; } if (arr[child] < arr[parent]) { Swap(&arr[child], &arr[parent]); parent = child; child = 2 * parent + 1; } else { break; } } }4.2 接口实现
4.2.1 初始化与销毁
void HeapInit(Hp* hp) { assert(hp); hp->arr = NULL; hp->capacity = hp->size = 0; } void HeapDestroy(Hp* hp) { assert(hp); free(hp->arr); hp->arr = NULL; hp->size = hp->capacity = 0; }4.2.2 插入元素
void HeapPush(Hp* hp, HeapdataType x) { assert(hp); if (hp->size == hp->capacity)//如果空间满了，对数组进行扩容 { int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity; HeapdataType* newarr = (HeapdataType*)realloc (hp->arr, sizeof(HeapdataType) * newcapacity); if (newarr == NULL) { perror("realloc failed"); return; } hp->arr = newarr; hp->capacity = newcapacity; } hp->arr[hp->size++] = x; AdjustUp(hp->arr, hp->size - 1); }4.2.3 删除堆顶元素
void HeapPop(Hp* hp) { assert(hp); assert(hp->size>0);//确保其中至少有一个元素 //为了保证不同时改变左右子树的结构，我们将第一个元素与最后一个元素交换 Swap(&hp->arr[0], &hp->arr[hp->size - 1]); hp->size--; //交换之后，我们需要将第一个元素进行向下调整，保证堆结构的完整性 AdjustDown(hp->arr, hp->size, 0); }4.2.4 其他简单接口
HeapdataType HeapTop(Hp* hp) { assert(hp); assert(hp->size > 0); return hp->arr[0]; } int HeapSize(Hp* hp) { assert(hp); return hp->size; } bool HeapEmpty(Hp* hp) { assert(hp); return hp->size == 0; }4.2.5 建堆
给定一个数组，我们如何将它调整成一个堆？常用的方法是向下调整建堆：从最后一个非叶子结点开始，依次向前对每个结点执行向下调整。最后一个非叶子结点的下标为 (n-1-1)/2 = n/2 - 1。
for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(hp->_a, n, i); }五、堆排序
堆排序是利用堆这种数据结构进行排序的一种算法，其基本思想是：
- 建堆：将待排序序列构建成一个堆（升序建大堆，降序建小堆）。
- 排序：不断将堆顶元素与堆尾元素交换，交换后堆的大小减一，然后对新的堆顶执行向下调整，重复此过程直到堆为空。
以升序排序为例，我们需要建大堆（这样堆顶是最大值），然后每次将最大值交换到最后，并调整剩余元素为大堆，最终得到升序序列。
5.1 堆排序代码实现
void HeapSort(int* a, int n) { // 1. 建堆（升序建大堆） for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } // 2. 排序 int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); // 将堆顶（最大值）交换到最后 AdjustDown(a, end, 0); // 调整剩余的元素为大堆 end--; } }注意：上述代码中的 AdjustDown 需要根据堆的类型调整比较逻辑。若用于大堆，向下调整时应将父结点与较大的孩子交换。
5.2 堆排序的时间复杂度
- 建堆阶段：O(n)
- 排序阶段：每次交换后向下调整的时间复杂度为 O(log n)，共进行 n-1 次，因此排序阶段为 O(n log n)
- 总时间复杂度：O(n log n)
- 空间复杂度：O(1)（原地排序，不需要额外空间）
结语
树作为重要的非线性结构，为我们提供了分层组织数据的能力。而堆作为完全二叉树的典型应用，不仅实现了优先队列，还衍生出高效的堆排序算法。通过本文的学习，我们掌握了堆的核心操作（向上调整、向下调整）及其在插入、删除、建堆、排序中的具体实现。希望读者能够动手编写代码，深入理解堆的精髓，并在实际问题中灵活运用。
