不需要主标题直接从二级标题开始。下面是完整的博文内容。1. 写在前面这一讲解决什么问题看到“16二叉树6”这种编号懂的人自然懂这是一套数据结构系列笔记里的第16篇、二叉树专题的第6部分。写到这里说明前面已经聊完了树的存储结构、基本遍历思路现在该碰硬骨头了二叉树的深度计算、搜索二叉树BST的增删查、线索二叉树以及一个几乎所有初学者都会撞上的墙——写着写着程序就报运行时错误而且怎么调都找不到原因。这篇笔记我打算换个讲法不只是摆代码而是把“为什么这么写”讲透。比如为什么递归遍历是二叉树的主旋律、为什么搜索二叉树的删除操作要分三种情况、为什么线索二叉树能让中序遍历不再依赖栈以及那些让人头皮发麻的段错误Segmentation fault到底是怎么冒出来的。适合正在啃数据结构、准备机试或面试、以及写二叉树代码总在崩溃边缘反复试探的同学。基础部分会从节点定义开始讲保证零基础也能跟上。2. 二叉树的基本盘节点定义与建树细节2.1 节点定义为什么长这样二叉树的节点定义十个人有九个人会写成这样typedef struct BiTNode { int data; // 数据域 struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree;有人会问为什么 left 和 right 指针的类型是struct BiTNode *而不能直接写BiTNode *原因很简单在typedef还没有生效之前编译器压根不认识BiTNode这个新名字。这是C语言里“先声明后使用”的基本规则很多运行时错误的根源其实在编译期就埋下了只是编译器没拦住而已。顺便说一句很多教材会在节点里额外加一个parent父指针这个不是必需品。普通二叉树用递归算法遍历时根本不需要回头找父亲加了反而让赋值操作变复杂。真正需要parent的场景是红黑树、并查集这类进阶结构初学阶段不建议一上来就加。2.2 建树的方式手动建一棵树 vs 序列建树手写一棵固定的树是最直观的学习方式。比如想建一棵这样的树1 / \ 2 3 / \ \ 4 5 6代码就是逐个申请节点、再手动把指针挂上BiTree createDemoTree() { BiTree root (BiTree)malloc(sizeof(BiTNode)); BiTNode *n2 (BiTNode*)malloc(sizeof(BiTNode)); BiTNode *n3 (BiTNode*)malloc(sizeof(BiTNode)); BiTNode *n4 (BiTNode*)malloc(sizeof(BiTNode)); BiTNode *n5 (BiTNode*)malloc(sizeof(BiTNode)); BiTNode *n6 (BiTNode*)malloc(sizeof(BiTNode)); root-data 1; root-lchild n2; root-rchild n3; n2-data 2; n2-lchild n4; n2-rchild n5; n3-data 3; n3-lchild NULL; n3-rchild n6; n4-data 4; n4-lchild n4-rchild NULL; n5-data 5; n5-lchild n5-rchild NULL; n6-data 6; n6-lchild n6-rchild NULL; return root; }这段代码看着简单但有个隐性风险如果中间某个malloc失败返回 NULL后面直接给n2-lchild赋值就会立刻崩溃。在实际工程里我不会这么裸写而是先封装一个createNode(int data)函数内部检查 malloc 结果失败就报错退出这种细节能帮你避开大量莫名其妙的运行时崩溃。另一种常见建树方式是根据先序遍历序列重建树。假设我们用一个特殊字符#表示空节点序列1 2 4 # # 5 # # 3 # 6 # #就能唯一确定上面那棵树。递归建树的代码非常优雅BiTree createTreeByPreOrder(int *arr, int *idx, int len) { if (*idx len) return NULL; if (arr[*idx] -1) { // 约定-1表示空 (*idx); return NULL; } BiTNode *node (BiTNode*)malloc(sizeof(BiTNode)); node-data arr[*idx]; (*idx); node-lchild createTreeByPreOrder(arr, idx, len); node-rchild createTreeByPreOrder(arr, idx, len); return node; }这里有个关键点idx必须传指针。因为递归过程要共享同一个“当前读到哪个位置”的游标如果传值每层递归拿到的是副本树就建歪了。这个坑我在刚学的时候踩过现在每次遇到“建树结果不对”的问题第一反应就是检查共享状态有没有正确传递。2.3 一个稳定可复用的建树模板综合来看我给初学者推荐一个比较稳的模板三个函数组合使用BiTNode* createNode(int data) { BiTNode *node (BiTNode*)malloc(sizeof(BiTNode)); if (node NULL) { printf(内存分配失败\n); exit(1); } node-data data; node-lchild node-rchild NULL; return node; } BiTree buildTree() { BiTNode *root createNode(1); BiTNode *n2 createNode(2); BiTNode *n3 createNode(3); BiTNode *n4 createNode(4); BiTNode *n5 createNode(5); BiTNode *n6 createNode(6); root-lchild n2; root-rchild n3; n2-lchild n4; n2-rchild n5; n3-rchild n6; return root; }createNode把“申请内存 初始化两个指针为 NULL”这件事固化下来每次创建节点都不用重复检查。C语言里最危险的就是用过未初始化的指针createNode直接杜绝了这种情况。到后面写搜索二叉树、线索二叉树时这个函数基本不用改直接复用。3. 二叉树的遍历递归、非递归与层序一次打通3.1 递归遍历为什么是“背下来就行”的老套路二叉树的递归遍历前序、中序、后序是数据结构里最不需要动脑子的部分因为每个版本都长得一模一样只有 printf 的位置不同void preOrder(BiTree root) { // 前序根左右 if (root NULL) return; printf(%d , root-data); preOrder(root-lchild); preOrder(root-rchild); } void inOrder(BiTree root) { // 中序左根右 if (root NULL) return; inOrder(root-lchild); printf(%d , root-data); inOrder(root-rchild); } void postOrder(BiTree root) { // 后序左右根 if (root NULL) return; postOrder(root-lchild); postOrder(root-rchild); printf(%d , root-data); }这段代码看起来简单到不值得写但很多人的运行时错误就藏在这个“简单”里就是有人会忘记第一行if (root NULL) return;。没有终止条件的递归跟没有出口的循环一样一旦跑到叶子节点的空孩子就无限往深处递归直到栈空间耗尽程序给你弹一个Segmentation fault。理解递归遍历的精髓是要把“打印”这个动作放在哪个位置想清楚。前序遍历打印在“进入左子树之前”中序遍历打印在“左子树返回之后、进入右子树之前”后序打印在“右子树返回之后”。这个顺序对应的正是递归调用栈里“第一次经过节点”“第二次经过节点”“第三次经过节点”的时机。想明白这个遍历就不需要背了。3.2 层序遍历队列怎么用才不踩坑层序遍历BFS要用队列核心思想是“每次出队一个节点就把它的左右孩子依次入队”。用C语言手写队列时最常出的问题是队头队尾指针搞混。我直接给一个循环数组队列版本void levelOrder(BiTree root) { if (root NULL) return; BiTNode *queue[100]; int front 0, rear 0; queue[rear] root; while (front rear) { BiTNode *cur queue[front]; printf(%d , cur-data); if (cur-lchild) queue[rear] cur-lchild; if (cur-rchild) queue[rear] cur-rchild; } }注意几个细节入队用rear出队用front判断队列空的条件是front rear队列满的条件要看你开多大。我这里的数组容量是100意味着最多只能存100个节点指针如果树有150个节点数组越界就会造成内存附近的数据被写坏——这又是“运行时错误”的一大来源。实际做题时如果树的规模没给上限建议直接用动态数组或者链式队列别贪图省事用固定数组。另外一个常见错误是在入队之前没有判断cur-lchild是否为 NULL导致 NULL 入队出队时访问NULL-data立刻崩掉。看似“多写一个if”很麻烦实则是在给运行时错误上保险。3.3 遍历结果有什么用千万别以为遍历只是输出数字。中序遍历二叉搜索树得到的是有序序列这是 BST 最经典的性质前序遍历可以用来做序列化后序遍历可以配合中序遍历唯一重建二叉树。如果你笔试题目说“已知前序和中序重建二叉树”本质就是利用根节点在中序序列里的位置去切分左右子树范围递归构造。从“只知道背代码”到“理解遍历结果的意义”是二叉树学习的第一个分水岭。很多人卡在后面写搜索二叉树删除操作根本原因是中序序列的有序性没内化成直觉。4. 二叉树的深度递归一行非递归要看懂4.1 递归求深度的标准写法二叉树的深度也叫高度严格来说略有区别后面细说递归公式就一句话当前节点的深度 max(左子树深度, 右子树深度) 1。代码只有五行int maxDepth(BiTree root) { if (root NULL) return 0; int leftDepth maxDepth(root-lchild); int rightDepth maxDepth(root-rchild); return (leftDepth rightDepth ? leftDepth : rightDepth) 1; }用上面的树算一遍节点4、5、6的深度都是1节点2的深度是 max(1,1)12节点3的深度是 max(0,1)12根节点1的深度是 max(2,2)13。整体逻辑非常直观。这个递归为什么不用写终止条件我写的是if (root NULL) return 0这就是终止条件。所有递归版本的树算法第一步永远是判空没有例外。如果有人在递归函数里先访问root-data再判空那么叶子节点的空孩子会直接炸给你看。4.2 非递归求深度的层序思路层序遍历天然能算出深度每遍历完一层深度加1。实现的关键是“怎么知道一层结束了”。经典做法是用levelSize变量记录当前层的节点数int maxDepthByLevel(BiTree root) { if (root NULL) return 0; BiTNode *queue[100]; int front 0, rear 0; int depth 0; queue[rear] root; while (front rear) { int levelSize rear - front; // 当前层节点数 while (levelSize--) { BiTNode *cur queue[front]; if (cur-lchild) queue[rear] cur-lchild; if (cur-rchild) queue[rear] cur-rchild; } depth; } return depth; }每次处理完一层rear - front的差值正好是下一层的节点数这个技巧在很多二叉树题目里都能复用比如“之字形打印二叉树”“求每层最大值”等等。面试时候如果非要你非递归求深度层序法的代码量最可控不容易错。4.3 深度和高度别在细节上翻车国内教材里深度和高度经常混用但严格定义是深度是从根节点往下数高度是从叶子节点往上数。根节点的深度为1有的教材是0叶子节点的高度为1。换算关系上对于任意一个节点它的深度 它所在子树的高度 - 1 整棵树的深度。做题和面试时先跟面试官确认好“根节点深度是0还是1”这个细节能让你的代码少一半边界错误。另外一个很容易忽略的点递归深度。如果树特别深比如一万层的退化树递归求深度时调用栈会爆掉因为系统栈的空间是有限的。这时候要么改成非递归层序法要么用尾递归或者迭代加深。刷LeetCode时那些提示“Stack Overflow”的大多数是这类问题。5. 搜索二叉树BST有序性的工程价值5.1 BST 到底是什么搜索二叉树Binary Search Tree也叫二叉排序树/二叉查找树的定义并不复杂左子树所有节点值小于根节点右子树所有节点值大于根节点且左右子树各自都是BST。这个定义一出来立刻就能得到一个关键推论中序遍历BST输出结果必然是有序递增的。我为什么要在二叉树专题里专门强调BST因为它是从“结构”迈向“算法”的关键一步。普通二叉树只是一堆节点的集合而BST因为存在“有序性”查找效率可以达到 O(logn)。工程上的数据库索引、C 的 std::map、Java 的 TreeMap底层都是这种思路的变体红黑树是平衡版的BST。5.2 插入和查找递归写法怎么“带着结果往上走”BST插入的递归实现核心是“把新节点挂在合适的位置”。很多初学者写插入时总想用返回值传递新节点但又不理解为什么必须接收返回值BiTree insertBST(BiTree root, int key) { if (root NULL) { return createNode(key); } if (key root-data) { root-lchild insertBST(root-lchild, key); } else if (key root-data) { root-rchild insertBST(root-rchild, key); } // 相等则不做任何操作 return root; }这个函数的返回值是关键设计。叶子节点新插入时createNode(key)返回新节点地址上一层通过root-lchild insertBST(...)把这个新地址挂到正确位置。如果不接收返回值新节点就“丢”了整棵树不会有任何变化。我见过特别多人的代码把最后那行return root漏掉编译能过但插入永远失败——这类 bug 最坑人因为程序不崩但输出结果怎么都不对。查找逻辑类似BiTNode* searchBST(BiTree root, int key) { if (root NULL || root-data key) { return root; } if (key root-data) { return searchBST(root-lchild, key); } return searchBST(root-rchild, key); }或者写成迭代版空间复杂度直接降到 O(1)BiTNode* searchBSTIter(BiTree root, int key) { while (root ! NULL root-data ! key) { if (key root-data) root root-lchild; else root root-rchild; } return root; }选择迭代版还是递归版取决于场景。笔试机试时我推荐迭代版因为不用吃栈空间理解原理时用递归版因为和定义的形式最贴近。5.3 删除节点为什么是三种情况BST的删除是所有操作里最容易写崩的原因在于要处理“孩子数量”的不同情况情况一待删节点是叶子直接 free父节点对应指针置 NULL。情况二待删节点只有一个孩子用孩子替代它的位置。情况三待删节点有两个孩子经典做法是用中序遍历的前驱或后继节点值覆盖待删节点然后递归删除那个前驱/后继节点。为什么情况三不直接删因为直接删的话两个子树没法同时保留到父节点下面。BST每个节点最多有两个孩子你不可能把两棵子树都挂在原来位置。用前驱左子树中最大的节点或者后继右子树中最小的节点替换待删节点能保持中序序列有序性不变——这才是真正的目的不是“删节点”而是“删掉一个数同时保持搜索树性质”。删除的完整实现我贴一下中规中矩的教科书版本BiTree deleteBST(BiTree root, int key) { if (root NULL) return root; if (key root-data) { root-lchild deleteBST(root-lchild, key); } else if (key root-data) { root-rchild deleteBST(root-rchild, key); } else { // 找到待删节点 if (root-lchild NULL) { BiTNode *temp root-rchild; free(root); return temp; } if (root-rchild NULL) { BiTNode *temp root-lchild; free(root); return temp; } // 两个儿子都在找右子树最小节点作为后继 BiTNode *successor root-rchild; while (successor-lchild ! NULL) { successor successor-lchild; } root-data successor-data; root-rchild deleteBST(root-rchild, successor-data); } return root; }这段代码看着长实际上每一分支都很清晰。有一个细节值得单独说明在找右子树最小节点时我用的是while (successor-lchild ! NULL)一路向左找到的 successor 一定是“没有左孩子”的节点所以递归删除它时要么是情况一要么是情况二绝不会无限递归。5.4 BST 退化的经典坑BST最怕的输入是有序序列。如果按键值从小到大依次插入1,2,3,4,5整棵树会退化成一个“只有右孩子”的链表。这时查找复杂度从 O(logn) 恶化为 O(n)跟顺序查找没有区别。我在学习阶段就踩过这个坑用BST给一个大数组排序结果发现比简单数组排序还慢。后来才明白单纯BST不保证平衡只有 AVL 树、红黑树这类带自平衡机制的变体才能稳定享受 O(logn) 的查找效率。所以面试被问“BST有什么缺点”时一定要答到“可能退化成链表”这条顺带说说平衡树的解决思路这一下就能拉开和普通人的差距。6. 线索二叉树给遍历装一条捷径6.1 线索化到底想解决什么问题普通的二叉链表里叶子节点的左右指针都是 NULL这其实是浪费——一棵有 n 个节点的二叉树有 n1 个空指针这个结论可以计算出来每个节点有2个指针共2n个n个节点需要 n-1 条边连接所以空指针数 2n - (n-1) n1。线索二叉树Threaded Binary Tree的核心思路把这些空指针利用起来左空指针指向前驱节点右空指针指向后继节点。这样做最大的好处是中序遍历不需要递归或栈了。普通中序遍历依赖系统栈或手动栈这受限于栈深度线索化之后你可以沿着线索一遍走完空间复杂度降到 O(1)。这在嵌入式、底层系统等“栈资源极珍贵”的场景下有实际价值也是面试题里考线索二叉树的动机所在。6.2 中序线索化的核心思路线索化的难点在于一个节点的 left 可能指向真正的左孩子也可能指向前驱节点程序怎么区分解决方法是加两个标志位ltag和rtag。约定ltag0表示 left 是左孩子ltag1表示 left 指向前驱rtag同理。节点结构typedef struct ThreadNode { int data; struct ThreadNode *lchild, *rchild; int ltag, rtag; // 0:孩子, 1:线索 } ThreadNode, *ThreadTree;中序线索化的递归代码关键是要保留一个pre指针记录“刚刚访问过的节点”ThreadNode *pre NULL; void inThread(ThreadTree root) { if (root NULL) return; inThread(root-lchild); if (root-lchild NULL) { root-lchild pre; // 指向前驱 root-ltag 1; } if (pre ! NULL pre-rchild NULL) { pre-rchild root; // 前驱的后继指向当前节点 pre-rtag 1; } pre root; inThread(root-rchild); }这个pre就是全局遍历中序遍历序列时“上一个访问的节点”。线索化的过程不是单独处理每个节点而是每个节点都要“回头看”既设置自己的前驱线索又补充前驱节点的后继线索。这两个 if 一个都不能少我在初学时只写了第一个 if结果前驱节点都没指过来遍历到一半就断了。6.3 线索二叉树的遍历像走链表一样轻快中序线索二叉树找后继有现成的规律如果rtag 1右指针直接就是后继如果rtag 0则右子树里“最左下的节点”就是后继因为右子树里最小的节点是下一个被中序访问的。代码ThreadNode* firstNode(ThreadNode *p) { while (p-ltag 0) p p-lchild; return p; } ThreadNode* nextNode(ThreadNode *p) { if (p-rtag 1) return p-rchild; return firstNode(p-rchild); } void inOrderTraverseThread(ThreadTree root) { ThreadNode *p firstNode(root); while (p ! NULL) { printf(%d , p-data); p nextNode(p); } }这个遍历全程没有函数递归纯粹靠指针移动效率是 O(n)空间 O(1)。写线索化时有个低级错误特别容易犯把全局变量pre忘初始化或者每次调用inThread前不重置pre为 NULL。因为全局变量会保留上一次调用的值第二次线索化一棵新树时pre 指向旧树节点线索就全乱了。实操中的解决办法是要么把 pre 作为参数传递要么每次调用前公开招聘pre NULL。值得一提的是线索二叉树也有前序线索化和后序线索化的版本但中序线索化最常用、最容易考因为中序的应用最贴合 BST 的有序性需求。先透彻理解了中序其他版本只是把递归顺序换一换。7. 运行时错误排查实录写二叉树程序为什么总崩溃7.1 空指针与野指针九成崩溃的源头写二叉树报“运行时错误”十个里九个是访问了 NULL 指针或不存在的内存地址。典型的场景是建树时某个节点的孩子没有初始化直接在遍历里访问root-lchild-data可这时候root-lchild是 NULL 或者是一块随机地址程序就炸了。排查时有个笨但管用的办法在代码里频繁判断if (x NULL) { printf(这里为空\n); return; }先定位到第一次崩溃的位置再往回调。然后回头看节点创建时有没有把左右指针显式初始化成 NULL。很多“诡异”的崩溃其实只是因为malloc出来的内存是脏数据没有归零就拿来当指针用。7.2 递归越界忘记终止条件就是自杀递归算法如果没有正确处理空子树分支会无限调用直到栈溢出。二叉树递归里终止条件一定放在函数最开头并且判定参数为 NULL。有的人喜欢写成if (root-lchild NULL) return;这个写法不是不行但会漏掉 root 本身为 NULL 的 repo。更离谱的写法是遍历函数里先输出再判空直接对 NULL 解引用。栈溢出触发时Linux 下你会看到 “Segmentation fault”Windows 下是 “0xC00000FD: Stack Overflow”。看到这种错误先检查递归终止条件再考虑树的规模是否过大导致递归深度死亡。7.3 内存管理malloc 和 free 的连环坑二叉树每创建一节点就 malloc 一次用完必须 free不然内存泄漏。但 free 之后还有个升级版问题野指针。看看这段错误示范BiTNode *p root-lchild; free(root-lchild); // 此时 p 指向的内存已释放但 p 本身还指在那里 // 后续 p-data 0; 就是访问已释放内存结果是未定义行为正确做法是 free 之后把对应指针置为 NULL。而且要注意“先摘链再 free”比如删除 BST 节点时我的代码里是先保存temp root-lchild再free(root)最后return temp这个顺序之间的依赖关系一步都不能错。7.4 排查工具与手段遇到顽固的运行时错误别靠肉眼干瞪眼。Linux/Mac 环境下用gdb直接跑崩溃程序bt命令能看到调用栈精确定位到哪一行崩的。Windows 下用 Visual Studio 调试器断点加在可能出错的行。还有一个很实用的技巧把你的二叉树打印出来。写一个printTree函数用缩进展示树形结构任何“树长得不对”的问题一眼就能看出来比如 “为什么我的排序结果不对” 往往是因为树根本就没建对。类比一下这就像做菜不知道哪里变味儿先把食材列表列出来比瞎猜靠谱得多。下面整理一个高频错误速查表按症状对号入座错误现象可能原因排查思路访问节点属性就崩溃指针未初始化 / 已释放检查 createNode 是否把 lchild/rchild 置 NULL程序无限递归直至栈溢出缺少判空终止条件在递归函数入口补if (root NULL) return;插入 BST 后树没有变化没有接收递归返回的新节点指针检查root-lchild insertBST(...)是否被漏掉中序线索遍历死循环pre 全局变量未重置每次线索化前把 pre 置 NULL删 BST 节点后中序序列乱序没处理双子节点情况用后继节点值替换待删节点再递归删除后继固定数组队列越界树节点数超过数组容量改用链式队列或动态扩容这个表里的问题我全都在学习中实际踩过尤其是第二条和第三条当时调试了快三个小时最后发现只是漏了一行代码。后来我给自己定了一个规矩所有递归树算法写完先检查三件事——判空了吗、返回值传了吗、共享状态idx、pre传对了吗。三句话能过滤掉绝大多数运行时崩溃。8. 几个偏冷但实用的细节心得多写一些树相关的代码后会发现一些非主流但真实好用的经验第一关于函数的命名习惯。createTree、buildTree、initTree看着差不多但团队协作时真的有讲究。我自己的习惯是“create”表示内存层面的创建“build”表示按照业务逻辑组装。翻看以前的代码大项目里命名混乱导致的浪费时间丝毫不比逻辑 bug 少。第二关于递归返回值的设计。树的递归函数大体分两类“不关心返回值”的遍历、打印、线索化和“需要返回值”的插入、删除、求高度。拿到需求先判断是哪种能省掉大量思考时间。插入 BST 如果不想用返回值可以改成传二级指针BiTree *root但这种写法对初学者不友好容易把代码绕晕我推荐先老老实实用返回值版本。第三画图是定位思路的最好工具。遇到复杂的删除操作或线索化先在纸上画出具体例子模拟指针变化再回来看代码。数据结构这东西编码是从抽象到具体调试是从具体回抽象纸上推演是唯一的桥梁。9. 这六讲二叉树到这里才算是真的入门写到这里“16二叉树6”这个系列的核心内容就算告一段落了。回想我自己学二叉树的经历前五讲都在积累概念这一讲把遍历、深度、BST、线索化、错误排查串起来之后才有一种“哦原来树是这么一回事”的贯通感。坦白说学二叉树最容易产生的错觉是“代码我都看懂了”。但看懂了和写得出来、调得出来完全是两回事。我建议拿到这篇笔记的读者不要光读一定亲手把代码敲一遍然后自己设计几个刁钻的测试用例——比如只输入有序序列测 BST 退化比如故意删一个双子节点比如连续线索化两棵树。给自己找麻烦才能避开别人可以轻轻放过的坑。最后分享一个小习惯我会在调试的时候把每个节点打一个唯一的编号打印进 data 的临时副本里这样画图和看输出都对得上号。时间久了你对“报错”这件事的恐惧感会慢慢消失因为几乎每个报错你都能预判原因。这也是数据结构训练带给人最大的红利——不是背会了哪棵树而是拥有了一种“程序崩了也不慌一步一步查”的稳定心态。