企业官网建设流程全解析

考研 408 的数据结构部分，“树”这一章是选择题的绝对大户。很多同学把重心放在二叉排序树、AVL、哈夫曼树这些复杂考点上，结果遇到一类“给遍历序列，数无右孩子结点”的题目反而容易懵。2011 年统考第 6 题就是典型代表，它问的是一棵二叉树里无右孩子结点有几个。题目看似是计算，实际考的是“由遍历序列还原二叉树”的基本功，以及你对结点孩子方向的理解是否到位。

这篇文章会从考点定位讲起，逐步拆解前序+中序还原二叉树的通用方法，再用完整例题带你手算一遍，最后给出 C 语言和 Python 的可运行代码，帮你把这 2 分稳稳拿下。

1. 考点定位：408 为什么要考“无右孩子结点”

1.1 题目到底在考什么

2011 年第 6 题给出的信息通常是二叉树的遍历序列，然后问这棵树中无右孩子结点的个数。这类题表面在考“数数”，实际上内在的考点链条是：

1. 能否根据前序（或后序）遍历序列和中序遍历序列，唯一确定一棵二叉树。
2. 能否正确画出还原后的二叉树结构。
3. 能否理解“无右孩子结点”这个概念，并准确遍历树中的每个结点完成统计。

这三点环环相扣。很多同学不是不会遍历，而是不会“逆向还原”，或者忽略了“只有左孩子、没有右孩子”的结点也应该被统计进去。

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 由遍历序列还原二叉树的基本原理

以前序 + 中序为例，还原的基本步骤可以总结为：

1. 取前序序列第一个元素作为当前子树的根。
2. 在中序序列中找到该根的位置，根左边是左子树的中序序列，右边是右子树的中序序列。
3. 根据左子树中序序列的长度，在前序序列中划分出左子树和右子树的前序序列。
4. 对左右子树分别递归执行上述过程。

整个过程可以用一张表来辅助手算，避免在草稿纸上画乱。

3. 手算通法：从前序 + 中序还原二叉树

3.1 通用步骤

假设前序遍历序列为 pre，中序遍历序列为 ino，当前处理的区间为：

• pre 区间：[preL, preR]
• ino 区间：[inL, inR]

执行以下步骤：

这个模板也对应着后面代码实现的递归参数，考试手算时把它写在草稿纸上，能减少出错。

3.2 典型例题逐步还原

下面用一道与 2011 年第 6 题同考法的题目来演示完整过程。已知某二叉树：

• 前序遍历序列：A B D G C E F
• 中序遍历序列：D G B A E C F

先在中序序列中找根。前序第一个元素是 A，中序序列中 A 的下标是 3。所以：

• 根：A
• A 的左子树中序序列：D G B，左子树结点数为 3
• A 的右子树中序序列：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 G，D 是根
• 中序D G中 D 在下标 0，G 在 D 的右边，说明 G 是 D 的右孩子

右子树部分：

• 前序C E F，第一个元素 C 是根
• 中序E C F中 C 在下标 1，左边是 E，右边是 F
• 所以 E 是 C 的左孩子，F 是 C 的右孩子

最终还原出的二叉树为：

A / \ B C / / \ D E F \ G

3.3 统计无右孩子结点

树画出来后，逐个结点检查右孩子：

所以无右孩子结点为：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 的结点只有结点 1，n2 = 1，n - n2 = 4，一致。

5.3 层次遍历序列 + 中序序列还原

如果题目给出层次遍历序列和中序遍历序列，还原思路也是“先找根、再切中序、分左右”，只是找根的顺序需要按照层次序列从前到后扫描。层次遍历序列中第一个出现在某个子树中序区间内的结点，就是该子树的根。这种考法相对较少，但原理相通。

6. 常见错误与排查思路

这类题目的错误往往集中在还原环节和概念理解上。下面把高频错误整理成一张表，方便你对照检查。

针对手算题，建议每次还原时都先写清当前处理的中序区间，再从前序或后序里找根。不要凭感觉在草稿纸上跳步。

如果使用代码实现，调试时可以先输出前序、中序、后序中的任意两个遍历结果，与题目给出的序列比对。只要遍历序列一致，说明建树正确，再统计无右孩子结点才有意义。

7. 408 备考建议与总结

7.1 这类题在下笔前的 30 秒

看到“无右孩子结点有几个”这类问法，先不要急着数结点，在草稿纸上快速完成三步：

1. 从给定序列中确定根结点。
2. 利用中序序列切分左右子树。
3. 画出二叉树结构，再统计无右孩子结点。

如果题目要求判断选项，还可以利用“叶子结点一定无右孩子”这个性质先排除一部分错误选项。

7.2 复习清单

针对“树”这一章，建议你重点整理以下内容：

• 二叉树前序、中序、后序、层次遍历的递归与非递归实现。
• 由前序+中序、后序+中序还原二叉树的模板。
• 无右孩子结点、叶结点、度为 1 结点、度为 2 结点之间的关系。
• 完全二叉树结点编号规律，以及各种结点数的计算公式。
• 树、森林与二叉树的相互转换。

每整理一个知识点，就找 2 到 3 道对应真题练手。真题不需要贪多，把每一道题背后的方法提炼出来，比盲目刷十道题更有效。

7.3 结语

回到 2011 年第 6 题，这道题真正想考察的不是你记住了多少结论，而是你能否在陌生序列面前快速还原二叉树，并准确理解“无右孩子结点”这个边界概念。把这套“找根、切中序、分左右”的模板练熟，遇到同类题目基本就是送分题了。

如果你现在正在刷 408 真题，建议把这套还原模板抄在笔记本上，考前再快速过一遍。纸上得来终觉浅，拿张草稿纸，把 ABDGCEF 和 DGBAECF 这对序列亲手画一遍，你才能真正吃透这个考点。