2010年408统考数据结构部分有一道题问的是n个结点的线索二叉树中线索的数目。这题就2分但当年很多人在B和C之间犹豫——因为不少同学只背了“线索二叉树把空指针指向前驱后继”这句话真到推导到底有多少空指针、哪些指针会变成线索时就开始含糊。今天把这题彻底拆开从概念到推导再到代码实现全套理一遍适合正在准备408考研数据结构部分的同学也适合复习到树这一章想把手上的易错点一次清干净的人。1. 真题原题回放与易错点分析1.1 题目原文与选项这道题的题干很简洁大意是一棵有n个结点的线索二叉树线索的数目是多少。选项是四个经典候选选项数值An-1BnCn1D2n正确答案是Cn1。别急着往下看先自己心里推一遍为什么不是n-1为什么也不是2n如果这一步你能立刻说清楚说明线索二叉树的基础是过关的如果说不清那这篇文章后面几个部分正好帮你把逻辑补起来。这道题看似只是在考一个结论但它的前置条件其实是两件事第一n个结点的二叉树一共有多少个指针域第二真实存在的父子关系指针占掉了多少个。这两件事搞明白答案就自己出来了。1.2 绝大多数人为什么选错我见过很多同学做这题第一反应是线索二叉树不就是把空指针变成线索嘛那线索数量不就是空指针数量这句话没问题但问到空指针数量是多少就开始发挥想象力了。常见的错误思路有三个。第一种选A的n-1。这类同学把二叉树当成了链表的某种扩展觉得n个结点连成一棵树边数是n-1线索好像也是沿着这些边走的所以选了n-1。这完全是把线索和边混在一起了。线索不是真实的父子关系它是“冗余”的导航信息数量不可能等于边数。第二种选B的n。这种直觉来自于“每个结点都有一个前驱或一个后继”的印象然后一拍脑袋觉得n个结点对应n条线索。但题目问的是所有线索的总数不是“每个结点贡献一条”这么简单。实际上大部分结点会贡献两条线索还有一些结点一条都不贡献具体要看指针空不空。第三种选D的2n。这思路是“每个结点有两个指针域全部变成线索所以是2n”。这又走向另一个极端。因为n个结点的树至少有n-1条边是靠指针域在维护的这些指针是真实的孩子指针不可能同时再当地线索用。所以这道题真正的考点是先把真实的n-1条边拿出来剩下的指针域才是可以被线索化利用的“空余资源”。把这个逻辑想通答案就不是背出来的而是推出来的。2. 线索二叉树在考什么前驱、后继与线索化2.1 一句话说清线索二叉树普通二叉树每个结点有两个指针域分别指向左孩子和右孩子。问题是很多结点并没有两个孩子甚至一个孩子都没有于是出现了大量空指针。线索二叉树的思路特别朴素这些空指针空着也是空着不如让它们指向遍历序列中的前驱或后继。比如中序遍历之后某个结点的前一个结点是谁、后一个结点是谁直接用空指针记下来下次找的时候就省事了。注意一个关键点不是所有空指针都必须变成线索。到底哪些空指针变成线索、变成指向谁的线索取决于你用的是中序、先序还是后序遍历规则。不同遍历方式下“前驱”和“后继”的具体含义完全不同。这个稍后我在第4部分详细对比。要让计算机知道一个指针到底是孩子指针还是线索指针每个结点还要加上两个标志位。一般定义是ltag为0表示lchild指向左孩子为1表示lchild指向前驱rtag为0表示rchild指向右孩子为1表示rchild指向后继。标志位不占多少空间但这是线索二叉树能正常工作的大前提。2.2 线索二叉树 vs 普通二叉树遍历普通二叉树的中序遍历一般靠递归或者手动维护栈。递归的代码很好看但每一次递归调用都在消耗系统栈树很深的时候这不是一个小开销。手动栈稍微可控一点但代码复杂度上来了而且空间复杂度还是O(n)。线索化之后中序遍历可以不借助栈。因为你走到任何一个结点如果想找它的后继只需要看rtag如果rtag是1那么rchild直接就是后继一步到位如果rtag是0说明有右子树那后继就是右子树中最左边的结点。整个过程不需要保存现场空间复杂度降到O(1)遍历速度也快很多。用一个生活化类比普通二叉树的递归遍历就像你在迷宫里边走边做记号走完还得沿记号退回来线索二叉树相当于迷宫的每个岔路口都挂了一个牌子直接告诉你“下一个该去哪”你只管一路往前走就行。不过线索化也不是没有代价。最大的代价是插入和删除很难。因为线索关系是动态的你插入一个新结点可能要改动前后好几个结点的线索指向。所以工程上线索二叉树一般用在“树建好了基本不动但需要频繁遍历查找”的场景而不是用来做频繁的动态修改。408真题目前对线索二叉树的考察也集中在概念、数量推导、特定遍历顺序下的前驱/后继判断上动态增删考得很少。3. 核心推导为什么空指针域是n1个3.1 指针域总数与边数的关系现在回到2010年这道真题的核心计算。一棵二叉树不管形状是什么样只要它有n个结点那么每个结点都有两个指针域左孩子指针和右孩子指针所以整棵树的指针域总数是2n。这2n个指针里有多少个真的指向了一个孩子结点注意一个事实二叉树中的每个非根结点都有且只有一个父结点而父结点指向它的那个指针就是一条真实的“边”。根的父结点是不存在的所以它没有从父结点来的那条边。因此n个结点的二叉树一共有n-1条边这n-1条边就对应着n-1个被实际使用的指针域。这里有一个考场上的快速理解方式你可以想象把所有结点一个一个“拎起来”除了根结点每个结点都是被一个指针“提着”的所以真实使用的指针数就是除了根以外的结点总数也就是n-1。那么空指针域就是总数减去使用掉的数量2n - (n-1) n 1这n1个空指针域就是线索化过程中可以变成线索的候选资源。也就是说线索的数量上限由这些空指针决定。线索二叉树在实现时确实会让这些空指针全部变成前驱或后继线索所以线索总数就是n1。3.2 严谨推导与特殊情况验证为了让自己信服可以拿很小的树做验证。n1时只有一个根结点没有边。两个指针域全是空的。线索化之后左指针指向前驱NULL右指针指向后继NULL线索数是2。n1也等于2对上了。n2时假设根结点只有左孩子。中序序列是“左孩子、根”。线索化之后左孩子没有左孩子所以它的左指针变成指向NULL的线索左孩子没有右孩子所以它的右指针变成指向根结点的线索根结点的左指针指向左孩子这是真实边根结点没有右孩子所以它的右指针变成指向NULL的线索。一共3条线索n1等于3也对上了。n3时如果是一棵满二叉树即根结点有左右两个孩子。中序序列是“左孩子、根、右孩子”。线索化后左孩子的左指针指向前驱NULL右指针指向根右孩子的左指针指向根右指针指向后继NULL根结点的两个指针都在使用中不产生线索。总共4条线索n1等于4还是对。这几个特例不只是在验证公式它们还揭示了一个规律线索主要产生在叶子结点和缺少某个孩子的结点上不是每个结点都均匀贡献。3.3 特值法在考场上的实际用法如果考场上你突然卡住了推导过程忘了怎么办我的建议是别硬想公式画一棵最小的、你自己能完全控制形状的树手工把它线索化数一数。实际考试中n等于1或者n等于2这种极端情况是完全可以用来排除选项的。比如你画一个只有根结点的树发现线索数是2。那A选项的0、B选项的1直接排除D选项的2n等于2看起来也满足这时候再画一棵n2的树验证一下C和D很快就能锁定n1。这个技巧看起来笨但非常稳。选择题没有过程分只有结果分能稳定地得到正确答案才是目的。我当年备考复习到这一章时特意把树、图这些结构里的“特殊值”——比如空树、单结点树、单支树——全部手推了一遍考试遇到相关选择题直接代入速度特别快正确率也有保障。另外还要提醒一下有的同学会把n0的情况也拿来验证但408树的题目默认n为正整数因为线索二叉树的定义里“空树”不是常规讨论对象。如果你自己复习时想验证边界条件记住n1才是最小可用样例。4. 三种线索二叉树的对比与代码模板4.1 中序、先序、后序线索化的差异线索二叉树不是只有一种根据遍历规则的不同分为中序线索二叉树、先序线索二叉树和后序线索二叉树。这三种之间最大的区别在于空指针到底指向“哪个遍历顺序”中的前驱和后继。类型空左指针指向空右指针指向找前驱找后继中序线索二叉树中序前驱中序后继容易容易先序线索二叉树先序前驱先序后继较麻烦需借助父结点容易后序线索二叉树后序前驱后序后继容易较麻烦需借助父结点为什么中序线索二叉树最常考因为中序遍历下左子树和右子树之间的顺序关系非常清晰一个结点的前驱要么是其左子树中最后一个被访问的结点要么就是它的某个祖先后继要么是其右子树中第一个被访问的结点要么也是某个祖先。这种关系最直观所以教材和真题对中序线索二叉树的倾斜度远高于另外两种。先序和后序线索二叉树没有这么“对称”。先序遍历中找后继相对好办因为根结点先访问后继通常是左孩子或右孩子但找前驱就比较头疼因为前驱可能是某个祖先想在O(1)时间内找到往往需要树的每个结点额外存一个指向父结点的指针。后序线索化则正好反过来找前驱容易找后继难。408历年对这块的考法主要集中在概念判断和遍历序列理解上。比如给你一棵中序线索二叉树让你判断某个结点的中序后继是谁或者问你后序线索二叉树中找后继为什么需要栈或者父结点指针。把上面对比表理解清楚这种题基本不会错。4.2 结点结构与中序线索化代码线索二叉树的结点定义在C语言里很常见。这里多出来的两个标志位是关键因为它们告诉遍历程序当前指针到底表示“孩子”还是“线索”。typedef struct ThreadNode { ElemType data; // 数据域 struct ThreadNode *lchild, *rchild; // 左右孩子指针 int ltag, rtag; // 0: 孩子指针, 1: 线索指针 } ThreadNode, *ThreadTree;中序线索化的核心做法是用递归遍历整个树在访问到当前结点的中序位置时判断它和上一个结点pre之间的线索关系。具体逻辑是如果当前结点左孩子为空就把左孩子指向pre同时把ltag置为1如果pre的右孩子为空就把pre的右孩子指向当前结点同时把pre的rtag置为1然后更新pre为当前结点。这个“当前结点左孩子为空就指prepre右孩子为空就指当前结点”的操作我建议不要死记而是画一棵小树用一个辅助指针pre跟着中序遍历走一遍。你自己走一遍之后会发现其实就是在相邻结点之间补上一条“捷径”把所有空气泡都串起来。下面是一段完整的递归中序线索化代码void InThread(ThreadTree p, ThreadTree pre) { if (p NULL) { return; } InThread(p-lchild, pre); // 递归线索化左子树 if (p-lchild NULL) { // 左指针为空指向前驱 p-lchild pre; p-ltag 1; } if (pre ! NULL pre-rchild NULL) { pre-rchild p; // pre的右指针为空指向当前结点 pre-rtag 1; } pre p; // 更新pre为当前结点 InThread(p-rchild, pre); // 递归线索化右子树 } void CreateInThread(ThreadTree T) { ThreadTree pre NULL; if (T ! NULL) { InThread(T, pre); pre-rchild NULL; // 处理最后一个结点的右线索 pre-rtag 1; } }注意代码最后几行为什么要有pre-rchild NULL; pre-rtag 1;因为中序遍历的最后一个结点它的右指针理论上一定为空但这只是“理论上”。在实际初始化时你不能保证它已经被正确置空所以必须手动处理否则最后一个结点的右线索状态可能是脏数据。4.3 遍历线索二叉树找前驱和后继线索二叉树最大的卖点就是找中序后继可以不走递归。在任何一个结点上判断rtag如果rtag是1说明右指针已经是线索直接返回rchild就是中序后继如果rtag是0说明结点有右子树那么中序后继是右子树中最左下角的那个结点。对应代码ThreadNode *FirstNode(ThreadNode *p) { while (p-ltag 0) { p p-lchild; } return p; } ThreadNode *NextNode(ThreadNode *p) { if (p-rtag 0) { return FirstNode(p-rchild); } else { return p-rchild; } }有了NextNode中序遍历整个线索二叉树就不需要栈了void InOrder(ThreadTree T) { if (T NULL) return; ThreadNode *p FirstNode(T); while (p ! NULL) { // 访问结点 p NextNode(p); } }这里有一个我自己备考时踩过的坑FirstNode函数里的判断条件是while (p-ltag 0)不是while (p-lchild ! NULL)。如果你用后者判断一旦遇到左指针指向线索的情况就会一头扎进死循环。所以线索二叉树的遍历代码所有判断都建议优先看ltag/rtag而不是直接看lchild/rchild是否为NULL。这个习惯不养好做代码题时很容易写错。找中序前驱也是类似对称的逻辑如果ltag等于1那么lchild直接就是前驱如果ltag等于0说明有左子树前驱是左子树中最右下角的结点。这部分代码我就不贴了建议自己写一遍比看十遍印象都深。5. 408真题考察规律与备考避坑5.1 线索二叉树在真题里的出题角度从408往年的真题来看线索二叉树这个知识点的出题角度大概是这几个方向。第一类概念题。直接考察线索二叉树的定义、空指针域数量、标志位含义。2010年的这道题就是典型代表。这类题不需要写代码但要求你对空指针域推导过程和三种线索二叉树的概念差异非常清楚。第二类序列推断题。给出一棵具体的二叉树要求判断线索化后某个结点的前驱或后继。这类题本质上是考你对三种遍历序列的熟悉程度再用线索的规则套进去。如果遍历序列都写不对那线索指向必然选错。第三类代码理解题。给你一段线索化的核心代码让你填空或者判断功能。这个我建议复习时把上面第4部分的代码自己默写两遍尤其是条件判断部分为什么用ltag/rtag而不是直接用指针判空一定要能讲出理由。第四类结合其他知识点。比如有些题会把线索二叉树和二叉排序树的查找结合起来问你线索化之后能不能加速查找。要注意的是线索化的作用是加速“遍历”时的前驱后继定位不是加速基于关键字的搜索。这个区别如果混淆看到那种“优化查找效率”的选项就会误选。5.2 三个最容易踩的坑第一个坑把“线索”和“空指针”完全划等号。严格说线索是用空指针实现的但线索是有方向性的区分前驱线索和后继线索。而且有真实孩子的指针永远不可能变成线索。所以我经常跟准备考试的朋友说空指针是线索的“材料”但一条指针只能承担一个角色要么是孩子指针要么是线索不可能既是孩子又是线索。第二个坑后序线索二叉树找后继时直接用rchild。后序线索结构中虽然rchild也可能存线索但一旦结点的rtag为0说明它有右子树其后继必须在子树或祖先那边才能找到。很多同学把中序找后继的那套逻辑直接搬到后序结果就出错了。第三个坑忽略空树和单结点树。平时自己刷题时代码也好、手推也好一定要先测空指针再测单结点然后才测普通树。我复习时手写过一段线索化代码一开始没处理pre NULL的情况测试单结点树直接空指针异常。这类问题在408机试或复试着上机时尤其致命因为数据里真的可能出现只有根结点的树。6. 考场实战技巧与复习建议6.1 做对这道题的最低知识清单如果你想在考场上稳定拿下2010这道题这样的分数最低要求是下面四件事知道n个结点共有2n个指针域知道n个结点的树有n-1条边知道线索是复用空指针域实现的会做n1和n2的快速验证。这四件事对应到做题流程上就是先算2n减n-1得到n1再用最小例子确认没有记反最后扫一眼选项选出答案。整个过程只要30秒左右比较稳。对于准备更充足的同学我建议把上面的清单再增加两条能够手写中序线索化核心代码且不查资料能够说明先序、中序、后序三种线索二叉树在找前驱/后继时各自的复杂度差异。这两条不仅是应对选择题也是复试面试时老师喜欢追问的点。还有一点经验是真题的难度不在于单题有多深而在于知识密度。线索二叉树本身不难但它和二叉树遍历、递归、栈、指针这些基础概念绑定在一起。一个地方模糊做题时就会被带偏。所以复习时别孤立地背“线索数n1”这个结论一定要把它放在二叉树的基本计算框架里理解。6.2 复习时的两个实用技巧第一个技巧画图推演。准备一沓草稿纸专门用来画各种形态的二叉树完全二叉树、单支树、随机树然后手动执行中序线索化。画的时候不要偷懒要把每个结点的ltag和rtag都标出来。这样画完三五棵树之后你会形成一种直觉叶子结点通常贡献两条线索只有一个孩子的结点贡献一条线索满结点不贡献线索。这种直觉对做选择题帮助极大。第二个技巧和代码题联动复习。408的大题里经常考二叉树的遍历而线索二叉树恰恰就是遍历的进阶版。你在复习代码题时可以顺手把普通的递归中序遍历改成线索化版本再把中序线索二叉树的非递归遍历也写一遍。这样一次复习同时覆盖了二叉树遍历、递归、指针操作、标志位思想效率远高于单独背结论。我个人建议把这道2010年的真题当成一个“支点”题。什么叫支点题就是通过把一道题彻底吃透连带着把一整块知识网的细节全部激活。线索二叉树这个概念从这一道选择题出发可以牵出二叉树存储结构、遍历序列、空指针数量、递归转非递归、代码实现等一系列考点。把这条线走通不只是拿到这2分而是让整个数据结构树这一章的知识框架都更扎实。