很多人学数据结构的时候前面线性表、栈、队列一路都还顺一到树就卡住了指针套指针递归套递归调试器一开满屏都是地址。我第一次写二叉树的插入程序跑起来直接崩盯着代码查了两个多小时最后发现根指针作为参数传进去改的是个副本原指针根本没动。所以这篇我就按自己的理解把 C 语言里的树和二叉树从头到尾捋一遍结构体怎么定义、指针怎么传才不出错、四种遍历怎么写、深度和节点数怎么算、二叉搜索树和哈夫曼树这些变体各自能干嘛。不管你是刚学到这一章还是在准备期末复习、实验报告甚至工作几年后想回头把基础补扎实下面这些内容应该都能用得上。1. 树这个结构到底解决什么问题1.1 从线性结构到层次结构数组和链表都是一条线一个挨着一个。数组的好处是按下标访问快时间复杂度 O(1)但中间插一个元素就得整体搬动代价 O(n)链表插入删除只要改指针O(1) 搞定可要找一个元素必须从头顺着走O(n)。这两种结构在处理层次关系时都很别扭比如公司组织架构、文件目录、家谱、运算符的优先级这些天然就是一层套一层的东西硬塞进一条线里会非常难维护。树就是为这种一对多的层次关系准备的。它有一个根往下分叉每个节点可以有多个孩子。这个形状跟现实里的树是反着的——根在最上面枝叶往下长这一点刚开始容易别扭习惯就好。它的价值在于在比较理想的情况下查找、插入、删除都能做到 O(log n) 这个量级比线性结构的 O(n) 好太多。后面要讲的二叉搜索树、平衡树本质都是在追求这个 log 级别的效率。1.2 树在真实系统里都藏在哪别以为树只是课本里的习题它几乎无处不在。文件系统就是典型的树结构目录套目录浏览器的 DOM 结构是一棵树改一个节点会连带影响它的子孙编译器的语法分析阶段会生成抽象语法树AST你写的每行代码在编译器眼里都是一棵表达式树数据库索引大量使用 B 树因为磁盘读写一次代价很高需要把树压得又矮又胖来减少 I/O 次数。再看操作系统内核内存管理里管理虚拟内存区域用的是红黑树任务调度器里也有红黑树的身影网络路由表的前缀匹配常常用字典树数据压缩里的哈夫曼编码依赖哈夫曼树。你会发现凡是需要分级查找前缀匹配按优先级排序的地方树几乎都会出现。所以这一章不是应付考试它是后面很多课程和工程问题的地基。2. 树与二叉树的基础概念一次讲透2.1 递归定义和必须记住的术语树的定义本身就是递归的一棵树是由一个根节点和若干棵互不相交的子树组成的每棵子树又各自是一棵树。这个自己定义自己的特点决定了后面几乎所有操作都适合用递归来写。术语这块必须分清不然后面做题、看代码全是懵的。节点的度指的是它有几个孩子一棵树的度是整棵树里节点度的最大值。度为零的节点叫叶子节点也叫终端节点度不为零的是分支节点。节点的孩子叫子节点往上叫父节点同一个父节点下的是兄弟节点。从根到某个节点经过的所有节点是它的祖先反过来是子孙。节点拥有的子树数量决定它的度。还有一个容易混淆的森林是若干棵互不相交的树组成的集合把一棵树的根去掉剩下的子树集合就是一个森林。2.2 深度、高度、层次到底怎么数这块是考试最容易丢分的地方因为不同教材的定义有细微差别我先按国内主流教材比如王道那套的约定讲清楚。层次从根开始算根是第 1 层它的孩子是第 2 层往下依次加一。节点的深度是自顶向下累加的根节点的深度是 1节点的高度是自底向上累加的叶子节点的高度是 1。整棵树的高度也常叫深度等于所有节点层次的最大值。要注意的是有些国外教材和编程场景里根节点的深度定义为 0空树高度定义为 -1。这两种约定没有对错关键是同一道题、同一份代码里保持一致。我自己写代码时习惯让空树深度返回 0这样递归式max(left, right) 1写起来最干净也不用处理边界负数。你做实验报告的时候最好在开头注明用的是哪种约定免得老师按另一种标准扣分。2.3 满二叉树与完全二叉树的编号规律满二叉树指每一层的节点数都达到最大深度为 h 的满二叉树一共有 2^h − 1 个节点。完全二叉树则是除了最后一层其他层都是满的并且最后一层的节点全部集中在左边中间不能有空洞。完全二叉树这个限制看起来苛刻但它带来一个极大的好处——可以用数组来存储而且父子关系可以用下标直接算出来不需要指针。如果把根节点编号为 1那么节点 i 的左孩子是 2i右孩子是 2i1父节点是 i/2i1 时如果编号从 0 开始左孩子是 2i1右孩子是 2i2父节点是 (i−1)/2。这套公式是堆排序、优先队列的底层基础务必背熟。还有几个高频结论具有 n 个节点的完全二叉树高度是 ⌊log₂n⌋ 1叶子节点数 n₀ 和度为 2 的节点数 n₂ 满足 n₀ n₂ 1这个公式对任何非空二叉树都成立非常好用。概念定义要点高频结论满二叉树每层都满深度 h 时节点数 2^h − 1完全二叉树最后一层靠左连续可用数组存高度 ⌊log₂n⌋1叶子与双分支度 0 与度 2n₀ n₂ 13. C语言里如何定义和创建一棵二叉树3.1 结构体设计与内存布局二叉树的节点里要放数据还要能指向左右两个孩子所以最直接的定义是这样typedef struct TreeNode { int data; // 数据域实际项目中可能是结构体 struct TreeNode *left; // 左孩子指针 struct TreeNode *right; // 右孩子指针 } TreeNode;这里有个细节值得说结构体内部的指针必须写完整的struct TreeNode *因为在结构体定义还没结束的时候TreeNode这个别名还没生效。有人图省事写成TreeNode *left编译器直接报错。内存上一个节点占的空间大致是数据域加上两个指针64 位机器上两个指针就是 16 字节加上对齐节点往往比你想的要胖所以数据域别塞太大的结构体常见做法是节点里只放一个指向实际数据的指针。3.2 指针传参的坑为什么要用二级指针这是我开头提到的那个坑。C 语言是值传递函数参数拿到的是实参的副本。如果你写void insert(TreeNode *root, int val)函数里修改root指向外面那个根指针纹丝不动。想让函数真正改变根指针的指向必须传指针的地址也就是二级指针void insert(TreeNode **root, int val) { if (*root NULL) { TreeNode *node (TreeNode *)malloc(sizeof(TreeNode)); node-data val; node-left node-right NULL; *root node; // 修改的是外面那个指针本身 return; } if (val (*root)-data) insert((*root)-left, val); else insert((*root)-right, val); }另一种常见做法是让插入函数返回新的根节点root insert(root, val)这样也能把变化带出去可读性还更好。两种都行但我建议初学者先用返回指针的版本等对指针理解透了再玩二级指针。实际排错时一旦发现树建出来是空的或者插入后根没变八成就是这个传参问题。3.3 建树、销毁与内存管理用前序序列建树是最常见的实验题。约定一个特殊值表示空节点比如输入 -1 或者字符 #TreeNode *createTree(void) { int ch; scanf(%d, ch); if (ch -1) return NULL; TreeNode *node (TreeNode *)malloc(sizeof(TreeNode)); node-data ch; node-left createTree(); node-right createTree(); return node; }写这段代码要保证输入序列本身是合法的前序扩展序列否则建出来的树会缺胳膊少腿。用完树之后一定要释放而且必须用后序顺序释放先放左、再放右、最后放自己反过来会访问到已经释放的内存void destroyTree(TreeNode *root) { if (root NULL) return; destroyTree(root-left); destroyTree(root-right); free(root); }注意malloc 之后如果没有检查返回值在大规模建树时可能悄悄拿到 NULL程序在别处崩溃排查起来非常费劲。养成if (node NULL) return NULL;的习惯。4. 二叉树的四种遍历递归和非递归都写一遍4.1 先序、中序、后序的递归写法遍历的命名看的是根节点被访问的时机。先序是先根、再左、再右中序是先左、再根、再右后序是先左、再右、再根。三种递归写法结构几乎一样只是打印语句挪位置void preOrder(TreeNode *root) { if (root NULL) return; printf(%d , root-data); preOrder(root-left); preOrder(root-right); } void inOrder(TreeNode *root) { if (root NULL) return; inOrder(root-left); printf(%d , root-data); inOrder(root-right); } void postOrder(TreeNode *root) { if (root NULL) return; postOrder(root-left); postOrder(root-right); printf(%d , root-data); }递归版本好写但有个隐藏问题递归深度等于树的高度。如果树退化成一条链几百层还能扛几百万层就会爆栈实际项目里这种输入是可能出现的。所以工程代码里非递归版本并不是炫技而是真的有防御价值。4.2 用栈把递归改成非递归中序的非递归思路是一路向左把节点压栈压到底之后弹出一个访问再转向它的右子树如此循环。这个过程其实是手动模拟了系统的函数调用栈void inOrderIter(TreeNode *root) { TreeNode *stack[100]; int top -1; TreeNode *p root; while (p ! NULL || top ! -1) { while (p ! NULL) { stack[top] p; p p-left; } p stack[top--]; printf(%d , p-data); p p-right; } }先序的非递归更简单压栈后先访根再压右孩子、压左孩子因为栈是后进先出压的顺序要反过来。后序稍微绕一点有个小技巧按根右左的顺序遍历把结果反过来就是后序或者用双栈法。我个人的经验是考试里掌握中序和先序的非递归足够后序非递归理解思路即可真写起来容易出错不如直接用两个栈写清楚。4.3 层序遍历与队列层序是一层一层从左到右访问这就要用到队列。手写一个数组队列就够了void levelOrder(TreeNode *root) { if (root NULL) return; TreeNode *queue[100]; int front 0, rear 0; queue[rear] root; while (front rear) { TreeNode *p queue[front]; printf(%d , p-data); if (p-left) queue[rear] p-left; if (p-right) queue[rear] p-right; } }层序遍历的用途比想象中大求树的最大宽度、按层打印、判断完全二叉树、求最左下角的节点都要靠它。判断完全二叉树的经典做法就是层序遍历一旦遇到空节点后面就不允许再出现非空节点否则就不是完全二叉树。4.4 用两种遍历序列还原一棵树这道题基本每学期都考。结论是先序 中序、后序 中序、层序 中序都能唯一确定一棵二叉树但先序 后序不能。原因是中序能告诉我们根节点左边是左子树、右边是右子树从而划分区间。以先序加中序为例TreeNode *build(int *pre, int *in, int len) { if (len 0) return NULL; int rootVal pre[0], i; for (i 0; i len; i) if (in[i] rootVal) break; TreeNode *root (TreeNode *)malloc(sizeof(TreeNode)); root-data rootVal; root-left build(pre 1, in, i); root-right build(pre 1 i, in i 1, len - i - 1); return root; }这里的关键就是算出左子树的长度 i然后正确偏移三个数组的下标。写的时候容易在偏移量上翻车建议先在纸上画出两个序列标好区间再动手。5. 深度、节点数、叶子数这些高频计算5.1 二叉树深度的递归与迭代求法深度是最常考的量。递归版本三行就够int depth(TreeNode *root) { if (root NULL) return 0; int l depth(root-left); int r depth(root-right); return (l r ? l : r) 1; }这个函数的时间复杂度是 O(n)因为每个节点都要访问一次空间复杂度是 O(h)h 是树高来自递归栈。想用迭代写就配合层序遍历每处理完一层计数加一或者手动维护一个栈记录每个节点对应的深度。如果你追求极致也可以在遍历时用一个数组存每层节点数最后取最大。5.2 节点统计的通用套路求节点总数、叶子数、度为 2 的节点数套路都一样递归到左右子树再按条件合并。int countNodes(TreeNode *root) { if (root NULL) return 0; return 1 countNodes(root-left) countNodes(root-right); } int countLeaves(TreeNode *root) { if (root NULL) return 0; if (root-left NULL root-right NULL) return 1; return countLeaves(root-left) countLeaves(root-right); }写这类题的时候先想清楚递归出口是什么当前节点要不要算进去左右结果怎么合并想清楚这三点几乎所有树上的统计题都能套进去。这也是树这一章训练递归思维的价值所在。5.3 完全二叉树性质在堆里的应用堆本质就是一棵完全二叉树只不过额外加了父节点不小于或不大于孩子的顺序性质。正因为是完全二叉树堆可以用数组实现父子下标直接算不需要任何指针。建堆的过程是自底向上调整时间复杂度 O(n)比一个个插入的 O(n log n) 更快这个结论很多人第一次听到会很意外。再说个实用结论n 个节点的完全二叉树最后一个非叶子节点的下标是 n/2 − 1按根为 0 编号从这个位置往前逐个向下调整就能建好堆。堆排序、优先队列、TopK 问题都建立在这套性质上把这块搞懂后面很多算法题都会顺畅很多。6. 从二叉搜索树到平衡树工程上的取舍6.1 BST的插入、查找、删除二叉搜索树BST的规矩是左子树所有节点的值都小于根右子树所有节点的值都大于根。有了这个性质查找就像二分TreeNode *search(TreeNode *root, int val) { while (root ! NULL) { if (val root-data) return root; root (val root-data) ? root-left : root-right; } return NULL; }插入沿着查找路径走到空位置挂上去就行。删除是最麻烦的分三种情况删叶子直接删只有一个孩子用孩子顶替有两个孩子时用中序后继右子树里最小的那个或者中序前驱替换掉要删的值再递归删除那个后继节点。第三种情况是很多人第一次写会绕晕的地方记住先用后继的值覆盖再删后继这个口诀就不会错。6.2 退化问题与AVL、红黑树BST 有个致命缺点如果你按从小到大有序插入它就退化成一条链表查找从 O(log n) 变回 O(n)。显然依赖它就等于把性能交给了运气。解决办法是让树自动平衡。AVL 树规定任意节点左右子树高度差不超过 1一旦违反就通过左旋、右旋、左右旋、右左旋来调整。它查询效率高但插入删除时旋转比较频繁。红黑树则放松了平衡条件用颜色约束保证最长路径不超过最短路径的两倍插入删除时的调整次数更少所以在工程里更受欢迎。像 C 的 std::map、Java 的 TreeMap底层都是红黑树。选哪个其实是个权衡读多写少用 AVL读写都频繁用红黑树这不是死规定但大方向是这样。6.3 B树、B树为什么在数据库里吃香磁盘和内存的速度差距是几个数量级所以数据库索引设计的核心目标不是比较次数少而是磁盘 I/O 次数少。二叉树再平衡高度也是 log₂n 级别一亿条数据要二十多层每次读一层可能就是一次磁盘访问。B 树改成多路一个节点存几百个关键字高度能压到三四层I/O 次数一下就降下来了。B 树又在 B 树基础上做了优化所有数据都放在叶子节点叶子之间用链表串起来。这样范围查询只要找到起点然后顺着链表扫就行特别适合数据库里的区间检索。索引的度节点能容纳多少个孩子取决于磁盘块大小磁盘块一般是 4KB一个关键字加一个指针大概十几字节算下来一个节点能放几百路这就是它能变矮的算术依据。7. 几类特殊树的应用场景7.1 哈夫曼树与压缩编码哈夫曼树的目标是让带权路径长度WPL最小。做法是每次从集合里取两个权值最小的节点合并新节点的权值是两者之和放回集合重复直到只剩一个节点。用最小堆实现这个取两个最小的动作复杂度是 O(n log n)。它最经典的应用是哈夫曼编码出现频率高的字符分配短码频率低的分配长码而且任何一个编码都不是另一个的前缀保证解码无歧义。这也是压缩软件、图像格式里常见的底层思路。考试里常见题型是给一组权值让你画树、算 WPL只要记住每次取最小两个合并就不会画错。7.2 字典树Trie与前缀搜索字典树按字符逐层存储每条从根到某节点的路径代表一个前缀。它特别适合做前缀查询比如输入法联想、搜索框自动补全、敏感词过滤。插入和查询的复杂度是 O(L)L 是字符串长度跟你存了多少词没关系这是它相对哈希表的优势。typedef struct TrieNode { struct TrieNode *child[26]; int isEnd; } TrieNode;用一个 26 大小的数组表示小写字母的孩子isEnd标记这个节点是不是某个单词的结尾。缺点是空间开销大每个节点都要预分配 26 个指针实际工程里常用哈希表或压缩字典树来省内存。7.3 表达式树与四则运算求值表达式树是编译器前端的常见练手项目。叶子是操作数内部节点是运算符中序遍历得到中缀表达式后序遍历直接就能求值。实现时通常先把中缀表达式转成后缀用栈处理运算符优先级再用后缀序列建树。求值时递归地算出左右子树的值再按当前运算符合并遇到除号还要判断除零。这套东西看着简单但把括号、优先级、多位数、负数都考虑进去代码量不小很适合当课程设计的题目。我自己写过一版支持加减乘除和括号的计算器踩的最多的坑就是优先级判断和负号与减号的区分建议先把状态机想清楚再动手。8. 常见报错与排查实录8.1 段错误和运行时错误的几个高发点写二叉树时遇到的崩溃九成来自这几处第一指针没初始化就用TreeNode *root;然后直接访问root-left第二free 之后又去访问那块内存造成悬空指针第三建树时输入序列不合法递归没有正确终止一直往下钻第四数组栈开太小非递归遍历时溢出。排查的时候我一般会先用 gdb 跑一遍或者简单粗暴地在关键位置加 printf 打印指针值看空指针到底出在哪一层。还有一个很隐蔽的坑用 scanf 读字符建树的时候换行符会被当成有效字符读进去导致树的形状跟预期完全不一样。解决办法是在读字符前加一个空格过滤空白比如scanf( %c, ch);注意那个空格它能跳过所有空白字符。8.2 内存泄漏与递归爆栈内存泄漏在树里特别容易发生因为节点是你一个个 malloc 出来的忘了释放或者只释放了一部分都很常见。写完建树功能后一定要配一个 destroy 函数并且用工具验证一下比如 valgrind看有没有 definitely lost 的报告。测试时故意多建几次树、多销毁几次观察内存占用是否稳定。递归爆栈则出现在树很深的时候尤其是退化成链的 BST。解决办法有两个一是把递归改成用显式栈的迭代版本二是给递归加一个深度上限做保护。如果只是做实验题一般规模小不用担心但如果是处理真实数据这两个问题都要提前想好。8.3 常见问题速查表现象可能原因处理方式程序直接崩溃指针未初始化 / 访问空节点用 gdb 定位加空指针判断建出来的树是空的根指针传参用了副本改二级指针或返回新根遍历结果不对输入序列含空白字符scanf 格式串前加空格内存持续增长没有释放节点后序 destroy配 valgrind深度算出来偏大空树返回值约定不一致统一根深度为 1 或 0删除 BST 节点后乱序双子节点处理错误用中序后继替换后再删提示调试树结构时先把树画出来再对代码比盯着代码硬想快得多。输入小规模数据手写上先序、中序结果跟程序输出对照问题很快能定位。9. 练手路线和一点个人建议如果让我重新学一遍这一章我会这样安排顺序先手写结构体和递归建树确保指针传参彻底搞明白接着把四种遍历的递归版默写一遍重点体会中序然后逼自己写出非递归中序和层序这一步能把栈和队列真正用起来再往上做深度、节点数、判断完全二叉树这类小题最后挑一个综合项目比如 BST 加表达式树或者哈夫曼编码压缩器把学的东西串起来。我个人踩过的最大教训是不要一开始就追求写出最漂亮的代码先把功能跑通再考虑优化。我见过不少人卡在想一次写对结果一整天没跑通一个遍历。实际上打印中间结果、用小数据验证、画图对照这些笨办法才是最省时间的。还有一点C 语言里指针的坑不会因为你理解了概念就自动消失只有多写多调手才会形成肌肉记忆。等你能不查资料默写出非递归后序遍历、能一眼看出 BST 删除的三种情况这一章就算真的过关了。