前阵子整理数据结构笔记把二叉树和线索二叉树从头到尾过了一遍。这东西讲真看的时候觉得挺简单不就是节点加指针嘛。可自己上手写 C 代码动不动就是运行时错误、死循环、莫名其妙的空指针访问。后来把几个关键点捋清楚才明白树的问题从来不在“怎么定义”而在“遍历顺序怎么控制”和“空指针怎么处理”。这篇文章就把我整理的内容、踩过的坑以及排查思路完整写出来适合刚学到二叉树、或者学完线索二叉树还不太会用代码实现的人参考。1. 先弄明白二叉树到底在解决什么问题1.1 为什么是二叉树而不是普通树很多教材会直接给定义二叉树是每个节点最多只有两个子节点的树结构。我当年看这个定义时心想那不就是树的一个特殊情况吗没错但把“最多两个分支”这个限制加上去之后整棵树的数学性质就变得非常规整。分支数被限制成两个一个节点就能区分明确的左右方向遍历时“先左后右”天然形成固定次序。普通多叉树虽然也能存数据但子节点数量不固定存储结构、查询逻辑都要复杂得多。实际工程里多叉树经常会用“左孩子右兄弟”的方式转换成二叉树来处理比如比赛中的树的存储、操作系统的文件系统目录处理都能看到这个转换思路。可以说学透二叉树是理解更复杂树结构红黑树、B树、哈夫曼树的基石。从 C 实现角度说两个子节点也意味着每个节点最多两个孩子指针内存布局和空指针判断都非常清晰。拿数组、链表来对比数组插入删除麻烦链表随机访问麻烦而二叉树在“查找增删”之间取得了一种平衡这也是之后二叉搜索树、AVL 树能高效工作的原因。1.2 学二叉树必须背的几个性质和公式这部分看起来是纯理论但写代码时真的用得上尤其是判断递归边界和计算复杂度的时候。第一第 i 层最多有 2^(i-1) 个节点根节点算第 1 层。这意味着高度为 h 的二叉树最多能容纳 2^h - 1 个节点。写递归时“高度为 0”和“高度为 1”的情况经常要区分这个公式能帮你验证递归的返回值对不对。第二任意一棵二叉树如果叶子节点数是 n0度为 2 的节点数是 n2那么一定有 n0 n2 1。这个定理的证明思路很简单边数和节点数的关系。很多遍历算法的边界条件、二叉树的构建题都能从它推导出来。第三对于 n 个节点的完全二叉树深度是 floor(log2 n) 1。这句话在做“判断完全二叉树”的层序遍历题时特别重要你会在代码里频繁检查“当前层是不是满的”。第四线索二叉树理论里最关键的一个数字n 个节点的二叉链表一共有 2n 个指针域真正被用来指向孩子节点的只有 n-1 个剩下 n1 个指针域都是空指针。这就是后面线索化的空间出发点不理解这个数你就不知道为什么线索化有东西可做。这些性质建议不要死记而是自己画一棵树数一下节点、指指针推一遍。当年我就是画了一个三层满二叉树手动数空指针数到 4才真正理解 n1 这个结论。2. 二叉树在 C 里的存储方式结构选对后面全顺2.1 顺序存储适合完全二叉树不能无脑用顺序存储其实是用数组存二叉树。下标为 i 的节点它的左孩子下标是 2i1如果从 0 开始右孩子是 2i2父节点是 (i-1)/2。这个映射关系让完全二叉树用数组存非常紧凑不需要额外指针。但是普通二叉树用数组存就有大问题了。比如一个只有右链的退化树n 个节点按顺序映射到数组里需要约 2^n 个位置空间直接爆炸。我在写堆排序时用过顺序存储那没问题因为堆本身是完全二叉树。可是一旦树的形状不规则立刻要切回链式存储。所以选择顺序存储的第一判断标准就是这棵树是不是完全二叉树泛化使用很容易把空间复杂度搞崩。C 里用数组存二叉树的代码非常简单常见的就是 vector 访问子节点就是 vector[2*i1]。但使用时要注意下标越界这是初学者最容易犯的错。很多“运行时错误”其实就是数组下标访问了不存在的左孩子位置。2.2 链式存储节点的 C 定义与内存细节链式存储就是每个节点用结构体定义左右孩子指针指过去是学习阶段最常用的方式。一个经典的 C 定义是这样struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };这里有两个细节值得说。第一一定要写构造函数初始化 left 和 right否则它们是未定义的值访问时就会出问题。我见过太多报错案例节点创建出来之后左右指针没初始化直接 while(cur-left) 遍历结果读了一个随机地址要么段错误要么跑飞。第二如果要写更复杂的功能可以给结构体加父节点指针 parent这在实现红黑树、并查集、回溯操作时很有用。但注意每加一个指针构建和销毁时都要额外维护不是越多越好。创建节点通常用 new销毁整个树时就要递归删除。这是 C 特有的麻烦void destroyTree(TreeNode* root) { if (root nullptr) return; destroyTree(root-left); destroyTree(root-right); delete root; }很多初学者只 new 不 delete或者写了 delete 但是递归顺序错误导致内存泄漏。我自己的习惯是每写一个 new 的地方立刻确认对应的删除函数在哪里最外层调用者负责调用 destroyTree。不要想着用完再补代码一多补是补不回来的。2.3 构造一棵树的两种思路学习阶段经常需要手工构造测试树我一般用两种方式。一种是从数组反推。比如数组表示法 [1,2,3,null,4,5,6]按层序填充。写一个辅助函数TreeNode* buildTree(const vectorint nums) { if (nums.empty()) return nullptr; TreeNode* root new TreeNode(nums[0]); queueTreeNode* q; q.push(root); int i 1; while (!q.empty() i nums.size()) { TreeNode* cur q.front(); q.pop(); if (i nums.size() nums[i] ! INT_MAX) { cur-left new TreeNode(nums[i]); q.push(cur-left); } i; if (i nums.size() nums[i] ! INT_MAX) { cur-right new TreeNode(nums[i]); q.push(cur-right); } i; } return root; }这里我约定 INT_MAX 代表空节点。每次从队列取一个节点按层序给它挂上左和右然后把自己弹出继续处理下一层。这个函数我用了很久调试树的题目时直接传一个数组进去就能生成测试树非常方便。另一种方式是二叉搜索树的插入构建这个适合测试搜索类算法。边插入边调整即可但注意它构造出来的树形和插入顺序强相关顺序不好会退化成长链写题时务必小心。3. 遍历是二叉树的核心功底递归和非递归都得会3.1 递归遍历三行代码理解“根”的位置递归遍历是二叉树最直观的操作。先序、中序、后序的区别其实只是访问当前节点的时间点不同。以中序为例void inorder(TreeNode* root, vectorint res) { if (root nullptr) return; inorder(root-left, res); res.push_back(root-val); inorder(root-right, res); }先序就是把 push_back 放到递归左之前后序就是放到递归右之后。本质上一个节点被递归函数碰到的时机有三个进入时、左子树返回时、右子树返回时。你选择哪个时机记录节点值输出就是哪种遍历。我建议把这三个时刻完全背下来因为线索二叉树的访问顺序其实就是“按中序顺序找下一个节点”你必须对中序遍历的流程有肌肉记忆。3.2 非递归中序遍历显式栈模拟递归调用递归虽然好写但 C 里递归深度过大时会栈溢出所以面试和工程里经常要求非递归写法。中序非递归是用栈来模拟“一路向左”的过程vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* st; TreeNode* cur root; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); res.push_back(cur-val); cur cur-right; } return res; }这个过程可以这样理解每次先拼命往左走把沿途节点都压栈走到空就弹栈输出然后转去处理右子树。整个逻辑说起来简单但自己手写时容易漏掉“外层 while 条件包含 cur 不为空”这一点。一旦漏掉第一个节点是空树时就会直接跳过正确逻辑或者无法处理“右子树为空且栈不为空”的情况。3.3 非递归先序和后序写起来差别很大先序非递归有一种很顺的写法先把根入栈每次弹出一个节点先压右孩子再压左孩子。因为栈是后进先出先压右孩子就能保证左孩子先弹出从而得到“根左右”的输出顺序。后序非递归最直观的是用两个栈或者给每个节点打上一个“访问标志”。我常用的双栈法思路是先用一个栈做“根右左”的遍历再把结果反转得到“左右根”。具体代码vectorint postorderTraversal(TreeNode* root) { vectorint res; if (root nullptr) return res; stackTreeNode* st; stackTreeNode* out; st.push(root); while (!st.empty()) { TreeNode* cur st.top(); st.pop(); out.push(cur); if (cur-left) st.push(cur-left); if (cur-right) st.push(cur-right); } while (!out.empty()) { res.push_back(out.top()-val); out.pop(); } return res; }注意这里先压 left 还是先压 right 和先序正好相反因为我们要在 out 栈里营造出“先根后右再左”的顺序弹出时自然就是“左右根”。这个方法好理解面试时容易讲清楚。还有一个只用一个栈、用 lastVisited 记录前一次访问节点的写法空间更省但边界判断较多我建议先把双栈法写熟。3.4 层序遍历BFS 的模板层序遍历就是一层一层从左往右访问用队列非常自然vectorvectorint levelOrder(TreeNode* root) { vectorvectorint res; if (root nullptr) return res; queueTreeNode* q; q.push(root); while (!q.empty()) { int sz q.size(); vectorint level; for (int i 0; i sz; i) { TreeNode* cur q.front(); q.pop(); level.push_back(cur-val); if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } res.push_back(level); } return res; }这里的核心是每次进入 while 循环先取一次 q.size()这个值代表当前层的节点数。处理完这一层之后队列里剩下的正好是下一层全部节点。如果不先缓存 sz而是直接 while(!q.empty())层与层的边界就搞混了输出会变成全部节点的平铺。这一行缓存代码就是层序遍历和普通 BFS 的区别点。4. 线索二叉树把浪费的空指针捡回来4.1 为什么需要线索化先数一数空指针前面提到n 个节点的二叉链表有 n1 个空指针。这些空指针本来存放 nullptr在内存上没有任何信息量。线索二叉树的思路就是把这些空指针利用起来让它们分别指向遍历序列中的前驱或后继节点。以中序线索二叉树为例一个节点的左孩子为空时就让左指针指向它的“中序前驱”右孩子为空时就让右指针指向它的“中序后继”。这样遍历时就不需要递归或栈顺着线索一路走就行时间复杂度和递归一样是 O(n)但空间复杂度在某些场景下更优。这怎么理解普通中序遍历需要栈来保存回溯信息线索树把回溯信息直接存在空指针里相当于用空间换时间里的“空间”从栈变量变成了树自身的存储空间。要说明的一点是线索化并没有“增加”存储只是重新利用了原本闲置的空指针。4.2 中序线索化的 C 实现细节线索化之后指针的语义变了所以节点里需要额外两个标志位表示左/右指针到底指向孩子还是前驱/后继。struct ThreadNode { int val; ThreadNode *left; ThreadNode *right; bool lTag; // false 表示 left 指向左孩子true 表示 left 指向前驱 bool rTag; // false 表示 right 指向右孩子true 表示 right 指向后继 ThreadNode(int x) : val(x), left(nullptr), right(nullptr), lTag(false), rTag(false) {} };中序线索化一般通过中序遍历完成。用一个 pre 指针记录上一个访问的节点当前节点 p 访问时做两件事p 的左孩子为空就让它指向上一个节点 prepre 的右孩子为空就让 pre 的右指针指向 p。递归代码void inThread(ThreadNode* p, ThreadNode* pre) { if (p nullptr) return; inThread(p-left, pre); if (p-left nullptr) { p-lTag true; p-left pre; } if (pre ! nullptr pre-right nullptr) { pre-rTag true; pre-right p; } pre p; inThread(p-right, pre); }这里最容易错的是 pre 必须用引用传递。如果不加引用递归返回上一层时 pre 还是旧值线索链就断了。还有一个非常隐蔽的坑判断左孩子是否为空的语句必须放在修改 lTag 之前因为线索化之后 p-left 可能被改成前驱如果你下次递归时误把它当左孩子继续访问就会陷入死循环。线程化结束后还要给树加一个头节点把整棵树的第一个节点的前驱指向头节点最后一个节点的后继指向头节点头节点的左指针指向根节点。这个头节点主要是为了遍历和插入删除的边界统一初学者可以先不做头节点直接用空指针判断也能完成中序遍历。4.3 基于线索的中序遍历找“第一个”和“下一个”中序线索树遍历的关键是两个函数找以 p 为根的最左节点以及找 p 的中序后继。第一个是沿左指针一路走直到 lTag 为 true 为止说明左边已经到头了ThreadNode* firstNode(ThreadNode* p) { while (p-lTag false) { p p-left; } return p; }找后继则看右指针如果 rTag 为 true右指针直接就是后继如果 rTag 为 false说明右孩子存在那么真正的中序后继就是右子树的最左节点ThreadNode* nextNode(ThreadNode* p) { if (p-rTag true) { return p-right; } return firstNode(p-right); }整个中序遍历写成了一个 for 循环完全不依赖递归和栈void inOrderTraverse(ThreadNode* root) { ThreadNode* p firstNode(root); while (p ! nullptr) { visit(p); p nextNode(p); } }这个遍历过程我建议亲手在纸上画一棵小树把线索一个个画出来再走一遍。你会发现普通中序遍历要靠递归回溯的地方线索树直接通过后继指针跳过去了。这就是线索化真正的价值把递归的过程变成了链表式的线性扫描。4.4 前序和后序线索化的差异提醒很多教材重点讲中序线索化但前序和后序也存在。实现思路一样只是访问顺序不同递归里“当前节点访问位置”要从中序的中间换成先序或后序的位置。不过要注意前序线索化格式上容易后序线索化麻烦。特别后序遍历时右子树结束后要回到父节点而父节点的右指针如果已经被线索化掉了普通递归就无法回溯。所以后序线索化的实现里经常需要给节点额外增加 parent 指针否则线索化过程和遍历过程都会遇到无法回溯的情况。我个人建议学习阶段把中序线索化吃透就够了前序后序理解思想即可真要用到的时候再查资料也来得及。5. 写二叉树程序时的常见报错和排查方法5.1 为什么编译器不报错一运行就崩热搜里有一句“写二叉树程序时为什么总是报运行时错误”这问题我太有共鸣了。编译能过说明语法没问题运行崩溃多半是内存访问问题。二叉树程序最常见的运行时错误集中在几个方向。第一是空指针解引用。比如前序遍历写的 cur cur-left但 cur 已经为空了程序直接崩溃。第二是递归没有终止条件。如果递归函数忘了写 if (root nullptr) return无限递归会把调用栈打爆系统直接抛出栈溢出异常。第三是悬空指针。树的某个节点被 delete 了但其他地方还有指针指向它访问时读的是无效内存。这三种错误还有一个共同难点程序可能不是立刻崩而是运行几十次、数据变多时才崩。我在学的时候经常遇到“本地小数据好好的换了大一点的数据就 status access violation”的情况其实就是某个空指针路径没处理到。5.2 高频 Bug 对照表下面这张表是我自己排查错误时经常对照的也推荐给你。现象常见原因排查思路运行崩溃报错包含 access violation访问了已释放或未初始化的内存检查所有 new 出来的节点是否都有初始化检查 delete 之后是否还保留指针递归函数栈溢出缺少递归终止条件或树链过长在函数入口打印输入指针看是否有 nullptr 进入非递归转用栈改写线索遍历进入死循环线索化时左/右指针被改成前驱后继后又被当成孩子访问检查 lTag/rTag 的判断是否在指针前递归线索化时必须先判断 Tag输出顺序不对递归位置放错用“访问时机”来检查push_back 是在左调用之前、之后还是在右调用之后树的节点漏构建buildTree 时数组越界构建函数里循环条件加 i nums.size() 双重判断还有一个特别常见的 C 特有坑在头文件或全局作用域里定义了 TreeNode 结构体但不同 .cpp 文件里对结构体大小理解不一致也可能导致运行时错误。学习阶段一般单文件写问题不大如果是多文件工程记得结构体定义放到同一个头文件里所有 cpp 包含同一个定义。5.3 我用过的几个实用调试手段排查树的问题不要靠肉眼硬看几百行代码我一般按这个顺序来。先把“打印整棵树”的函数写好。最简单的是打印中序遍历结果如果中序是升序的说明树结构基本正确。但树形结构光靠遍历序列看不清楚我习惯写一个按层输出的调试函数把每层节点输出成一行空节点用 # 占位。这样能直观看到树的形状判断左右子节点是否挂对位置。然后是使用断点配合条件判断。在 VSCode 配置好 C 调试环境后可以在递归函数入口处判断某个特定节点值时断住比如 val 5 的时候停下来看一下当前的 left、right、lTag、rTag 是什么。这种方式排查线索化特别有效。单靠 print 输出容易把线索链上的值刷屏刷得眼花缭乱断点可以定点查看关键节点。最后是缩小数据规模。任何树逻辑错误先把它放在一棵只有三个节点的最小二叉树上测试根节点只有左孩子、只有右孩子、左右都有。跑通了再扩展到五节点、七节点。很多错误在小数据下就会现原形这比一上来调试一颗随机大树轻松得多。6. 最后分享几点我自己学习后的体会大概是第三遍整理二叉树之后我才真正意识到学二叉树不是一个“记住代码”的过程而是要把三个层面的东西打通。第一层是数学性质比如空指针数量、层数节点个数关系这些决定了算法的边界。第二层是递归思想一棵树的问题一定能拆成左子树和右子树的同构问题递归函数名不用变只管左右。第三层才是 C 的具体写法包括指针初始化、内存释放、Tag 标志的维护。写线索二叉树的时候我踩过最大的坑就是“先写了遍历代码才想起来改节点定义”。结果原来的 left/right 语义全变了所有遍历代码都得重写。后来我学乖了只要开头确定要写线索化节点定义里立刻加上 lTag 和 rTag哪怕暂不使用也不删。结构体里多两个布尔变量成本几乎为零后面的修改量却能省下一大半。还有一个经验一定要自己手写一棵树并完成全部线索化不要去抄网上的完整代码。抄代码的结局通常是你以为自己会了一旦 Tag 判断顺序稍微变了立刻傻眼。纸上画一遍再用代码实现再对照画出来的线索图走一遍遍历过程这个流程走下来线索二叉树才算真正是你的了。如果你是在刷题或者准备面试我建议二叉树部分集中练三个题型递归遍历与分治、非递归遍历用栈、层序遍历用队列。这三个题型吃透后遇到对称二叉树、最大深度、路径总和、树的序列化这些题你会发现它们全部是遍历模式的变种。线索二叉树在面试里考得不算多但它非常能检验你对“遍历序列中的前驱后继”理解到位没有。能把中序线索化写明白说明你是真的理解了中序遍历而不是只会背代码。