企业官网建设流程全解析

数据结构这门课，不少人学到二叉树就开始掉队了。指针、递归、层序、前中后序，乍一看全是新概念，其实核心就那么几个点。这篇博客我打算用 C 语言把“树 -> 二叉树 -> 堆”这条线完整串一遍，从基本概念讲到代码实现，再讲到堆排序。无论你是正在准备期末考试，还是自学补基础，只要跟着思路走一遍，自己动手把代码敲出来，二叉树这关就算彻底过了。

1. 从树开始：先把这些术语一次性讲透

1.1 树到底是个什么东西

树是一种非线性的数据结构。你之前接触的数组、链表、栈、队列，都是线性结构，数据是一个挨着一个排队的。树不一样，它有一个根节点，然后向下分叉，每个节点可以连接多个子节点，就像文件夹套文件夹一样。

比如你的电脑目录：

C盘 ├── 用户 │ └── 下载 ├── Program Files └── Windows

这就是一棵典型的树。最顶层的 “C盘” 是根节点，“用户”“Program Files”“Windows” 是它的孩子，它们之间不是简单的先后关系，而是层次关系、父子关系。

树的结构在现实中到处都是：公司的组织架构、网页的 DOM 树、编译器的语法分析树、路由器的路由表……所以学树不只是为了考试，它几乎是所有复杂系统的底层骨架。

1.2 树的术语表：建议直接背诵

学树的第一道门槛是术语，一共就那么几个，但考试和面试都爱考，我给你整理成一张表：

这里最容易搞混的是深度和高度。简单记：深度是从上往下数（根到节点），高度是从下往上数（节点到叶子）。不同教材对根在第 0 层还是第 1 层有分歧，你自己做题时先看题目约定，代码里我习惯用“空树高度 -1，根节点高度 0”的算法，后面写递归代码时会体现。

1.3 为什么偏偏是二叉树

树可以有多个分叉，但数据结构里研究得最多的是二叉树。原因很现实：

• 二叉树每个节点最多两个子节点，存储结构简单，左右孩子用两个指针就能搞定；
• 任何多叉树都能通过“左孩子右兄弟”的方式转换成二叉树，研究二叉树等于研究了一般树；
• 二叉树上的算法（遍历、查找、插入）逻辑最清晰，是后续红黑树、B 树、堆的基础。

所以别急着去纠结三叉树四叉树，先把二叉树的底子打牢。

2. 二叉树的形态、性质与存储选型

2.1 满二叉树、完全二叉树、斜树：别再搞混

二叉树里有三个高频概念，很多新手栽在这里。

满二叉树：每一层都是满的。深度为 k 的满二叉树一共有 2^k - 1 个节点，节点数严格按照指数增长。比如深度 3 的满二叉树，总共 7 个节点，第 3 层有 4 个叶子。

完全二叉树：除了最后一层，上面全是满的；最后一层的节点要从左到右连续排列，不能有空洞。满二叉树一定是完全二叉树，但完全二叉树不一定是满的。判断方法很简单：给每个节点从 1 开始编号，看编号是否和满二叉树完全一致，中途不能断开。

斜树：所有节点都偏向一边，比如只有左孩子或者只有右孩子，这种树其实退化成了链表。斜树在存储上会造成很大的空间浪费，在查找效率上也没有优势，所以实际工作中很少直接用，但它经常被拿来测试算法边界情况。

2.2 二叉树的五个重要性质：会推比会背强

背性质没什么意义，但下面这几个性质做题时会反复用到，我给你推一遍：

1. 第 i 层最多有 2^(i-1) 个节点。这个看等比数列就知道，第一层 1 个，第二层 2 个，第三层 4 个。

2. 深度为 k 的二叉树最多有 2^k - 1 个节点。等比数列求和，1 + 2 + 4 + ... + 2^(k-1) = 2^k - 1。

3. n0 = n2 + 1。叶子节点数 = 度为 2 的节点数 + 1。这个性质最常考，证明思路是：总边数 = 节点数 - 1，同时总边数又等于 0n0 + 1n1 + 2*n2，联立可得。做题时碰到“度为 0 和度为 2 的关系”，直接秒答。

4. 具有 n 个节点的完全二叉树深度为 floor(log2 n) + 1。因为完全二叉树节点数 n 满足 2^(k-1) - 1 < n ≤ 2^k - 1，取对数即可。

5. 对完全二叉树按层序编号，节点 i 的左孩子是 2i，右孩子是 2i+1，父节点是 floor(i/2)。这个性质是堆和完全二叉树数组存储的根基，后面讲堆的时候你会再遇到它，只是编号从 1 还是从 0 开始会有所不同。

2.3 顺序存储还是链式存储

二叉树有两种存法，各有各的适用场景。

顺序存储：用一个一维数组，按完全二叉树的编号规则摆放节点。对于完全二叉树，这种方式极其高效，不需要额外指针，下标就能算出父子关系。但如果是一棵普通二叉树，中间会有大量空位，空间浪费严重。比如一棵深度 4 只有 4 个节点的斜树，用数组存需要 15 个位置，白白浪费 11 个。

链式存储：每个节点带左指针和右指针，按需分配，不浪费。这是最通用的方案，也是我下面代码里主要用的。

还有一种“三叉链表”会额外存一个父指针，好处的向上回溯方便，代价是多一个指针的内存。面试时如果题目允许，用三叉链表能简化不少操作，平时练习建议先用二叉链表，把思路练扎实。

2.4 手写二叉链表的节点定义

C 语言里，二叉树节点本质就是一个结构体：

typedef struct BTNode { char data; // 数据域 struct BTNode *left; // 左孩子指针 struct BTNode *right; // 右孩子指针 } BTNode;

注意这里struct BTNode *left不能直接写成BTNode *left，因为在结构体内部类型名还没定义完，必须带struct关键字。这是我见过新手报错最多的点之一，编译器报unknown type name 'BTNode'就是这个问题。

3. 建树与四种遍历：C 语言完整代码与思路拆解

3.1 怎么把一棵树“造”出来

写遍历之前先得有树。我建议先用最简单的方式手动创建一棵固定结构的树，方便调试。下面我们约定创建一个这样的二叉树：

A / \ B C / / \ D E F

代码就是创建节点再连线：

BTNode *createNode(char data) { BTNode *node = (BTNode *)malloc(sizeof(BTNode)); node->data = data; node->left = NULL; node->right = NULL; return node; } BTNode *buildSampleTree() { BTNode *root = createNode('A'); root->left = createNode('B'); root->right = createNode('C'); root->left->left = createNode('D'); root->right->left = createNode('E'); root->right->right = createNode('F'); return root; }

以后所有遍历代码，我都拿这棵树来跑。你验证结果的时候心里有个图，比盲看代码清晰得多。

注意：malloc出来的节点一定要判断是否为空，尤其是树很大的时候。练习代码可以偷懒，工程上必须检查。

3.2 递归遍历：前序、中序、后序

二叉树最经典的操作就是三种深度优先遍历。它们之间的区别，说白了就是先访问根、先访问左子树、先访问右子树这三件事的顺序不同。

前序遍历（根左右）：先根，再左子树，再右子树。

void preOrder(BTNode *root) { if (root == NULL) return; printf("%c ", root->data); preOrder(root->left); preOrder(root->right); }

中序遍历（左根右）：先左子树，再根，再右子树。

void inOrder(BTNode *root) { if (root == NULL) return; inOrder(root->left); printf("%c ", root->data); inOrder(root->right); }

后序遍历（左右根）：先左子树，再右子树，最后根。

void postOrder(BTNode *root) { if (root == NULL) return; postOrder(root->left); postOrder(root->right); printf("%c ", root->data); }

对上面那棵树跑一遍，结果分别是：

前序: A B D C E F 中序: D B A E C F 后序: D B E F C A

新手最容易犯的错是递归边界写错。记住一句话：遇到空指针就返回，这就是整个递归的出口。没有这个边界，递归就会无限往下走，直到栈溢出，程序直接崩溃。

这三种遍历看起来只是换一下 printf 的位置，但意义完全不同：前序能在遍历时直接拿到根节点，适合拷贝一棵树；中序在二叉搜索树里能拿到递增序列；后序先处理孩子再处理根，适合释放整棵树的内存（先释放孩子再释放根，避免悬空指针）。

3.3 非递归遍历：手动模拟递归栈

面试和考研笔试比你写递归的情况少，更多是让你写出非递归版本，原因是递归调用有函数栈开销，深度过大可能栈溢出。非递归的本质就是用显式栈模拟系统栈。

以前序遍历为例：

void preOrderIter(BTNode *root) { if (root == NULL) return; BTNode *stack[100]; int top = -1; stack[++top] = root; while (top >= 0) { BTNode *p = stack[top--]; printf("%c ", p->data); // 注意先压右孩子，再压左孩子 if (p->right) stack[++top] = p->right; if (p->left) stack[++top] = p->left; } }

因为栈是后进先出，要想先访问左子树，就得先把右孩子压栈、再压左孩子。

中序的非递归稍微绕一点，核心思路是：一直往左走到头，把沿途节点全部入栈，然后弹出一个访问，再转向右子树：

void inOrderIter(BTNode *root) { BTNode *stack[100]; int top = -1; BTNode *p = root; while (p != NULL || top >= 0) { while (p != NULL) { stack[++top] = p; p = p->left; } if (top >= 0) { p = stack[top--]; printf("%c ", p->data); p = p->right; } } }

这段代码值得反复琢磨。while (p != NULL)是在“深入左子树”，弹栈后p = p->right是在“转向右子树”，循环条件p != NULL || top >= 0保证了根节点为空但栈非空时还能继续处理。

3.4 层序遍历：队列 + 逐层访问

层序遍历就是从上到下、从左到右，一层一层访问。它对应广度优先搜索（BFS），需要借助队列实现：

void levelOrder(BTNode *root) { if (root == NULL) return; BTNode *queue[100]; int front = 0, rear = 0; queue[rear++] = root; while (front < rear) { BTNode *p = queue[front++]; printf("%c ", p->data); if (p->left) queue[rear++] = p->left; if (p->right) queue[rear++] = p->right; } }

层序遍历的思路和“报数排队”很像：根节点先入队，每次弹出队首，就把它的左右孩子入队。这样整棵树就按层级被顺序访问完了。对那棵树跑出来的结果是：

层序: A B C D E F

提示：队列的数组大小上限不要太抠，树很大的时候建议动态扩容，或者在结构体里维护容量。上面示例里用固定 100，只是演示核心逻辑。

3.5 遍历的实际应用：求深度、求叶子数、重建二叉树

学会遍历之后，很多问题其实都是“在遍历过程中顺手做点事”。比如求树的高度：

int treeHeight(BTNode *root) { if (root == NULL) return 0; int leftH = treeHeight(root->left); int rightH = treeHeight(root->right); return (leftH > rightH ? leftH : rightH) + 1; }

这个递归逻辑是：一个树的高度等于左右子树中较高者的高度加 1。空树高度为 0，叶子节点高度就是 1。

求叶子数也一样：

int leafCount(BTNode *root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return leafCount(root->left) + leafCount(root->right); }

还有一个高频题：已知前序和中序，重建二叉树。原理是前序第一个元素是根，根在中序里把序列切成左子树和右子树两块，然后递归处理。

BTNode* buildTreeFromPreIn(char *pre, char *in, int n) { if (n <= 0) return NULL; BTNode *root = createNode(pre[0]); int pos = 0; while (in[pos] != pre[0]) { pos++; } root->left = buildTreeFromPreIn(pre + 1, in, pos); root->right = buildTreeFromPreIn(pre + 1 + pos, in + pos + 1, n - pos - 1); return root; }

这个算法的前提是所有节点值不重复。如果题目允许重复值，判断位置时要特别小心，不能简单地用in[pos] != pre[0]找根。

4. 堆：完全二叉树的最佳舞台

4.1 堆的定义与下标规律

讲完普通二叉树，接下来是堆。堆是一种特殊的树，它必须满足两个条件：

1. 它是一个完全二叉树；
2. 任意节点的值总是不大于（或不小于）其孩子的值。

不大于孩子的是小顶堆（最小堆），根节点是全局最小值；不小于孩子的是大顶堆（最大堆），根节点是全局最大值。

堆最妙的地方是：因为它是完全二叉树，所以不需要链式指针，直接用数组就能存。如果我们用 0 作为起始下标，那么：

这个规律是堆所有操作的基础。比如数组[10, 7, 8, 5, 6, 4]，下标 0 是根节点 10，下标 1 是 7，它的左孩子是下标 3 的 5，右孩子是下标 4 的 6，完全正确。

4.2 堆的核心操作：上滤与下滤

堆的两个核心操作，一个是“往上冒”，一个是“往下沉”。

上滤（shift-up）：插入新节点时，先把新元素放到数组末尾，也就是完全二叉树的最后一个位置，然后它不断和父节点比较。如果违反堆序（比如大顶堆里新节点比父节点大），就交换位置，直到满足条件或者到达根节点。

下滤（shift-down）：删除堆顶时，把数组最后一个元素挪到根位置，堆的大小减 1，然后这个元素从根开始不断和较大的孩子比较（大顶堆），如果比孩子小就交换，一路沉下去直到合适位置。

这两种操作的时间复杂度都是 O(log n)，因为完全二叉树的高度是 log n 级别。这比在无序数组里维护最大值要高效太多。

4.3 C 语言实现一个最大堆

我用数组实现一个最大堆，包含创建、插入、删除堆顶、获取堆顶这几个常用操作。

typedef struct { int *data; int size; int capacity; } MaxHeap; MaxHeap* heapCreate(int capacity) { MaxHeap *heap = (MaxHeap *)malloc(sizeof(MaxHeap)); heap->data = (int *)malloc(sizeof(int) * capacity); heap->size = 0; heap->capacity = capacity; return heap; } void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } void shiftUp(MaxHeap *heap, int index) { while (index > 0) { int parent = (index - 1) / 2; if (heap->data[index] <= heap->data[parent]) break; swap(&heap->data[index], &heap->data[parent]); index = parent; } } void shiftDown(MaxHeap *heap, int index) { int n = heap->size; while (1) { int largest = index; int left = 2 * index + 1; int right = 2 * index + 2; if (left < n && heap->data[left] > heap->data[largest]) largest = left; if (right < n && heap->data[right] > heap->data[largest]) largest = right; if (largest == index) break; swap(&heap->data[index], &heap->data[largest]); index = largest; } } void heapInsert(MaxHeap *heap, int value) { if (heap->size >= heap->capacity) return; heap->data[heap->size] = value; shiftUp(heap, heap->size); heap->size++; } int heapPoll(MaxHeap *heap) { if (heap->size == 0) return -1; int result = heap->data[0]; heap->data[0] = heap->data[heap->size - 1]; heap->size--; shiftDown(heap, 0); return result; } int heapPeek(MaxHeap *heap) { if (heap->size == 0) return -1; return heap->data[0]; }

这里shiftDown里比较的是left < n和right < n，防止数组越界访问。很多新手写堆的时候，只记得比较大小，忘记判断孩子是否存在，结果一运行就segmentation fault。这个是堆实现里最常见的坑。

4.4 堆排序：只用数组就能排序的经典算法

堆排序的思路非常漂亮：先用数组建堆，然后反复把堆顶（最大值）和数组末尾交换，堆的大小减 1，再对新的根节点做一次下滤。这样每一轮都能把当前最大值放到最终位置。

下面是一个纯数组版的最大堆排序：

void siftDown(int *arr, int n, int index) { while (1) { int largest = index; int left = 2 * index + 1; int right = 2 * index + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest == index) break; int tmp = arr[index]; arr[index] = arr[largest]; arr[largest] = tmp; index = largest; } } void heapSort(int *arr, int n) { // 1. 从最后一个非叶子节点开始，逐个下滤，构建最大堆 for (int i = n / 2 - 1; i >= 0; i--) { siftDown(arr, n, i); } // 2. 反复把堆顶移到末尾，缩小堆范围 for (int i = n - 1; i > 0; i--) { int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; siftDown(arr, i, 0); } }

建堆为什么从n / 2 - 1开始？因为数组下标从 0 开始，最后一个非叶子节点就是最后一个节点的父节点(n - 1 - 1) / 2 = n / 2 - 1。叶子节点本身没有孩子，不需要下滤。

堆排序的时间复杂度是 O(n log n)，其中建堆是 O(n)，交换加下滤是 O(n log n)。而且它是原地排序，不需要额外空间，这是它比归并排序更省内存的地方。不过它不稳定，相同元素的相对顺序可能在排序后被改变，这在实际应用中是需要考虑的一个点。

5. 二叉树与堆到底能干什么

5.1 二叉搜索树：比链表更快的查找方式

二叉树最常见的变体是二叉搜索树（BST），它满足：左子树上所有节点的值都小于根节点，右子树上所有节点的值都大于根节点。查找时，平均只需要 O(log n) 时间就够了，而有序链表是 O(n)。

但 BST 有个致命缺陷：如果插入顺序是递增的，它会退化成一条链表，查找变成 O(n)。为了解决这个问题，才有了平衡二叉树（AVL）、红黑树这些进阶概念。理解了普通二叉树，再去看 AVL 的左旋右旋，会顺很多。

5.2 哈夫曼树：压缩与编码的基础

哈夫曼树（最优二叉树）是另一棵很出名的树，它的特点是带权路径长度最小。简单说，经常出现的字符放在离根近的地方，不常出现的字符放远一点，这样编码后的总长度最短。它是文件压缩、编码传输的基础。

构建哈夫曼树的思路也很有意思：每次从节点集合里取两个权值最小的节点，合并成一个新节点，再放回集合，重复直到只剩一个根。这个过程本质上是贪心算法。“二叉树的遍历”和“最小堆”在这里可以配合使用——用最小堆来快速取出两个最小权值节点。

5.3 堆的工程应用：优先队列、Top K、定时器

堆在工程里最直接的身份是优先队列。优先队列的“先进先出”不重要，重要的是“优先级最高的先出”。操作系统进程调度、任务队列、网络报文优先级，底层常用堆实现。

还有一个经典场景是Top K 问题：从海量数据里找出最大的 K 个数。做法是维护一个大小为 K 的最小堆，每来一个新元素就和堆顶比较，如果比堆顶大，就替换堆顶并调整。这样堆里始终是“目前见过的最大 K 个数”，时间和空间都控制得很好，在面试里几乎天天出现。

另外，定时器、优先任务调度、Dijkstra 最短路径算法里也都有堆的身影。可以说堆是所有高效算法里最常用的基础数据结构之一。

5.4 表达式树与编译器

把中缀表达式(a + b) * c转成表达式树后，叶子节点是操作数，内部节点是运算符。对表达式树做后序遍历，得到的就是后缀表达式；做中序遍历，表达式括号还保留了运算优先级。编译器在解析表达式时，本质上就是构建和遍历这种树，这离不开二叉树的基础能力。

6. 新手高频错误与排错清单

6.1 空指针与递归边界

这是二叉树最容易崩溃的地方。写递归代码前先问自己三个问题：

• 函数进入时空节点怎么处理？
• 节点只有左孩子或只有右孩子时，逻辑会不会越界？
• 递归的终止条件能不能覆盖所有空子树情况？

我建议所有二叉树函数，第一行都习惯性加上if (root == NULL) return ...;。听起来废话，但真的能救命的。调试时如果segmentation fault，先用 gdb 打断点看是哪个节点是空指针，八成是访问了NULL->left或者NULL->right。

6.2 遍历顺序混淆

前中后序的英文缩写很简单：先根、中根、后根，分别对应 preorder、inorder、postorder。你要是老记混，就按“根的位置”来记：pre 是根在前，in 是根在中间，post 是根在最后。

笔试里经常让根据遍历结果推树，有一个必背结论：已知前序和中序，能唯一确定一棵二叉树；已知中序和后序，也能唯一确定；但只知道前序和后序，通常无法唯一确定。原因很简单：前序和后序能确定根，但没法确定左右子树的边界。

6.3 堆的数组越界与下标混乱

写堆排序时，很多同学在left < n和right < n判断上栽跟头。当节点只有左孩子没有右孩子时，right可能等于 n，这时候arr[right]就会越界。数组下标虽然从 0 开始，但堆的逻辑编号和下标之间的对应关系必须心里门清。

还有一个小坑：堆排序的第二个循环里，交换之后调用siftDown(arr, i, 0)，第一个参数是i而不是n，因为堆的有效长度已经缩小了。这一步写错，结果就会乱七八糟。

6.4 我的一点训练建议

踩过这么多坑之后，我的建议是：不要光盯着别人的代码看，一定要自己手写。

第一遍，照着博客抄一遍，跑通；第二遍，合上博客，自己从零写建树和遍历；第三遍，加难度，写非递归、写层序、写重建二叉树、写堆排序。这三遍下来，这一章的内容基本就是你的了。

还有一个辅助技巧：每次写完一段树相关的代码，立刻在纸上把树画出来，把遍历结果写出来，再跑代码验证。人的脑子对图像比对抽象代码记忆更牢固，尤其是递归过程，画图能让你瞬间看清调用顺序。

我个人在实际练这块时，最受益的一个习惯是把所有遍历函数都放在同一个 main 文件里，每写一个函数立刻打印结果对比。遇到和预期不一致，就用小树（比如 3、4 个节点）单步调试，不要一上来就在大树上找 bug。数据结构不像算法题那样需要套路轰炸，它就是一层一层的东西，树不过是一个节点加两个指针，堆不过是一个数组加两条规则。把这层窗户纸捅破，后面的红黑树、B 树、图论，学起来都会轻松太多。