考研 408 的数据结构部分“树”这一章是选择题的绝对大户。很多同学把重心放在二叉排序树、AVL、哈夫曼树这些复杂考点上结果遇到一类“给遍历序列数无右孩子结点”的题目反而容易懵。2011 年统考第 6 题就是典型代表它问的是一棵二叉树里无右孩子结点有几个。题目看似是计算实际考的是“由遍历序列还原二叉树”的基本功以及你对结点孩子方向的理解是否到位。这篇文章会从考点定位讲起逐步拆解前序中序还原二叉树的通用方法再用完整例题带你手算一遍最后给出 C 语言和 Python 的可运行代码帮你把这 2 分稳稳拿下。1. 考点定位408 为什么要考“无右孩子结点”1.1 题目到底在考什么2011 年第 6 题给出的信息通常是二叉树的遍历序列然后问这棵树中无右孩子结点的个数。这类题表面在考“数数”实际上内在的考点链条是能否根据前序或后序遍历序列和中序遍历序列唯一确定一棵二叉树。能否正确画出还原后的二叉树结构。能否理解“无右孩子结点”这个概念并准确遍历树中的每个结点完成统计。这三点环环相扣。很多同学不是不会遍历而是不会“逆向还原”或者忽略了“只有左孩子、没有右孩子”的结点也应该被统计进去。1.2 为什么这个考点容易丢分丢分的原因一般有两种还原过程不熟练前序中序还原二叉树核心是“找根、切中序、分左右”。如果前序序列中的子树区间切分错误整棵树就画错了。概念边界模糊“无右孩子”不等于“叶子结点”。叶子结点一定无右孩子但只有左孩子、右孩子为空的非叶子结点同样属于“无右孩子结点”。这一点在考试中非常容易漏掉。所以这篇文章的功能不只是讲一道题而是把一类题的解题通法给你梳理清楚。2. 前置知识二叉树的三种遍历与“无右孩子”的定义2.1 前序、中序、后序遍历先快速回顾一下二叉树的三种深度优先遍历方式。这里有一个简单的二叉树A / \ B C / \ D E前序遍历根 → 左 → 右结果为A B D C E。中序遍历左 → 根 → 右结果为D B A C E。后序遍历左 → 右 → 根结果为D B E C A。408 真题里最常给的是“前序 中序”或“后序 中序”因为这两种组合可以唯一确定一棵二叉树。原因很简单前序序列的第一个结点一定是根后序序列的最后一个结点一定是根。中序序列中根结点把左右子树的中序序列分成了左右两部分。通过左右子树的中序序列长度可以反推前序或后序序列中左右子树的范围从而递归还原整棵树。如果只给前序和后序而没有中序一般无法唯一确定二叉树因为单孩子结点无法区分是左孩子还是右孩子。2.2 无右孩子结点指的是什么一个结点的“右孩子”就是该结点通过右指针指向的结点。判断一个结点是否无右孩子只需要看它的 right 指针或右子树是否为空。需要特别注意三类情况叶子结点左右孩子都为空当然也无右孩子。只有左孩子的结点这种结点右指针为空属于无右孩子结点。只有右孩子的结点这种结点有右孩子不属于。所以无右孩子结点的集合 叶子结点集合 ∪ 只有左孩子的结点集合。2.3 由遍历序列还原二叉树的基本原理以前序 中序为例还原的基本步骤可以总结为取前序序列第一个元素作为当前子树的根。在中序序列中找到该根的位置根左边是左子树的中序序列右边是右子树的中序序列。根据左子树中序序列的长度在前序序列中划分出左子树和右子树的前序序列。对左右子树分别递归执行上述过程。整个过程可以用一张表来辅助手算避免在草稿纸上画乱。3. 手算通法从前序 中序还原二叉树3.1 通用步骤假设前序遍历序列为 pre中序遍历序列为 ino当前处理的区间为pre 区间[preL, preR]ino 区间[inL, inR]执行以下步骤步骤操作说明1取 pre[preL] 作为当前根结点前序第一个元素一定是根2在 ino 中从 inL 到 inR 找到根的位置 k根把中序分成左右子树3计算左子树结点数 leftLen k - inL用于切分前序区间4左子树的前序区间为 [preL1, preLleftLen]中序区间为 [inL, k-1]5右子树的前序区间为 [preLleftLen1, preR]中序区间为 [k1, inR]6对左右子树递归执行上述过程直到区间为空这个模板也对应着后面代码实现的递归参数考试手算时把它写在草稿纸上能减少出错。3.2 典型例题逐步还原下面用一道与 2011 年第 6 题同考法的题目来演示完整过程。已知某二叉树前序遍历序列A B D G C E F中序遍历序列D G B A E C F先在中序序列中找根。前序第一个元素是 A中序序列中 A 的下标是 3。所以根AA 的左子树中序序列D G B左子树结点数为 3A 的右子树中序序列E C F对应到前序序列A 后面的 3 个元素B D G是左子树的前序序列剩下C E F是右子树的前序序列左子树部分前序B D G第一个元素 B 是根中序D G B中 B 在下标 2也就是最右边所以 B 的左子树中序为D G右子树为空D G对应的前序为D GD 是根中序D G中 D 在下标 0G 在 D 的右边说明 G 是 D 的右孩子右子树部分前序C E F第一个元素 C 是根中序E C F中 C 在下标 1左边是 E右边是 F所以 E 是 C 的左孩子F 是 C 的右孩子最终还原出的二叉树为A / \ B C / / \ D E F \ G3.3 统计无右孩子结点树画出来后逐个结点检查右孩子结点是否有右孩子是否无右孩子A有C否B无是D有G否G无是C有F否E无是F无是所以无右孩子结点为B、G、E、F共4 个。如果你在考场上遇到这类题建议不用把所有结点都写进表格只需要在画好的树上用标记法有右孩子就打个勾没右孩子就打叉最后数叉号数量即可。4. 代码实现还原二叉树并统计无右孩子结点真题是选择题理论上手算就能解决。但如果你正在复习数据结构或者刷的是代码题把建树和统计过程写成代码可以帮助你彻底理解还原逻辑。下面用 C 语言实现完整流程。4.1 C 语言二叉树结点定义#include stdio.h #include stdlib.h // 文件路径main.c typedef struct BTNode { char data; struct BTNode *lchild; struct BTNode *rchild; } BTNode;这里用 char 类型存储结点数据便于演示。实际考试代码题中数据域也可能是 int逻辑完全相同。4.2 前序 中序建树递归函数需要同时维护前序序列和中序序列的左右边界这是最容易写错的地方。// 由前序遍历序列和中序遍历序列还原二叉树 BTNode* createTreeByPreIn(char pre[], int preL, int preR, char in[], int inL, int inR) { if (preL preR) { return NULL; } BTNode *root (BTNode*)malloc(sizeof(BTNode)); root-data pre[preL]; root-lchild NULL; root-rchild NULL; // 在中序序列中找到根结点位置 k int k inL; while (in[k] ! pre[preL]) { k; } int leftLen k - inL; // 左子树结点个数 root-lchild createTreeByPreIn(pre, preL 1, preL leftLen, in, inL, k - 1); root-rchild createTreeByPreIn(pre, preL leftLen 1, preR, in, k 1, inR); return root; }关键点在于leftLen k - inL。leftLen 代表左子树有多少个结点它决定了前序序列中左子树区间的右边界是preL leftLen右子树区间的左边界是preL leftLen 1。4.3 统计无右孩子结点统计函数同样递归实现。每访问一个结点先判断它的右孩子是否为空再接着递归左右子树。// 统计无右孩子结点的个数 int countNoRight(BTNode *root) { if (root NULL) { return 0; } int cnt (root-rchild NULL) ? 1 : 0; cnt countNoRight(root-lchild); cnt countNoRight(root-rchild); return cnt; }4.4 运行与验证为了验证建树是否正确可以顺便输出后序遍历结果和手算结果对照。void postOrder(BTNode *root) { if (root NULL) { return; } postOrder(root-lchild); postOrder(root-rchild); printf(%c , root-data); } int main() { char pre[] ABDGCEF; char in[] DGBAECF; BTNode *root createTreeByPreIn(pre, 0, 6, in, 0, 6); printf(后序遍历结果); postOrder(root); printf(\n); printf(无右孩子结点个数%d\n, countNoRight(root)); return 0; }编译运行gcc main.c -o main ./main预期输出后序遍历结果G D B E F C A 无右孩子结点个数4后序遍历结果G D B E F C A和我们手算画出的树完全吻合说明建树过程是正确的。4.5 Python 可视化版本Python 版逻辑更直观适合用来验证思路。如果你平时用 Python 刷题可以参考下面写法class TreeNode: def __init__(self, val): self.val val self.left None self.right None def build_from_pre_in(pre, ino): if not pre: return None root_val pre[0] root TreeNode(root_val) idx ino.index(root_val) root.left build_from_pre_in(pre[1:idx 1], ino[:idx]) root.right build_from_pre_in(pre[idx 1:], ino[idx 1:]) return root def count_no_right(root): if root is None: return 0 cnt 1 if root.right is None else 0 cnt count_no_right(root.left) cnt count_no_right(root.right) return cnt pre list(ABDGCEF) ino list(DGBAECF) root build_from_pre_in(pre, ino) print(无右孩子结点个数, count_no_right(root))运行输出同样是 4。5. 同类变式后序 中序及其他考法5.1 后序 中序还原408 真题也经常改用“后序 中序”来出题。此时根结点在后序序列的最后一个位置其余思路完全对称。以后序遍历序列G D B E F C A和中序遍历序列D G B A E C F为例后序最后一个元素 A 是根。中序中 A 把序列分成左子树D G B和右子树E C F。左子树后序序列为G D B最后一个是 B所以 B 是 A 的左孩子这一子树的根。继续递归即可还原出同一棵树A / \ B C / / \ D E F \ G对应的 C 语言建树函数需要调整区间关系BTNode* createTreeByPostIn(char post[], int postL, int postR, char in[], int inL, int inR) { if (postL postR) { return NULL; } BTNode *root (BTNode*)malloc(sizeof(BTNode)); root-data post[postR]; // 后序最后一个元素是根 root-lchild NULL; root-rchild NULL; int k inL; while (in[k] ! post[postR]) { k; } int leftLen k - inL; root-lchild createTreeByPostIn(post, postL, postL leftLen - 1, in, inL, k - 1); root-rchild createTreeByPostIn(post, postL leftLen, postR - 1, in, k 1, inR); return root; }调用时只需要把后序序列和中序序列的区间 0 到 6 传进去即可。这个函数的核心差异在于根取自 post[postR]左子树后序区间右边界是postL leftLen - 1右子树后序区间左边界是postL leftLen。5.2 完全二叉树中的无右孩子结点计数还有一种衍生考法不给你遍历序列而是直接给一棵完全二叉树的结点数问无右孩子结点有几个。完全二叉树中度为 1 的结点最多只有 1 个且只能是左孩子。无右孩子结点包含两类度为 0 的叶子结点。度为 1 的结点如果有。设叶子结点数为 n0度为 1 的结点数为 n1则无右孩子结点数为 n0 n1。也可以换一种说法一棵有 n 个结点的完全二叉树中无右孩子结点数为 n - n2其中 n2 是度为 2 的结点数。比如一棵完全二叉树有 5 个结点1 / \ 2 3 / \ 4 5结点 3、4、5 是叶子结点结点 2 只有左孩子、没有右孩子。所以无右孩子结点是 3、4、5、2共 4 个。这个结论可以用公式验证n 5度为 2 的结点只有结点 1n2 1n - n2 4一致。5.3 层次遍历序列 中序序列还原如果题目给出层次遍历序列和中序遍历序列还原思路也是“先找根、再切中序、分左右”只是找根的顺序需要按照层次序列从前到后扫描。层次遍历序列中第一个出现在某个子树中序区间内的结点就是该子树的根。这种考法相对较少但原理相通。6. 常见错误与排查思路这类题目的错误往往集中在还原环节和概念理解上。下面把高频错误整理成一张表方便你对照检查。问题现象常见原因解决思路还原出的树和验证结果不一致中序序列中根的位置找错在中序区间内用循环定位根特别注意当前处理的是哪一个子树区间左子树前序区间切分错误没有用 leftLen 计算区间边界记住左子树前序区间为 [preL1, preLleftLen]统计结果少了结点漏掉“只有左孩子的结点”逐个结点检查右指针不要只看叶子结点后序中序建树时左右子树区间写反根取的是 post[postR]区间逻辑和前序不同左子树后序区间 [postL, postLleftLen-1]右子树区间 [postLleftLen, postR-1]递归不终止导致栈溢出区间为空时没有正确返回 NULL递归函数开头必须判断左边界大于右边界的情况针对手算题建议每次还原时都先写清当前处理的中序区间再从前序或后序里找根。不要凭感觉在草稿纸上跳步。如果使用代码实现调试时可以先输出前序、中序、后序中的任意两个遍历结果与题目给出的序列比对。只要遍历序列一致说明建树正确再统计无右孩子结点才有意义。7. 408 备考建议与总结7.1 这类题在下笔前的 30 秒看到“无右孩子结点有几个”这类问法先不要急着数结点在草稿纸上快速完成三步从给定序列中确定根结点。利用中序序列切分左右子树。画出二叉树结构再统计无右孩子结点。如果题目要求判断选项还可以利用“叶子结点一定无右孩子”这个性质先排除一部分错误选项。7.2 复习清单针对“树”这一章建议你重点整理以下内容二叉树前序、中序、后序、层次遍历的递归与非递归实现。由前序中序、后序中序还原二叉树的模板。无右孩子结点、叶结点、度为 1 结点、度为 2 结点之间的关系。完全二叉树结点编号规律以及各种结点数的计算公式。树、森林与二叉树的相互转换。每整理一个知识点就找 2 到 3 道对应真题练手。真题不需要贪多把每一道题背后的方法提炼出来比盲目刷十道题更有效。7.3 结语回到 2011 年第 6 题这道题真正想考察的不是你记住了多少结论而是你能否在陌生序列面前快速还原二叉树并准确理解“无右孩子结点”这个边界概念。把这套“找根、切中序、分左右”的模板练熟遇到同类题目基本就是送分题了。如果你现在正在刷 408 真题建议把这套还原模板抄在笔记本上考前再快速过一遍。纸上得来终觉浅拿张草稿纸把 ABDGCEF 和 DGBAECF 这对序列亲手画一遍你才能真正吃透这个考点。
