【数据结构】二叉树、堆

文章目录

二叉树的概念及结构
- 定义
- 特殊的二叉树
- 核心性质
- 存储方式
二叉树的链式存储
- 前序遍历
- 中序遍历
- 后序遍历
- 层序遍历
二叉树的顺序存储
- 父子关系的推导
- 堆（heap）
- - 堆的概念
  - 向上调整算法和向下调整算法
  - - 向上调整算法
    - 向下调整算法
  - 堆的创建
  - 堆的插入
  - 堆的删除
- 堆的应用
- - 堆排序
  - TOP-K 问题

二叉树的概念及结构

定义

二叉树是每个节点最多有两个子节点的树结构，分别称为左子节点和右子节点。子树区分左右顺序，即使仅有一个子节点也需明确方向。二叉树可以为空（无节点）。

特殊的二叉树

满二叉树：所有非叶子节点均有左右子节点，且所有叶子在同一层。
完全二叉树：除最后一层外，其他层节点全满，最后一层从左到右连续填充。
平衡二叉树：任意节点左右子树高度差不超过1（如AVL树）。
二叉搜索树（BST）：左子树节点均小于根，右子树节点均大于根。

核心性质

节点关系：
- 每个节点最多有两个子节点
- 若树的高度为 h，则最大节点数为 2^h - 1（即满二叉树的情况）
层次与深度：
- 根节点位于第一层（或第零层，依定义不同）
- 根节点的深度为从根节点到该节点的路径长度

存储方式

链式存储：
- 节点包含数据、左指针和右指针。
- 灵活，适合动态增删。
顺序存储（数组）：
- 适用于完全二叉树，父节点下标 i 的左子节点为 2i，右子节点为 2i + 1
- 非完全二叉树可能浪费存储空间。

二叉树的链式存储

根据定义，我们很容易就知道二叉树节点分为一个数据域和两个分别指向左右子树的指针域，于是就有：

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}TreeNode;

对于链式结构的二叉树，我们主要得掌握它的三种深度优先遍历和一种层序遍历的方式
对于三种深度优先遍历，它这个前、中、后指的是根节点的前、中、后。

前序遍历(Preorder Traversal 亦称先序遍历)——访问根节点的操作发生在遍历其左右子树之前。
中序遍历(Inorder Traversal)——访问根节点的操作发生在遍历其左右子树之中（间）。
后序遍历(Postorder Traversal)——访问根节点的操作发生在遍历其左右子树之后。

前序遍历

因为是递归调用，所以代码极其简单

void PrevOrder(TreeNode* root)
{if (root == NULL){printf("N\n");return;}printf("%d ", root->data); // 访问根节点PrevOrder(root->left);	   // 访问左子树PrevOrder(root->right);	   // 访问右子树
}

中序遍历

void InOrder(TreeNode* root)
{if (root == NULL){printf("N\n");return;}InOrder(root->left);		// 访问左子树printf("%d ", root->data);	// 访问根节点InOrder(root->right);		// 访问右子树
}

后序遍历

void PostOrder(TreeNode* root)
{if (root == NULL){printf("N\n");return;}PostOrder(root->left);		// 访问左子树PostOrder(root->right);		// 访问右子树printf("%d ", root->data);	// 访问根节点
}

从代码中，我们不难看出，这三种遍历方式仅是访问根节点的时机不同。

层序遍历

对于层序遍历，也就是字面意思，我们需要按层逐层访问节点。
那么如何做到呢？
这就得使用一个队列去保存树中的节点。
首先让根节点入队列，当队列不为空的时候，取出队列中队头节点，访问该节点的元素。然后判断该节点是否存在左右节点，存在则入队列。重复这个过程直到队列为空

vector<int> breadthFirstTraversal(TreeNode* root) {vector<int> result;		   // 用于存放层序遍历的结果if (!root) return result;  // 处理空树情况queue<TreeNode*> q;		   // 创建队列q.push(root);			   // 根节点入队列while (!q.empty()) {	   // 直到队列为空TreeNode* current = q.front();	// 取队头节点q.pop();						result.push_back(current->val);	// 将该节点的元素放入数组中if (current->left) q.push(current->left);	// 存在左节点就入队列if (current->right) q.push(current->right);	// 存在右节点就入队列}return result;
}

注释写的已经很清楚了，应该能看懂吧。
考虑到可能有些同学刚接触二叉树，可能看不懂这代码。没事，先有个印象就行了，等到后面对于数据结构的理解加深自然就理解了。

二叉树的顺序存储

普通的二叉树并不适合使用顺序存储，因为这可能会导致大量的空间浪费。在使用顺序存储时，一定是完全二叉树。
父子下标关系本质上是完全二叉树层序遍历在数组中的直接映射：

左子下标 = 父下标 x 2（根从1开始）或父下标 x 2 + 1（根从0开始）
右子下标 = 左子下标 + 1

父子关系的推导

因为数组是从 0 下标开始的，所以这里就以根节点从 0 开始推导

完全二叉树的层次遍历特性
完全二叉树的节点按层次遍历顺序连续存储在数组中，且满足以下性质：

第 k 层的节点数：2^k
第 k 层的起始下标：2^k - 1
第 k 层的第 m 个节点的下标：2^k - 1 + m

父子节点位置关系

父节点在第 k 层第 m 个位置：
- 下标：i = 2^k - 1 + m
左子节点在第 k+1 层的第 2m 个位置：
- 下标：left_child = 2^k+1 - 1 + 2m
- 代入 $i=2^k-1+m$ ，化简得：
  left_child = 2i + 1
右子节点为左子节点下标 + 1
- right_child = 2i + 2

推导就到这里，数学好点的同学可以使用数学归纳法来证明一下。markdown的语法不太好写，这里就不再证明了

堆（heap）

说起二叉树的顺序存储就不得不提堆了。如果你存的数据都是些非常杂乱的，且你对它并没有做出些什么修正，那你用二叉树干嘛？搞得这么花里胡哨，不如直接使用数组。而堆就不一样了。

堆的概念

堆（Heap）是一种特殊的完全二叉树，具有以下核心性质，可分为 最大堆 和 最小堆 两种类型：

性质：

结构性：完全二叉树

堆在逻辑上是完全二叉树，所有层（除最后一层）节点全满，最后一层节点从左到右连续填充。
顺序存储实现：通常用数组存储，利用下标关系快速定位父子节点：

堆序性：节点值的有序性

最大堆（Max-Heap）：
- 每个节点的值 ≥ 其子节点的值。
- 根节点是树中的最大值。
最小堆（Min-Heap）：
- 每个节点的值 ≤ 其子节点的值。
- 根节点是树中的最小值。

核心操作与性质维护
堆通过以下操作维护其性质：
1. 插入（Insert）：
  - 新元素插入末尾，通过上浮（Percolate Up）调整位置。
  - 时间复杂度：O(logN)
2. 删除堆顶（Extract-Max/Min）：
  - 移除堆顶元素，将末尾元素移至堆顶，通过下沉（Percolate Down）调整位置。
  - 时间复杂度：O(logN)

向上调整算法和向下调整算法

在建堆之前，我们需要理解向上调整和向下调整算法。
以小堆为例

向上调整算法

向上调整算法，听名字就知道是向上比较，那么就是孩子节点（我们选择的节点）与父节点的比较。
使用场景：插入新元素后，将其从堆尾逐步向上调整到合适位置

void AdjustUp(HDataType* a, int child)
{int parent = (child - 1) / 2;	// 通过下标关系计算出父节点下标while (child > 0)				// 当子节点下标大于 0 时就继续调整{if (a[child] < a[parent])	// 这里以小堆为例，所以子小于父的时候交换两节点数据，将小的元素往上调{Swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else{break; // 到达合适位置的时候跳出循环}}
}

向下调整算法

向下调整需要一直调整到叶子节点

void AdjustDown(HDataType* a, int n, int parent)
{// 假设左孩子小int child = parent * 2 + 1;while (child < n) // child >= n说明孩子不存在，调整到叶子了{// 找出小的那个孩子，确保child指向的是小的孩子节点if (child + 1 < n && a[child + 1] < a[child]){++child;}if (a[child] < a[parent])	// 孩子节点比父节点小就进行交换{Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;	// 到合适的位置跳出循环}}
}

堆的创建

建堆有两种方法：

一种是不断插入新节点（新节点肯定是叶子节点啦），插入一个节点就对其进行一次向上调整，直到建好堆。
还有一种是将已知的数组视为一个堆，从最后一个非叶子节点开始进行向下调整，直到调整到根节点。

那么这两种建堆方式推荐使用哪种呢？
推荐使用向下调整的方式建堆！

为什么呢？因为更快。
这里很明确的告诉你向上调整建堆的时间复杂度是 O(Nlog N)，而向下调整建堆的时间复杂度是 O(N)。
具体的证明这里就不写了，有兴趣的同学可以自己去推导一下，这里只说明个大概。

向上调整建堆，越深的节点，它要调整的次数越多（根节点到它的距离），并且越深的节点数量越多（在满二叉树的情况下）。
而向下调整建堆，越深的节点，它要调整的次数越少（它到叶子节点的距离），并且越深的节点数量越多。
那么在二者数量相同的情况下，向上调整：
（一层里）数量多的节点要调整的次数多，（一层里）数量少的节点调整的次数少。
向下调整：
（一层里）数量多的节点要调整的次数少，（一层里）数量少的节点调整的次数多。
很明显向下调整的次数更少，并且向下调整本身要调整的节点数量就小于向上调整要调整的节点数量，很明显向下调整建堆更快。

堆的插入

插入位置是在叶子节点，直接将其向上调整

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

堆的删除

因为堆删除只能删除堆顶元素。
将堆顶元素和堆尾元素交换，删除掉原先的堆顶元素，再将新的堆顶元素向下调整即可。
解释：
以小堆为例，原先堆顶元素是整个堆中最小的，而堆尾元素肯定是大于原先的堆顶的，且会大于中间层的几个元素，将其放到堆顶，而向下调整又是将父节点的两个子节点中更小的那个调整上去，自然就能够保证堆顶为新的最小元素。

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

堆的应用

堆排序

很明显，是将数组排序，那么只要对需要排序的数组进行向下调整建堆，分为两个步骤：

建堆
- 升序：建大堆
- 降序：建小堆
利用堆删除的思想来进行排序

这两个步骤都是使用了向下调整算法，所以其实理解了向下调整算法，那么堆排序也挺简单的。

TOP-K 问题

找出 n 个元素中，前 K 大的元素。
直接建堆再取 K 次堆顶即可。
当然，如果 n 的值非常非常大，也可以维护一个 K 大小的堆，对整个数据遍历一遍，最后剩下来的 K 个数据便是我们所需要的答案。

我记得前几年的蓝桥杯省赛中 c++ b、c组中就有几题需要用到这个，就自己实现一下 node 节点，再不断地对堆顶进行操作，出堆，入堆，有兴趣的话也可以自己去找来看看。