软考软件设计师上午的选择题里数据结构一直是必考模块而二叉树在其中占比又特别高。我备考和帮人备考时最明显的感觉是这块内容不难但很碎——今天问遍历序列明天问平衡因子后天问哈夫曼编码。很多同学卡在及格线附近往往就是树这一块有两三个考点没有真正吃透。这篇文章把我认为最核心的几组知识点串起来讲包括形态性质、遍历与还原、二叉排序树和平衡树、哈夫曼树、线索二叉树以及树森林转换目标是让你拿到一套能直接套用的做题方法考前两三天也能快速过一遍。1. 二叉树形态与性质先把送分题捡起来1.1 二叉树不是每个节点最多有两个孩子这么简单软考上午题特别喜欢在一道题里同时考二叉树的定义和性质。你要先记住一个容易被忽略的点二叉树不是简单的度为2的树它强调每个节点最多只有两个孩子并且左右子树有严格次序交换左右子树后就是另一棵二叉树了。这个区分在判断题里出现过很多次。接着就是两条高频性质几乎是每年都会露面的那种二叉树第 i 层最多有 2^(i-1) 个节点。因为每往下一层节点数最多翻倍从1开始第 i 层就是 2^(i-1)。深度为 k 的二叉树最多有 2^k - 1 个节点k≥1。这就是把每一层的最大值加起来等比数列求和的结果。很多同学不明白为什么要单独记一条叶节点数等于度为2的节点数加1也就是 n0 n2 1。这个公式出现频率极高而且它可以用很直观的方式理解每产生一个度为2的节点就相当于多了一条从上面分叉下来的路整棵树的叶子就会比分叉点个数多1。做题时直接套公式就行不用自己去推。我随手举个例子一棵二叉树有11个度为2的节点问它有多少个叶子。答案就是12不需要看树长什么样直接 n0 n2 1。这种题就是典型的送分题错了很可惜。1.2 完全二叉树与满二叉树的节点计算套路满二叉树比较好理解每一层都是满的。真正容易出错的是完全二叉树它的定义是最后一层可以不满但必须从左到右连续排列。软考喜欢拿完全二叉树的编号做文章。如果你用数组从1开始顺序存储一棵完全二叉树就会得到这几个结论编号为 i 的节点左孩子编号是 2i右孩子编号是 2i1它的父节点编号是 ⌊i/2⌋完全二叉树含 n 个节点时高度是 ⌊log₂n⌋ 1。我记得有一年考题问的是某完全二叉树共有700个节点问叶子节点数。这种题看着复杂其实有个快速结论完全二叉树中度为1的节点最多只有1个所以 n n0 n1 n2再结合 n0 n2 1就能解出来。700个节点的完全二叉树叶子数为350个度为1的节点为1个你可以用这个结果去倒推体验一下。再做一道常见的判断题完全二叉树一定是满二叉树吗反过来呢答案是满二叉树一定是完全二叉树但完全二叉树不一定是满二叉树。这个逻辑搞清楚之后很多选项都能一眼排除。1.3 顺序存储与链式存储的适用边界二叉树在计算机里有两种存储方式顺序存储和链式存储。顺序存储就是把节点按层序放进数组它最适合完全二叉树和满二叉树因为空间不浪费而且父子和兄弟关系都能用下标算出来。但如果是普通二叉树尤其是斜树顺序存储就非常浪费。比如一棵深度为5、实际只有5个节点的右斜树顺序存储可能要开 2^5 - 1 31 个位置中间全是空位。这种时候就应该用链式存储也就是二叉链表每个节点包含 data、left、right 三个部分。软考还经常考一个空链域数量的题n 个节点的二叉链表一共有 2n 个指针域其中只有 n-1 个指针指向孩子节点剩下的空链域就是 n1 个。这个结论简单就是每个节点除了根节点外都有一条来自父亲的边所以非空指针一定是 n-1。复习这个模块时我建议你心里始终绷一根弦性质公式一定要自己手动推一遍而不是死记。考试的时候一旦选项比较模糊理解公式的来龙去脉比硬背结论更稳。2. 遍历序列还原二叉树把递归切分练成肌肉记忆2.1 前序中序的还原原理与手推流程这是软考二叉树里最能体现会与不会差距的题型。给出一棵二叉树的前序遍历和中序遍历要求还原整棵树或者进一步求它的后序遍历。很多同学拿到题就蒙其实规律很简单前序遍历的第一个节点就是根而这个根在中序遍历里的位置恰好把左右子树分开。举个例子前序遍历是 ABDGHCEFI中序遍历是 GDHBAECFI。第一步前序第一个 A 是根。在中序遍历里找到 AA 左边是 GDHB右边是 ECFI所以左子树有4个节点右子树有4个节点。第二步回到前序遍历根 A 后面紧接着的4个节点 BDGH 属于左子树再往后4个 CEFI 属于右子树。第三步对左子树重复同样的逻辑前序 BDGH 中第一个 B 是左子树的根中序 GDHB 中 B 在最右边说明 B 只有左子树而没有右子树。继续分下去D 是 B 的左孩子G 和 H 分别是 D 的左右孩子。右边也这样推前序 CEFI 中 C 是右子树根中序 ECFI 中 C 的左边是 E、右边是 FI最后 F 是 I 的父节点。整棵树就还原出来了A / \ B C / / \ D E F / \ \ G H I看到没有整个过程就是前序定根中序分左右这是一个递归过程。考前我强烈建议你拿两三个例子亲手画一遍不要只是在脑子里想画一次之后速度会快很多。2.2 后序中序与层序中序的推法差异后序遍历和中序遍历的组合同样可以还原二叉树但规律要反过来用后序遍历的最后一个节点是根。还是用上面这棵树后序遍历是 GHDBEIFCA。第一步后序最后一个 A 是根。中序里 A 左边 GDHB 是左子树右边 ECFI 是右子树。第二步左子树的后序序列是 GHD B其中最后一个 B 是左子树的根中序 GDHB 里 B 在最右说明 B 没有右子树。再细分得到 D 为 B 的左孩子G、H 为 D 的左右孩子。第三步右子树的后序序列是 EIFC最后一个 C 是根中序 ECFI 表明 C 的左孩子是 E右子树由 F、I 构成而后序 EIFC 中 F 排在 I 前面且 F 是那一小段的根所以 I 是 F 的右孩子。层序中序相对少一些但也会考。层序遍历的第一个节点永远是根剩下的节点要依靠中序来分配左右。做题思路是不断在中序里找子树根。因为层序本来就是从上到下、从左到右输出的所以在给定中序后从层序靠前的节点开始逐个放入对应子树段就能还原。不过软考里层序的题目更多是选择题形式比如给你一棵树层序遍历的结果问中序或前序是什么。这时候你就需要理解层序与队列之间的关系。2.3 还原题里容易踩的两个坑第一个坑把前序和后序搞混。前序的第一个是根后序的最后一个才是根。这个错误在考场上特别常见尤其是连续做两三道序列题之后人容易机械套用。第二个坑认为前序后序也能唯一确定一棵二叉树。这是经典误区。前序 AB、后序 BA 的时候根是 A但 B 可能是 A 的左孩子也可能是 A 的右孩子没法确定。所以只有前序和后序无法唯一还原二叉树。软考曾在判断题里专门设过这个陷阱。第三个坑是还原完之后没有校验。我建议你每次还原出树之后快速用前序或中序走一遍看能不能和题目给定序列对上。这一步看起来多花十秒实际上能救回不少粗心分。3. 递归遍历与非递归遍历从背代码到画栈3.1 三种递归遍历为什么容易混淆二叉树的三种递归遍历本质区别只有访问根的时机前序是根左右中序是左根右后序是左右根。考概念的时候大家都会但一旦给出具体二叉树问遍历结果就容易出错。我用上面那棵树做一遍输出你对照感受前序A B D G H C E F I中序G D H B A E C F I后序G H D B E I F C A你会发现中序的结果特别重要因为二叉排序树的中序遍历一定是递增序列这是后面二叉树排序树章节的基石。考试里经常让考生根据一棵实际BST的插入过程来判断其中序遍历结果其实只要记住左根右递归定义就一定能写对。3.2 前序和中序非递归实现的栈模板很多资料一上来就放非递归代码把初学者吓跑。其实非递归无非就是自己维护一个栈模拟系统函数调用栈的进出过程。考场上虽然不一定让你写完整代码但理解它有助于你做序列输出题。前序非递归的模板特别简练根节点入栈 while 栈非空: 弹出 p访问 p 若 p 有右孩子右孩子入栈 若 p 有左孩子左孩子入栈为什么先压右孩子再压左孩子因为栈是后进先出先压右孩子左孩子就会先弹出这样访问顺序才是左子树在前、右子树在后。中序非递归稍微绕一点核心思想是一路向左走走到不能再走就弹栈访问然后再转向右子树p 根节点 while p 不为空或栈非空: while p 不为空: 栈.push(p) p p.left p 栈.pop() 访问 p p p.right你可以在纸上对树模拟几遍中序遍历的栈变化先是连续入栈 A、B、D、GG没有左孩子弹出G然后 p 指向 G 的右孩子为空所以继续弹D……整个过程就是递归展开的样子。3.3 后序与层序的考试出现形式后序非递归的模板比前序、中序都麻烦软考很少直接考代码但经常考下列哪个序列不可能是后序遍历的结果。这种题你要抓住后序遍历的核心特征左右根根一定是最后访问的。作为一个反例如果一个序列的结尾是一个明明在中序里靠中间的节点那就肯定不是后序。后序还有一种简便记忆法把前序遍历的根左右改成根右左然后整体倒过来就得到后序遍历。这个技巧在一些选择题里非常好用尤其是不用真正写出代码的时候。层序遍历则必须用队列根节点入队出队时访问然后把左右孩子依次入队。软考里有个很经典的延伸考点是判断一棵二叉树是否为完全二叉树用层序遍历的思路一旦遇到缺失孩子的情况后面就不允许再出现带孩子的节点否则就不是完全二叉树。这个判断方法比数节点个数更快值得记下来。4. 二叉排序树与平衡二叉树构建、删除、旋转的核心逻辑4.1 BST构建、查找效率的同一根主线二叉排序树也叫二叉查找树它的规则很直观左子树所有节点都小于根节点右子树所有节点都大于根节点。由此推出一个最常用的结论——中序遍历BST得到的是递增序列。这个结论在软考里几乎年年出现要么直接考输出要么隐藏在查找逻辑里。构树的过程就是不断比较从根开始比当前节点小就走左大就走右直到找到空位置插入。比如依次插入 50、30、80、20、40、90、35、45构建出来的BST就是下面这样50 / \ 30 80 / \ \ 20 40 90 / \ 35 45这里我想多说一句查找效率的问题。BST查找的平均比较次数等于查找路径上的节点数因此树越胖越平衡效率越高。如果一个BST退化成一条链比如插入序列已经是完全有序的 10、20、30、40、50那查找复杂度就是 O(n)和线性表没有区别。软考经常拿这个说事问你二叉排序树一定能提高查找效率吗答案是否定的关键看树的形态。成功查找时的平均查找长度 ASL 是软考实打实的计算点。以上面那棵树为例各节点层数分别是 1、2、2、3、3、3、4、4加起来22除以节点数8得到ASL成功为2.75。考题里如果给你一棵现成的BST让你算ASL你只需要按层统计节点个数就够了。4.2 AVL四态旋转的分类与判断平衡二叉树AVL是在BST基础上增加了平衡约束任意节点的左右子树高度差不超过1。高度差也就是左子树高度减右子树高度叫平衡因子取值只可能是 -1、0、1。插入节点后如果某个节点的平衡因子绝对值变成2就要旋转调整。旋转按失衡的两个方向分成四类类型典型形态调整方式LL失衡节点的左子树的左子树插入对失衡节点做右旋RR失衡节点的右子树的右子树插入对失衡节点做左旋LR失衡节点的左子树的右子树插入先对左孩子左旋再对失衡节点右旋RL失衡节点的右子树的左子树插入先对右孩子右旋再对失衡节点左旋光记这四类名称还不够你得会判断。我拿一个简单序列举例依次插入 15、20、12、18、10、8。插入前五个节点时树一直保持平衡直到插入8。此时节点12的左子树下是10再往下是8左子树高度变2而右子树为空所以12的平衡因子是2需要调整。再判断插入方向12的左孩子是10而8是10的左孩子典型LL型所以对12做一次右旋。调整后10成为这个子树的根8和12分别是它的左右孩子最终整棵树依然平衡。做题时最容易错的是LR和RL。核心做法是先把连续下降的那条路径找出来如果路径先左后右就是LR先右后左就是RL。旋转时不要去想复杂的结构只需要记住LR要两次旋转并且第一步的旋转点是失衡节点的孩子不是失衡节点本身。4.3 平均查找长度的考场速算AVL经常和ASL结合出题。因为平衡树的高度较低成功查找的ASL通常接近 log 级别。不过考场给的树一般很小直接按层数累加就行。失败查找的ASL偶尔也会考。你需要知道失败查找比较次数等于落入外部节点时经过的内部节点数这等于把树的所有空指针位置看作外部节点然后逐层统计。这类题只要作图的时候把空孩子位置补成虚线方块计算就一目了然。我在备考时的一个体会是BST的删除规则必须牢固掌握因为软考有时候会把删除和插入混在一起考。删除分三种情况叶子节点直接删只有一个孩子就用孩子顶上来有两个孩子时通常用左子树的最大节点或者右子树的最小节点来替换被删节点然后再删掉那个用于替换的节点。记住左子树最大这个方向就够了因为这样替换后二叉排序树性质依然保持。5. 哈夫曼树和哈夫曼编码计算WPL的快捷方法5.1 构造规则与WPL的两种算法哈夫曼树也叫最优二叉树它的核心指标是带权路径长度 WPL也就是所有叶子的权值乘以路径长度的总和。构造算法本身不难一句话每次从集合里取出两个权值最小的节点合并成一个新节点新节点的权值就是两者之和再放回集合不断重复直到只剩一个根。我用经典权值集合 2、3、4、7 来演示取出2和3合并得5集合变为4、5、7取出4和5合并得9集合变为7、9取出7和9合并得16构造完成。最终树中7的路径长度是14的路径长度是22和3的路径长度都是3所以 WPL 7×1 4×2 2×3 3×3 30。这里我要推荐一个考场上的快捷算法不需要计算每个叶子深度再相乘只需要把每次合并产生的新权值再次累加。上面三步产生的中间权值是5、9、16加起来也是30。道理很简单每次合并一次相当于被合并的权值整体向上走了一层累加的中间权值正好等于所有叶子权值与深度乘积的总和。用这个办法做题速度至少快一倍。5.2 编码不唯一但WPL唯一的理解哈夫曼编码就是在哈夫曼树上约定左分支为0、右分支为1从根到叶子的路径串起来就是该叶子的编码。上面例子里如果规定左0右1一种可能的编码是7 → 04 → 102 → 1103 → 111每个编码都不是另一个编码的前缀这就是前缀码解码时不会产生歧义。压缩效果就体现在高频字符用短码、低频字符用长码。考试会问某字符集的哈夫曼编码长度之和是多少本质上还是在算WPL只不过把权值看成出现次数。很多同学会纠结是不是只有一棵特定的树才最优不是。当有相同权值存在或者合并顺序不同时树的结构可以不一样编码方案也不唯一但所有方案得到的最小WPL是一样的。软考判断题特别喜欢考哈夫曼树唯一吗你要能马上反应过来不唯一。5.3 高频陷阱题汇总哈夫曼树有几个隐藏结论选择题直接拿来用很方便哈夫曼树中不存在度为1的节点每个内部节点都有两个孩子。有 n 个叶子节点的哈夫曼树总的节点数是 2n-1。权值越大的叶子越靠近根路径越短。哈夫曼编码是前缀码也是可变长编码。有一种题目会反过来问给定编码总长度和各个频率求某一字符的编码长度。这时候你可以先构造完整的哈夫曼树再数对应叶子的深度。还有一种是要求你判断某一组编码是否能作为哈夫曼编码。除了看它是不是前缀码外还要注意哈夫曼编码对应的树必须是无单字节乏力的满二叉树结构也就是每个非叶子都恰好有两个孩子。只要不满足选项就是错的。另外构造时如果遇到权值相同的节点选择不同会影响树的形状但只要合并策略正确WPL依然最优。做题时不必为了标准答案纠结。6. 线索二叉树与树森林转换冷门考点的快速记忆6.1 线索二叉树的标志位和后继判定线索二叉树看起来冷门但软考真的会考而且一旦考到就是不折不扣的送分题因为题型很固定。它解决的问题是普通二叉树在遍历时要知道某个节点的前驱和后继必须重新遍历一遍很麻烦。于是我们把节点的空指针利用起来让左空指针指向前驱右空指针指向后继。关键在标志位。每个节点增加两个标记 ltag 和 rtag0表示指针指向孩子1表示指针指向前驱或后继。你必须记住这一点因为它决定了指针的语义。考试最常见的考法是给一棵中序线索二叉树问某个节点在中序遍历中的后继是谁。判断规则只有一条如果该节点的右指针不是线索也就是 rtag0那么后继是它右子树的最左下节点如果右指针是线索rtag1那么右指针直接指向的后继节点就是答案。举个例子前面那棵树的中序遍历是 GDHBAECFI。节点D有右子树右孩子是HH没有左孩子所以D的中序后继是H节点E没有右孩子它的右指针被线索指到它的中序后继F。这类题画图时线索线都是虚线看到虚线就要想到这代表前驱或后继而不是孩子。6.2 树转二叉树左孩子右兄弟的映射表树和二叉树之间的转换软考从来不考具体画图而是考遍历对应关系。树转二叉树的核心规则叫左孩子右兄弟第一个孩子保留在左指针其他孩子依次作为上一个孩子的右孩子这样一棵多叉树就变成了二叉树。这里最容易错的是遍历对应关系我整理成了固定表树或森林的遍历方式对应二叉树的遍历方式树的先根遍历二叉树的先序遍历树的后根遍历二叉树的中序遍历森林的先序遍历二叉树的先序遍历森林的中序遍历二叉树的中序遍历注意树的后根遍历不是对应二叉树的后序遍历而是对应二叉树的中序遍历。这个反直觉的结论就是考题的重灾区一定要单独强化记一下。我自己当时备考就栽过一次后来再也没错。6.3 森林转二叉树的链表特征森林转换成二叉树可以理解为先把每棵树都转成二叉树再把后续每棵树的根作为前一棵树根的右孩子串起来。所以森林转出来的二叉树根节点一定没有左孩子以外的问题不对根节点一定有左孩子除非第一棵树根本身没有孩子。更实用的结论是最终二叉树根节点的右链上有多少个节点就代表原森林里有多少棵树。因为右链串起来的都是兄弟树。举个例子如果森林由3棵树组成转换后二叉树的根沿着右指针一直走一定能经过另外两个树的根。做题遇到森林F对应的二叉树根节点右子树为空说明什么这类题目答案就是原森林只有一棵树。这些结论整体逻辑是一致的不要单独背理解了根连接兄弟树之后顺理成章就能写出来。7. 考前复习路线与易错清单7.1 知识依赖顺序与时间预算备考二叉树模块我不建议按教材顺序从头到尾啃而是按照依赖关系安排顺序。我自己的复习顺序是这样的先花半天搞定形态和性质n0 n2 1、完全二叉树计算、顺序存储与链式存储再用一天主攻遍历递归遍历、非递归栈过程、序列还原。这一块建议多画图接着用一天处理二叉排序树和平衡树构建、删除、平衡因子、旋转哈夫曼树单独用半天重点是WPL快速算法和前缀码判断线索二叉树和树森林转换放在最后半天因为它们和其他章节的关联度低背清楚两个表格就行。如果你整体复习时间只剩两天那就压缩第一步和第五步把大部分时间给遍历和BST/AVL因为真正的大分值题目集中在这两块。7.2 我的踩坑记录与应试技巧写到这里我想分享几个实战中特别容易踩的点。第一做题习惯。还原二叉树时我喜欢用简单的括号表示法先草稿比如 A(B(D(G,H),),C(E,F(,I)))写起来快不占地方。这种简写方式让我在考场节省了不少时间你不妨也试试。第二判断AVL旋转方向时不要只盯着失衡节点看而要看插入点相对于失衡节点到底在左左、左右、右左还是右右。先找失衡节点再看它的孩子方向最后看插入点方向三步固定不动。第三算哈夫曼WPL时如果对中间累加算法不放心就按叶子深度相乘来验算一遍。两道算法结果一致才敢往答题卡上填。第四完全二叉树判断用层序遍历不要数个数。层序遍历过程中一旦遇到一个节点缺少左孩子或右孩子后面所有节点都必须是没有孩子的叶子否则就不是完全二叉树。最后再提醒一句复习到最后阶段把那些最容易被绕的短句反复过几遍——前序第一个是根后序最后一个是根树的后根遍历对应二叉树的中序遍历哈夫曼树无度为1的节点中序线索二叉树中右指针为空时指向后继节点。这些句子在考场上一眼能判断对错干扰选项基本就废掉了。二叉树这一块拿稳分上午考试就能踏实很多。