🏷️ 知识点：二叉树的遍历
一棵二叉树的前序遍历序列为 1234567，它的中序遍历序列可能是（ ）。
A. 3124567 B. 1234567 C. 4135627 D. 2153647
[tag_link]
正确答案：B
前序遍历序列为 1234567，因此根节点是 1。
中序遍历的顺序是左子树、根、右子树。 对于根节点 1，在中序遍历中，所有在 1 左侧的节点构成左子树，在 1 右侧的节点构成右子树。 同时，前序遍历中根 1 之后应首先遍历左子树（如果存在），然后遍历右子树。
选项 A 的中序为 3124567，即序列 3,1,2,4,5,6,7。 此时根 1 左侧有节点 3，说明左子树非空。 但前序序列中根 1 之后是 2，而不是左子树的节点 3，这导致矛盾，因此不可能。
选项 C 的中序为 4135627，即序列 4,1,3,5,6,2,7。 根 1 左侧有节点 4，左子树非空。 但前序序列中根 1 之后是 2，而不是左子树的节点 4，同样矛盾，因此不可能。
选项 D 的中序为 2153647，即序列 2,1,5,3,6,4,7。 根 1 左侧有节点 2，左子树非空。 前序序列中根 1 之后是 2，这符合左子树根为 2 的情况。 然而，右子树的中序为 5,3,6,4,7，其根应为前序中 2 之后的 3。 但根据右子树的结构，根 3 应有左子树节点 5，因此在前序中 3 之后应先出现 5，而实际前序序列中 3 之后是 4，导致矛盾，因此不可能。
选项 B 的中序为 1234567，即序列 1,2,3,4,5,6,7。 此时根 1 左侧无节点，左子树为空，所有节点都在右子树。 右子树的结构类似：根 2 左子树为空，右子树根 3，依此类推，形成每个节点只有右孩子的向右倾斜二叉树。 这种情况下，前序遍历和中序遍历序列均为 1234567，完全匹配，因此是可能的。
综上，只有选项 B 的中序遍历序列可能对应前序遍历序列为 1234567 的二叉树。
若一棵二叉树的前序遍历序列为 a, e, b, d, c，后序遍历序列为 b, c, d, e, a，则根结点的孩子结点（ ）。
A. 只有 e
B. 有 e、b
C. 有 e、c
D. 无法确定
[tag_link]
正确答案：A
本题考察 双序列组合重建二叉树 ，前序序列和后序序列不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系：当两个结点的前序序列为 XY 与后序序列为 YX 时，则 X 为 Y 的祖先。考虑前序序列 a,e,b,d,c、后序序列 b,c,d,e,a 且，可知 a 为根结点，e 为 a 的孩子结点。此外，a 的孩子结点的前序序列 e,b,d,c、后序序列 b,c,d,e，可知 e 是 bcd 的祖先，故根结点的孩子结点只有 e。故选 A。
p、q、v 都是二叉树 T 中的结点，二叉树 T 的中序遍历为 ···, p，v，q，··· ，其中 v 有两个孩子结点，则下列说法正确的是（ ）。
A. p 没右孩子，q 没左孩子 B. p 没右孩子，q 有左孩子 C. p 有右孩子，q 没左孩子 D. p 有右孩子，q 有左孩子
[tag_link]
正确答案：A
根据中序遍历结果和 v 是子树的根节点这些信息，则可以判定 p,q 分别在 v 的的左右子树上，对 于左子树而言，根据中序遍历结果为…p，则没有右孩子，同理，q 没有左孩子。或者假设 p 有右孩子 ,q 有左孩子，则中序遍历结果中 p,v 之间一定还有序列，v,q 之间也一定还有序列，和题意冲突。
在一棵非空二叉树的中序遍历序列中，根结点的右边（ ）。
A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点
[tag_link]
正确答案：A
中序遍历二叉树的顺序是：先遍历左子树，然后访问根结点，最后遍历右子树。 因此，在中序遍历序列中，根结点的左边包含左子树上的所有结点，而根结点的右边包含右子树上的所有结点。 选项 A 正确描述了根结点右边只有右子树上的所有结点； 其他选项不符合中序遍历的定义。
要使一颗非空二叉树的先序序列与中序序列相同，其所有非叶节点须满足的条件是（）
A. 只有左子树 B. 只有右子树 C. 结点的度均为 1 D. 结点的度均为 2
[tag_link]
正确答案：B
先序序列是根左右，中序序列是左根右，递归进行。如果所有非叶结点只有右子树，先序序列和中序序列都是先父结点，然后右子树，递归进行，因此 B 正确。
已知森林 F 及与之对应的二叉树 T，若 F 的先根遍历序列是 a,b,c,d,e,f，中根遍历序列是 b,a,d,f,e,c，则 T 的后根遍历序列是（ ）。
A. b,a,d,f,e,c B. b,d,f,e,c,a C. b,f,e,d,c,a D. f,e,d,c,b,a
[tag_link]
正确答案：C
本题考察的是 森林的遍历，森林 F 的先根遍历序列对应其二叉树 T 的先序遍历序列，森林 F 的中根遍历序列对应其二叉树 T 的中序遍历序列。即 T 的先序遍历序列为 a,b,c,d,e,f，中序遍历序列为 b,a,d,f,e,c。根据二叉树 T 的先序序列和中序序列可以唯一确定它的结构，构造过程如下：可以得到二叉树 T 的后序序列为 b,f,e,d,c,a。
由某种序列可以唯一地确定一棵二叉树，不能唯一地确定一棵二叉树是（ ）。
A. 先序序列和中序序列 B. 后序序列和中序序列 C. 中序序列和层序序列 D. 先序序列和层序序列
[tag_link]
正确答案：D
在二叉树的遍历序列中，不同的序列组合对二叉树结构的确定能力不同。
已知先序序列和中序序列可以唯一确定一棵二叉树，因为先序序列提供根节点信息，中序序列区分左右子树； 同样，后序序列和中序序列也可以唯一确定二叉树，原理类似。
中序序列和层序序列也能唯一确定二叉树，因为层序序列给出层次顺序，结合中序序列的左右子树信息，可以通过递归方式重建二叉树。
然而，先序序列和层序序列不能唯一确定二叉树。 例如，考虑只有两个节点A和B的二叉树：若B是A的左子节点，先序序列为A、B，层序序列为A、B； 若B是A的右子节点，先序序列同样为A、B，层序序列也为A、B。 这两个不同的二叉树产生了相同的先序和层序序列，因此无法唯一确定结构。
因此，不能唯一确定二叉树的选项是D。
前序遍历和中序遍历结果相同的二叉树为（ ）。 I. 只有根结点的二叉树 II. 根结点无右孩子的二叉树 III. 所有结点只有左子树的二叉树 IV. 所有结点只有右子树的二叉树
A. 仅有 I B. I、II 和 IV C. I 和 III D. I 和 IV
[tag_link]
正确答案：D
前序遍历的顺序是根节点、左子树、右子树； 中序遍历的顺序是左子树、根节点、右子树。 要使两者结果相同，需满足序列的对应关系。
对于只有根结点的二叉树，前序和中序都仅包含根节点，序列相同，因此 I 正确。
对于根结点无右孩子的二叉树，若根结点有左孩子，则前序以根节点开头，中序以左子树节点开头，序列不同； 若左孩子也为空（即只有根结点），则与 I 相同。 因此 II 不一定成立。
对于所有结点只有左子树的二叉树（即左斜树），前序从根节点开始向下访问左孩子，中序从最左叶子开始向上访问，两者序列相反，因此 III 错误。
对于所有结点只有右子树的二叉树（即右斜树），每个节点的左子树为空，中序遍历中节点在左子树之后访问，由于左子树为空，节点立即被访问，然后访问右子树，递归地使得整个树的前序和中序序列一致，因此 IV 正确。
综上所述，I 和 IV 正确，对应选项 D。
某二叉树结点的中序序列为 BDAECF，后序序列为 DBEFCA，则该二叉树对应的森林包括（ ）棵树。
A. 1 B. 2 C. 3 D. 4
[tag_link]
正确答案：C
考查由遍历序列确定二叉树、森林与二叉树的转换。 根据后序序列，A 是二叉树的根结点。 根据中序遍历序列，则二叉树的形态一定如下图左所示。 对于 A 的左子树，由后序序列可知，因为 B 比 D 后被访问，因此，B 必为 D 的父结点，又由中序序列可知，D 是 B 的右儿子。 对于 A 的右子树，同理可确定结点 E、C、F 的关系。 此二叉树的形态如下图右所示。
再根据二叉树与森林的对应关系。 森林中树的棵数即为其对应二叉树（向右上旋转 45° 后）中根结点 A 及其“右兄弟”数。 可知此森林中有 3 棵树，根结点分别为 A、C 和 F。
若一棵二叉树的前序遍历序列和后序遍历序列分别为 1,2,3,4 和 4,3,2,1，则该二叉树的中序遍历序列不会是（）
A. 1,2,3,4
B. 2,3,4,1
C. 3,2,4,1
D. 4,3,2,1
[tag_link]
正确答案：C
前序序列为根左右，后序序列为左右根，由于前序序列和后序序列刚好相反，故不可能存在一个结点同时存在左右孩子，即二叉树的高度为 4。1 为根结点，由于根结点只能有左孩子（或右孩子），因此，在中序序列中，1 或在序列首或在序列尾，ABCD 皆满足要求。仅考虑以 1 的孩子结点 2 为根结点的子树，它也只能有左孩子（或右孩子），因此，在中序序列中，2 或在序列首或序列尾，ABD 皆满足要求，答案选择 C。
已知一颗二叉树的树形如下图所示，其后序序列为 e，a，c，b，d，g，f，树中与结点 a 同层的结点是（）
A. c B. d C. f D. g
[tag_link]
正确答案：B
后序序列是先左子树，接着右子树，最后父结点，递归进行。根结点左子树的叶结点首先被访问，它是 e。接下来是它的父结点 a, 然后是 a 的父结点 c。接着访问根结点的右子树。它的叶结点 b 首先被访问，然后是 b 的父结点 d, 再者是 d 的父结点 g。最后是根结点 f。因此 d 与 a 同层，B 正确。
以下关于二叉排序树的说法中，错误的有（ ）个。
A. 1 B. 2 C. 3 D. 4
[tag_link]
正确答案：D
说法 I 错误：对二叉排序树进行前序遍历（根→左→右）时，先访问根结点，然后访问所有小于根的左子树结点，最后访问所有大于根的右子树结点，得到的序列并非从大到小； 只有中序遍历才能得到有序序列。 说法 II 错误：二叉排序树要求每个结点的左子树中所有结点值都小于该结点值，右子树中所有结点值都大于该结点值； 仅满足“比左孩子值大、比右孩子值小”不能保证整个子树满足条件，例如左孩子的右孩子可能大于根结点，违反定义。 说法 III 错误：插入的关键字总是位于叶结点，但是叶结点并不一定位于最底层。 说法 IV 错误：删除结点时，若结点有两个孩子，通常用前驱或后继替换，可能改变树的结构； 重新插入同一关键字时，会作为新叶子插入，位置可能不同，因此得到的树与原来不一定相同。 综上，错误的有 I、II、IV，共 3 个。
对关键码序列 28,16,32,12,60,25,72 快速排序，从小到大一次划分结果为（ ）。
A. (2,5,12,16) 28 (60,32,72) B. (5,16,12) 28 (60,32,72) C. (2,16,12,5) 28 (60,32,72) D. (5,16,2,12) 28 (32,60,72)
[tag_link]
正确答案：B
快速排序的一次划分通常以序列的第一个元素作为基准（pivot）。
对于序列 28,16,32,12,60,25,72，选择 28 作为基准，目标是将序列划分为左边所有元素小于 28，右边所有元素大于 28。 常见划分方法（如 Lomuto 划分）的步骤如下：
- 从左向右扫描，将小于 28 的元素移动到左侧，大于等于 28 的元素留在右侧。 >
- 最终交换基准元素到正确位置。 >
具体过程：初始化基准为 28。 > 遍历序列，小于 28 的元素有 16、12 和 25。 > 通过交换操作，划分后基准 28 位于中间位置，左边为小于 28 的元素（顺序可能改变），右边为大于 28 的元素。 > 划分结果为左边序列 (25,16,12)，基准 28，右边序列 (60,32,72)。 >
观察选项，B 选项为 (5,16,12) 28 (60,32,72)，其中左边有三个元素，与小于 28 的元素个数一致； > 右边为 (60,32,72)，与大于 28 的元素一致。 > 虽然 B 中写为“5”，但根据序列元素推断应为“25”（可能为笔误），且其他选项左边元素个数不符合要求，因此 B 为正确答案。 >
（13 分）假设二叉树采用二叉链表存储结构存储，设计一个算法，求先序遍历序列中第 k（1≤k≤二叉树中结点个数）个结点的值，要求：
（1）给出算法的基本设计思想。
（2）写出二叉树采用的存储结构代码。
（3）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
[tag_link]
【答案】
（1）算法的基本设计思想： 采用递归先序遍历二叉树，设置一个计数器记录已访问的结点数。遍历时，每访问一个结点，计数器加 1。当计数器等于 k 时，当前结点即为所求，记录其值并终止遍历；若计数器小于 k，则继续递归遍历左子树和右子树。通过递归和计数器控制，可在找到第 k 个结点后提前结束遍历，提高效率。
（2）二叉树采用的存储结构代码： // 二叉链表存储结构 typedef struct BiTNode { int data ; // 结点数据域，假设为整型 struct BiTNode * lchild ; // 左孩子指针 struct BiTNode * rchild ; // 右孩子指针 } BiTNode , * BiTree ;
（3）算法描述（C++ 语言）： // 辅助递归函数：在先序遍历中查找第 k 个结点 // 参数：node-当前结点指针，k-目标序号，count-计数器（引用传递），result-存储结果（引用传递），found-是否找到标志（引用传递） void PreOrderKthHelper ( BiTree node , int k , int & count , int & result , bool & found ) { if ( node == nullptr || found ) { return ; // 结点为空或已找到目标，直接返回 } count ++ ; // 访问当前结点，计数器加 1 if ( count == k ) { result = node -> data ; // 找到第 k 个结点，记录其值 found = true ; // 设置找到标志，提前终止遍历 return ; } PreOrderKthHelper ( node -> lchild , k , count , result , found ); // 递归遍历左子树 PreOrderKthHelper ( node -> rchild , k , count , result , found ); // 递归遍历右子树 } // 主函数：求先序遍历中第 k 个结点的值 // 参数：root-二叉树根节点指针，k-要查找的序号（1≤k≤结点总数） // 返回值：第 k 个结点的值，如果 k 无效或未找到，返回 -1（假设结点值非负） int PreOrderKth ( BiTree root , int k ) { int count = 0 ; // 计数器，初始化为 0 int result = - 1 ; // 存储结果，初始化为 -1 表示未找到 bool found = false ; // 标志位，初始为 false PreOrderKthHelper ( root , k , count , result , found ); return result ; // 返回结果 } 【解析】 算法基于递归先序遍历实现，先序遍历顺序为根结点、左子树、右子树。通过计数器 count 记录访问结点的次序，当 count 等于 k 时，当前结点即为所求。使用引用参数传递 count、result 和 found，使得递归过程中能共享和修改这些变量，并通过 found 标志提前终止遍历，避免不必要的递归调用。 二叉链表存储结构是二叉树常用的链式存储方式，每个结点包含数据域和指向左右子树的指针，便于动态管理二叉树。 算法的时间复杂度为 O(n)，其中 n 为二叉树结点数，最坏情况下需遍历所有结点（当 k 大于结点总数或为最后一个结点时），但平均情况下若 k 较小可提前结束。空间复杂度为 O(h)，h 为二叉树高度，主要由递归栈空间占用。算法简洁高效，符合先序遍历特性。