企业官网建设流程全解析

把树和堆放在同一个标题里，其实不是偷懒，它们本来就是一对需要放在一起理解的搭档。我在准备数据结构期末考试、考研专业课和大厂算法面试的时候，都会把树和堆归成一类来复习。树给出了递归结构的骨架，堆则在这套骨架上实现了最简单的“取最值”操作。学完二叉树再回头看堆，你会有一种“原来一块连续数组也能装下一棵树”的豁然感。这篇不是教材原文的复述，而是我从刷题、做实验和背书过程中总结出来的一条学习路径，适合正在复习数据结构的人，也适合刚学完表、栈、队列，想往非线性结构进阶的初学者。

很多人觉得树难，难在递归；堆难，难在下标换算。但只要把“递归是系统帮我们压栈”和“堆是一棵住在数组里的完全二叉树”这两句话真正想透，大部分题目都能迎刃而解。下面我按自己的逻辑一步步展开，你可以跳到自己卡住的部分看。

1. 树和堆为什么必须放在同一轮复习

1.1 树解决“结构”问题，堆解决“效率”问题

数据结构的学习是有递进关系的。数组、链表、栈、队列都是线性结构，元素之间是一条链的关系。树是第一个真正意义上的非线性结构，它表达的是分支、层级、嵌套这些更接近真实世界的关系。而堆是树的一种特殊化：它首先是一棵完全二叉树，然后额外规定父节点和子节点之间的值必须满足某种次序。

你可以这样理解：树负责把“结构”搭出来，堆负责在“结构”上给出最快取到最值的方法。没有树，堆就像是空中楼阁；没有堆，二叉树就只是一个适合递归遍历的容器，缺少了那种“每次都能直接抓到最大/最小元素”的爽快感。把两者放在一起学，底层逻辑是同一个，记忆负担反而更小。

1.2 完全二叉树是两者之间的桥

堆之所以能像数组一样用一块连续内存存下来，核心前提就是堆在逻辑上是完全二叉树。完全二叉树的定义是：除了最后一层，其他层节点数都达到最大值，且最后一层的节点都集中在左侧。这听起来有点绕，但形象一点说，它是一棵“没有空洞”的树，从上到下、从左到右按层序编号时，编号是连续不断的。

正因为没有空洞，才能把这个编号直接映射成数组下标。比如数组[10, 7, 8, 5, 6, 4]，按层序遍历来看：

• 10是根，在数组下标 0；
• 7是左孩子，8是右孩子；
• 5、6是7的孩子，4是8的左孩子。

下标关系就是：下标i的节点，左孩子是2*i+1，右孩子是2*i+2，父节点是(i-1)/2。很多初学堆的人先把这组公式背下来，却不明白它怎么来的；其实它就是“完全二叉树按层序铺进数组”的自然结果。

1.3 正确的复习顺序能让你少走一半弯路

我见过很多人一上来就背堆排序，结果背完就忘。更合理的学习顺序是：先学二叉树的遍历，因为堆的上浮下沉本质上就是沿着树高走；再学用数组模拟完全二叉树，理解下标换算；接着学堆的插入、删除、建堆；最后再看堆排序、优先队列和 TopK、中位数这类经典问题。

这个顺序最大的好处是，你不会把堆当成一个孤立的数据结构。后面刷题时你会反复用到“堆只能高效取最值，不能高效搜索元素”“堆不是二叉搜索树”这些边界认知，而这些认知只有在你先看清树和堆的关系后才会自然长出来。

2. 树的根基：从链表到二叉树，再到多叉树的演进

2.1 树本来就是从链表长出来的

很多教材直接甩出“树是非线性结构”的定义，导致新手莫名紧张。但你把树节点和链表节点摆在一起看，就会发现它们长得几乎一样。链表节点里有一个指向下一个节点的指针：

struct ListNode { int val; struct ListNode *next; };

二叉树节点不过是从“一个后继”变成了“两个后继”：

struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; };

所以学树的第一步，不是背定义，而是接受一个事实：树就是链表的“多叉化”。链表的每个节点最多只有一个后继，树的每个节点可以有多个后继。如果你愿意，链表都可以看成每个节点只有一个孩子的“退化树”。这个概念打通之后，树对你来说就不那么神秘了。

2.2 二叉树为什么叫“二叉”

因为每个节点最多分出两个分支，所以叫二叉。树的通用定义是“一个有 n 个节点的有限集合，其中有一个根节点，其余节点可以分成若干个互不相交的子树”。二叉树则规定每个节点最多只有左右两棵子树，且左右顺序不能颠倒。

这个“左”和“右”的顺序非常关键，因为它让很多操作变得有迹可循。比如中序遍历二叉搜索树能得到一个递增序列，如果左右孩子没有固定语义，这个性质根本不存在。工程和算法里最常见的也是二叉树，因为两分支天然对应二选一的决策，搜索、比较、合并都能建立在二叉分支上。

2.3 递归遍历就是系统在帮你压栈

二叉树的深度优先遍历有前序、中序、后序三种，区分方法很简单：看根节点什么时候被访问。前序是“根左右”，中序是“左根右”，后序是“左右根”。递归写法基本是模板：

void preorder(struct TreeNode *root) { if (root == NULL) return; printf("%d ", root->val); // 前序访问根 preorder(root->left); preorder(root->right); }

这段代码看起来简单，但它背后藏着一个重要的原理：递归并不是什么黑魔法，而是系统帮你维护了一个调用栈。每次函数调用自己时，当前状态都会被压进栈里，等子树处理完再弹出来。所以面试题“用迭代实现中序遍历”，本质就是把这个系统栈手动写出来。

比如中序遍历，迭代思路是：从根开始一路往左走，把路上的节点全部压栈；走到空节点后弹栈访问，再转到右孩子继续这个过程。你只要在一棵小树上手动模拟一遍压栈、弹栈，就再也不会忘。画一棵只有三个节点的树，1是根，2是左孩子，3是右孩子，中序遍历结果是2 1 3，这一个小例子足以帮你理解整条链路。

2.4 层序遍历、树的直径这两个知识点别跳过

层序遍历对应广度优先搜索 BFS，用队列实现。伪代码很简单：先把根入队，然后循环弹出队首，访问它，并把它的左右孩子入队。很多和“最短路径”有关的树问题都要用到它，例如求二叉树的最小深度。

树的直径是另一个高频题。这里的“直径”不是指圆形，而是指一棵树中任意两个节点之间最长路径的边数。经典做法是：选任意一个节点出发，DFS 找到离它最远的节点 A；再从 A 出发，DFS 找到离 A 最远的节点 B，A 到 B 的路径就是直径。对于二叉树，更常用的递归写法是求每个节点的左右子树高度，把“左高度 + 右高度”作为经过当前节点的路径长度，在递归过程中取最大值。你可能会看到类似这样的 C++ 代码：

int diameter = 0; int dfs(TreeNode* root) { if (root == nullptr) return 0; int left = dfs(root->left); int right = dfs(root->right); diameter = max(diameter, left + right); return max(left, right) + 1; }

这里dfs返回的是当前节点的高度，同时顺手更新全局diameter。理解这段代码后，你会发现它和最大深度、平衡二叉树这些题都是同一个套路：递归返回子树信息，在根节点汇总。这套思想后面还会反复出现。

3. 堆的本质：完全二叉树在数组里的生存方式

3.1 堆的两条规矩，多少根节点说了算

堆有两种：大顶堆和小顶堆。大顶堆要求每个父节点都大于等于它的子节点，所以堆顶是整个堆的最大值；小顶堆相反，每个父节点都小于等于它的子节点，堆顶是最小值。

记住一个容易混淆的点：堆只约束父子和兄弟关系吗？不，它只约束父子关系，兄弟之间谁大谁小完全不管。因此堆不是一个适合“搜索某个元素”的结构，它只适合“马上拿到堆顶的最值”。很多人把堆和二叉搜索树混在一起，二叉搜索树要求左子树所有节点小于根、右子树所有节点大于根，堆完全没有这个约束。如果你面试时被问到“给一个堆，查找某个值是不是在里面”，正确回答是：堆支持不了 O(log n) 的查找，只能遍历，这是堆的位置决定的。

3.2 为什么下标 i 的孩子是 2i+1 和 2i+2

前面说过，完全二叉树可以按层序连续铺进数组。为了真正理解下标换算，建议自己数一遍。假设数组下标从 0 开始，根是 0。根的两个孩子是 1 和 2；节点 1 的两个孩子是 3 和 4；节点 2 的两个孩子是 5 和 6。发现规律了吗：对于下标i，左孩子在2i+1，右孩子在2i+2，父节点在(i-1)/2。

这个公式不需要用一句话总结成“左孩子是奇数，右孩子是偶数”，你只要多画几层完全二叉树就会形成直觉。另一个常用结论是：节点个数为n时，最后一个非叶节点下标是n/2 - 1。因为最后一个节点的下标是n-1，如果它是右孩子，父节点就是(n-2)/2，如果它是左孩子，父节点是(n-1)/2，整数除法之后结果都是n/2-1。这个结论在建堆时是起点，必须记准。

3.3 上浮和下沉：插入和删除为什么是 O(log n)

堆的插入操作，第一步是把新元素放到数组尾部，这样就保证了“完全二叉树”的结构完整性。但新元素可能会破坏堆序性，比如往大顶堆末尾放了一个非常大的数，它的父节点反而比它小。这时候需要“上浮”：把它和父节点比较，如果违反父大于子的规则就交换，然后继续向上比较，直到满足堆序为止。

删除堆顶操作正好相反。第一步把数组最后一个元素覆盖到堆顶，然后堆大小减一。此时结构依然是一棵完全二叉树，但堆顶可能不是最大/最小值，需要“下沉”：从堆顶开始，把当前节点和它较大的孩子比较（大顶堆就选较大的孩子，小顶堆就选较小的孩子），如果不符合堆序就交换，然后继续向下调整。

上浮和下沉每次最多沿着树高走，完全二叉树的高度是 O(log n)，所以插入和删除堆顶都是 O(log n)。这个结论是堆能成为“高效优先队列”的底气。

3.4 建堆为什么是 O(n)，而不是 O(n log n)

第一次看到“建堆只需 O(n)”时，很多人觉得反直觉：插入 n 个元素不是要 O(n log n) 吗？没错，如果你一个一个调用插入函数，代价确实是 O(n log n)。但建堆标准做法不是这样，而是先把所有元素直接放进数组，然后从最后一个非叶节点开始，自底向上逐个做下沉调整。

为什么这样更快？因为越靠近底层的节点，虽然数量多，但它们下沉的高度短；越靠近根部的节点，虽然下沉高度大，但数量少。可以做一个粗略的估算：设节点数为 n，叶子层约 n/2 个节点不需要调整；倒数第二层约 n/4 个节点最多下沉 1 次；倒数第三层约 n/8 个节点最多下沉 2 次……总操作次数大约是：

0 * n/2 + 1 * n/4 + 2 * n/8 + 3 * n/16 + ...

这个级数是收敛的，最终结果是一个常数乘以 n，所以总复杂度是 O(n)。面试时只要能说出“大多数节点位于底层，下沉距离短，总调整次数是常数倍 n”这个关键点，基本就能过关。

3.5 C 语言手写一个大顶堆

实验课或代码面试中，偶尔会遇到不允许用语言内置优先队列的情况。这时候手写一个堆是基本功。下面是一段 C 语言的最小实现，逻辑是：push把新值插到尾部并上浮，pop把最后一个元素覆盖到堆顶并下沉。

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; } void push(int heap[], int *size, int val) { heap[(*size)++] = val; int i = *size - 1; while (i > 0 && heap[(i - 1) / 2] < heap[i]) { swap(&heap[(i - 1) / 2], &heap[i]); i = (i - 1) / 2; } } void pop(int heap[], int *size) { if (*size <= 0) return; heap[0] = heap[--(*size)]; int i = 0; while (2 * i + 1 < *size) { int child = 2 * i + 1; if (child + 1 < *size && heap[child + 1] > heap[child]) { child = child + 1; } if (heap[i] >= heap[child]) break; swap(&heap[i], &heap[child]); i = child; } }

写这段代码时最容易出错的是pop的下沉循环：每次要先判断左孩子存在，再判断右孩子是否存在以及是否比左孩子大。大顶堆选较大孩子，小顶堆则要改成选较小孩子。写完建议随机生成一组数据，反复 push 和 pop，最后看 pop 出来是否呈递减序列，能验证你的堆到底对不对。

4. 堆的实战战场：TopK、中位数与优先队列

4.1 数据流中的中位数：两个堆的经典配合

我最早看到“方法3：两个堆”这个热搜词时，就知道大家多半是在查数据流中位数这道题。题目要求不断插入数字，随时能取当前所有数的中位数。如果每次都排序，复杂度太高；如果只用一个堆，又没法同时知道中间位置的两个值。

正确答案是同时维护两个堆：一个大顶堆left保存较小的一半，一个小顶堆right保存较大的一半。关键来了：大顶堆的堆顶是“较小一半里的最大值”，小顶堆的堆顶是“较大一半里的最小值”，这两个堆顶正好夹在中位数两侧。

插入一个数x时，如果left为空或者x <= left.top()，就放进left，否则放进right。然后做平衡调整，保持left的数量比right多 0 或 1。具体做法是：如果left.size() > right.size() + 1，就把left的堆顶移到right；如果right.size() > left.size()，就把right的堆顶移到left。这样取中位数时，总数是奇数就返回left.top()，总数是偶数就返回(left.top() + right.top()) / 2.0。

插入是 O(log n)，取中位数是 O(1)。这个设计最漂亮的地方在于“大顶堆放小半、小顶堆放大半”，两个结构互相补位，每次调整都只在堆顶之间移动，复杂度不会退化。面试时画一个数轴，把两个堆画成上下两层，一下子就能讲清楚。

4.2 TopK 问题：为什么求最大 K 个要维护小顶堆

另一个高频题是求一个数组里最大的 K 个数。最朴素的办法是排序后取前 K 个，O(n log n)。但更优的思路是用一个大小为 K 的小顶堆。遍历数组时，如果堆还没满，就插入；如果堆满了，且新元素比堆顶大，就替换堆顶并下沉。这样堆里始终维护着“已经遇到的最大 K 个”，其中堆顶是这 K 个里最小的那个，也就是当前第 K 大的门槛。

很多人第一次接触会困惑：求最大 K 个，为什么用“小顶堆”？因为小顶堆的堆顶是候选者中最弱的那个，来了更强的候选者，直接把最弱的踢出去。如果是大顶堆，堆顶是候选者里最强的，淘汰谁？不知道。所以正确的工具是“把弱者放在门口方便淘汰”的小顶堆。

同理，求第 K 大的元素，也可以在维护完大小为 K 的小顶堆后，直接返回堆顶。这个题的变形很多，但核心始终是“固定容量的小顶堆 + 只有比堆顶大才替换”。

4.3 优先队列在算法题里的几个高频场景

优先队列本质上就是堆，很多算法题不会直接说“请用堆”，但只要你识别出“每次都要从当前候选中取最值”这个需求，就知道该上优先队列了。

合并 K 个有序链表就是一个标准例子。把每个链表的头节点放进小顶堆，每次弹出最小值，接入结果链表，然后把这个节点的 next 入堆。因为每个链表本身有序，弹出的一定是当前所有链表头里的最小节点，整个过程是 O(N log K)，其中 N 是总节点数。

Dijkstra 最短路算法也依赖优先队列。每次从未确定最短路的点中，选一个距离最小的点扩展；如果每次遍历找最小，复杂度会很高。用堆维护候选距离，就能把选点这一步降到 O(log n)。

任务调度也类似，CPU 从就绪队列里选优先级最高的任务，操作系统里的优先队列就是堆的一种应用。所有场景的共同特征是：“插入一个候选”和“取走当前最优候选”都很频繁，堆恰好同时支持这两个操作。

4.4 堆排序：不稳定但内存极省

堆排序是堆的另一个直接应用。思路是：先建一个大顶堆，然后把堆顶和最后一个元素交换，堆大小减一，再对新的堆顶进行下沉调整。重复这个过程，数组尾部就会逐渐变成有序的递减部分，最终得到升序结果。

复杂度是稳定的 O(n log n)，空间 O(1)，因为整个排序可以在原数组上完成，不需要额外数组。但堆排序在工程中通常排不过快速排序，原因是它访问数组的模式是跳跃的，对 CPU 缓存不友好，实际比较次数也偏多。另外，堆排序不稳定，相同关键字的元素相对顺序可能会变。如果你被问到“为什么很多语言默认排序用快排而不是堆排”，可以从这两个角度回答。

5. 那些名字里带“树”的亲戚：哈夫曼、Trie、红黑树、B+树

5.1 哈夫曼树：变长编码的灵魂

哈夫曼树和堆的关系非常微妙。哈夫曼树的构造目标，是让带权路径长度 WPL 最小，也就是让频率高的叶子离根近、频率低的叶子离根远。构造方法是贪心：每次从当前集合中选出权值最小的两棵树合并成新树，新树权值为两棵子树权值之和，然后放回集合继续合并。

这里“每次选两个最小的”听起来很耳熟，对吧？如果用手工模拟，可以在纸上找最小；如果写程序，最方便的实现就是用一个小顶堆。把所有权值入堆，每次弹出两个最小的，合并后再入堆。所以哈夫曼树不仅适合放在“树”章节里学，也适合在学完堆之后回头看，一举两得。

哈夫曼编码则通过让每个叶子对应一个码字，编码之间满足“没有一个编码是另一个编码的前缀”，从而能无歧义解码。这个知识点在考研和期末考中都很常见，关键是要自己动手构造一棵哈夫曼树，而不是只背定义。

5.2 字典树 Trie：空间换时间的典型

字典树也叫 Trie 树，是处理字符串前缀匹配的神器。它的结构是：根节点不存字符，每条从根到某个节点的路径代表一个字符串前缀，路径上的字符按顺序拼接起来就是一个前缀。每个节点有一个标记表示“是否存在以此为结尾的单词”。

查找一个长度为 m 的字符串，只需要沿着树走 m 步，时间复杂度 O(m)，和字典里总共存了多少单词无关。这和二叉搜索树的 O(log n) 完全不同，因为 Trie 的搜索深度取决于字符串长度，而不是数据规模。实现时，26 个字母的节点可以用大小为 26 的孩子数组，缺点是比较耗内存；也可以改用哈希表保存孩子，适合字符集很大的场景。

在 C 语言里写 Trie 时，节点定义大概长这样：

struct TrieNode { struct TrieNode *children[26]; int isEnd; };

每次插入前先分配节点，插入时逐字符查孩子、没有就创建。搜索时也是逐字符走，如果中途遇到空指针，说明前缀不存在。自动补全、拼写检查、敏感词匹配这些功能背后都能看到它的影子。

5.3 红黑树、B+树：工程界的两位大佬

红黑树是一种自平衡二叉搜索树，它通过节点颜色和几条旋转规则，保证树的高度在 O(log n) 量级，从而避免二叉搜索树在有序输入下退化成链表。Java 的 TreeMap、C++ 的 map，底层都用红黑树。学习红黑树时，不要一开始死记旋转细节，先理解它解决的问题：普通二叉搜索树在极端情况下会变成一条链，插入、查找都退化成 O(n)。旋转和颜色调整，都是为了在插入、删除后继续保持平衡。

B+树则多出现在数据库和文件系统索引中。它是一棵多路搜索树，每个节点可以有多个孩子，因此同样规模的数据，B+树的树高比二叉树低很多，能减少磁盘 IO 次数。它的一个显著特点是所有关键字都出现在叶子节点，并且叶子节点通过指针串成链表，范围查询非常高效。如果你不是研究数据库内核，那么能说出“B+树减少磁盘 IO、方便范围查询”就是及格水平。

5.4 别把“Linux 设备树”这些同名概念混进来

搜索“设备树”时你会看到很多 Linux 嵌入式的资料，但这和数据结构的树完全是两码事。Linux 设备树（Device Tree）是一种描述硬件资源的组织方式，用来告诉内核“这块板子上有哪些设备、中断号是多少、寄存器地址在哪”，虽然它也有树状层次，但不涉及左右子树、搜索、堆序这些算法概念。

类似的还有故障树（FTA）、行为树（Behavior Tree），它们分别是可靠性工程和游戏 AI 领域的建模工具。复习数据结构时，如果被这些词干扰，很容易怀疑自己是不是漏了什么重点。我的建议是：看到“树”字先判断语境，如果是硬件描述、故障分析、游戏行为设计，那就不是数据结构的树，不用往二叉树上面套。

6. 面试和期末复习时的树与堆高频套路

6.1 递归模板：先想清楚这个函数返回什么

树题九成以上都能用递归解决。写递归前，先问自己三件事：这个函数对一棵子树返回什么？当前节点要做什么事？终止条件是什么？以最大深度为例：

int maxDepth(TreeNode* root) { if (root == nullptr) return 0; int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return max(leftDepth, rightDepth) + 1; }

这个函数返回的是“当前子树的高度”。当前节点做的事，就是把左右子树的高度取最大，再加 1。空节点返回 0 是终止条件。几乎所有树的递归题都可以套这个框架。判断平衡二叉树的经典写法也类似：递归返回 -1 表示不平衡，否则返回子树高度；一旦左右高度差超过 1，就返回 -1。写多了你会发现，递归不是靠记代码，而是靠想清楚“子树传上来什么信息”。

6.2 刷题时用内置优先队列，复习时手写一遍堆

笔试和日常刷题，直接用语言内置的优先队列就行了，不要自己造轮子，省时间也减少 bug。但复习数据结构，尤其是实验课或裸写代码的考试，手写堆是躲不过去的。我的建议是：先手写一个最小堆和一个最大堆，然后做三组测试。

第一组，随机插入 1000 个数，每次插入后从堆顶到数组末尾检查是否满足堆序；第二组，连续 pop，看弹出的序列是否按从小到大（小顶堆）或从大到小（大顶堆）排列；第三组，和语言内置优先队列的结果对拍，随机操作几万次，两边输出一致就说明实现没问题。这三组测试能把你手写堆里那些下标、比较方向的隐患全部揪出来。

6.3 几个容易踩的坑

这里整理几个我见过很多人踩过的坑：

还有一个认知上的坑：堆删除一个“指定元素”不是 O(log n)，因为堆不支持按值搜索。如果想删除任意元素，需要额外维护索引或位置数组。面试中如果被问到优先队列能不能 O(log n) 删除某个任意元素，这是一个需要重点说明的边界。

6.4 冲刺刷题建议清单

如果你时间紧，比如离面试或期末考试只剩三天，按下面这个清单刷，每类题覆盖一个核心套路：

• 二叉树遍历：前序、中序、后序、层序，至少要能手写递归和迭代各一遍。
• 经典递归：最大深度、平衡二叉树、二叉树直径、最近公共祖先。
• 构造与序列化：从前序和中序遍历重建二叉树、二叉树的序列化与反序列化。
• 二叉搜索树：验证二叉搜索树、二叉搜索树中第 K 小元素。
• 堆专项：数组中的第 K 大元素、数据流中的中位数、合并 K 个有序链表、前 K 个高频元素。

刷的时候要总结的不仅是怎么做，而是“递归函数返回什么”“堆在维护什么候选集合”这两个元问题。比如第 K 大元素：堆维护的是“目前遇到的最大 K 个候选”；中位数：两个堆维护的是“较小一半”和“较大一半”的分界线。一旦能从这种抽象层面理解题目，换个外壳你也能认出来。

6.5 最后分享一个我自己的记忆方法

学树和堆，别急着追求“把题做对”，先做到“能给别人讲清楚”。我复习时有个习惯：对着空气把原理讲一遍，比如“为什么建堆是 O(n)”“为什么 TopK 用小顶堆”“为什么中位数要用两个堆”。如果能用大白话讲明白，笔试时基本不会卡壳。反过来，如果只是记住了代码而没有想透，面试官随便追问一句就能把你打回原形。

你可以把堆和二叉搜索树放在一起对比：堆负责“找最值”，二叉搜索树负责“找目标值”，各管一头。结构上它们都是树，但语义完全不同。想明白这一点，整个数据结构的线性结构、树形结构、搜索结构、排序结构就能串成一张真正的网，而不是一堆零散的知识点。