数据结构这门课不少人学到二叉树就开始掉队了。指针、递归、层序、前中后序乍一看全是新概念其实核心就那么几个点。这篇博客我打算用 C 语言把“树 - 二叉树 - 堆”这条线完整串一遍从基本概念讲到代码实现再讲到堆排序。无论你是正在准备期末考试还是自学补基础只要跟着思路走一遍自己动手把代码敲出来二叉树这关就算彻底过了。1. 从树开始先把这些术语一次性讲透1.1 树到底是个什么东西树是一种非线性的数据结构。你之前接触的数组、链表、栈、队列都是线性结构数据是一个挨着一个排队的。树不一样它有一个根节点然后向下分叉每个节点可以连接多个子节点就像文件夹套文件夹一样。比如你的电脑目录C盘 ├── 用户 │ └── 下载 ├── Program Files └── Windows这就是一棵典型的树。最顶层的 “C盘” 是根节点“用户”“Program Files”“Windows” 是它的孩子它们之间不是简单的先后关系而是层次关系、父子关系。树的结构在现实中到处都是公司的组织架构、网页的 DOM 树、编译器的语法分析树、路由器的路由表……所以学树不只是为了考试它几乎是所有复杂系统的底层骨架。1.2 树的术语表建议直接背诵学树的第一道门槛是术语一共就那么几个但考试和面试都爱考我给你整理成一张表术语含义例子根节点没有父节点的节点上面的 “C盘”父节点、子节点直接上下级关系“用户” 是 “下载” 的父节点兄弟节点同一个父节点的多个子节点“用户” 和 “Windows” 是兄弟叶子节点没有子节点的节点“下载”“Program Files”度一个节点拥有的子树个数“用户” 的度是 1树的度所有节点中最大的度整棵树最大的度数深度 / 层次根节点深度为 0 或 1看教材约定建议统一用根为 1高度该节点到最远叶子的路径长度叶子高度为 0 或 1森林多棵互不相交的树组成把根删掉剩下的子树就是森林这里最容易搞混的是深度和高度。简单记深度是从上往下数根到节点高度是从下往上数节点到叶子。不同教材对根在第 0 层还是第 1 层有分歧你自己做题时先看题目约定代码里我习惯用“空树高度 -1根节点高度 0”的算法后面写递归代码时会体现。1.3 为什么偏偏是二叉树树可以有多个分叉但数据结构里研究得最多的是二叉树。原因很现实二叉树每个节点最多两个子节点存储结构简单左右孩子用两个指针就能搞定任何多叉树都能通过“左孩子右兄弟”的方式转换成二叉树研究二叉树等于研究了一般树二叉树上的算法遍历、查找、插入逻辑最清晰是后续红黑树、B 树、堆的基础。所以别急着去纠结三叉树四叉树先把二叉树的底子打牢。2. 二叉树的形态、性质与存储选型2.1 满二叉树、完全二叉树、斜树别再搞混二叉树里有三个高频概念很多新手栽在这里。满二叉树每一层都是满的。深度为 k 的满二叉树一共有 2^k - 1 个节点节点数严格按照指数增长。比如深度 3 的满二叉树总共 7 个节点第 3 层有 4 个叶子。完全二叉树除了最后一层上面全是满的最后一层的节点要从左到右连续排列不能有空洞。满二叉树一定是完全二叉树但完全二叉树不一定是满的。判断方法很简单给每个节点从 1 开始编号看编号是否和满二叉树完全一致中途不能断开。斜树所有节点都偏向一边比如只有左孩子或者只有右孩子这种树其实退化成了链表。斜树在存储上会造成很大的空间浪费在查找效率上也没有优势所以实际工作中很少直接用但它经常被拿来测试算法边界情况。2.2 二叉树的五个重要性质会推比会背强背性质没什么意义但下面这几个性质做题时会反复用到我给你推一遍第 i 层最多有 2^(i-1) 个节点。这个看等比数列就知道第一层 1 个第二层 2 个第三层 4 个。深度为 k 的二叉树最多有 2^k - 1 个节点。等比数列求和1 2 4 ... 2^(k-1) 2^k - 1。n0 n2 1。叶子节点数 度为 2 的节点数 1。这个性质最常考证明思路是总边数 节点数 - 1同时总边数又等于 0n0 1n1 2*n2联立可得。做题时碰到“度为 0 和度为 2 的关系”直接秒答。具有 n 个节点的完全二叉树深度为 floor(log2 n) 1。因为完全二叉树节点数 n 满足 2^(k-1) - 1 n ≤ 2^k - 1取对数即可。对完全二叉树按层序编号节点 i 的左孩子是 2i右孩子是 2i1父节点是 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 堆的定义与下标规律讲完普通二叉树接下来是堆。堆是一种特殊的树它必须满足两个条件它是一个完全二叉树任意节点的值总是不大于或不小于其孩子的值。不大于孩子的是小顶堆最小堆根节点是全局最小值不小于孩子的是大顶堆最大堆根节点是全局最大值。堆最妙的地方是因为它是完全二叉树所以不需要链式指针直接用数组就能存。如果我们用 0 作为起始下标那么节点下标 i左孩子下标右孩子下标父节点下标i2*i 12*i 2(i-1) / 2这个规律是堆所有操作的基础。比如数组[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 树、图论学起来都会轻松太多。