数据结构之二叉树的遍历和线索二叉树选择题

01.在下列关于二叉树遍历的说法中，正确的是：

A. 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。

B. 若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。

C. 若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。

D. 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。

解答

正确选项：C

解析

A. 错误

中序遍历的最后一个结点是二叉树中最右的结点，即从根沿右子女指针一直走到底的结点。如果这个结点不是叶子结点（即它还有左子树），则它的 前序遍历 的最后一个结点在它的左子树中。因为 前序遍历 先访问根结点，然后左子树，再右子树。因此，在这种情况下，中序遍历的最后一个结点不一定是前序遍历的最后一个结点。所以这个选项是错误的。

B. 错误

如果一个结点是某个子树 前序遍历 的最后一个结点，它只是最后访问的结点。它在 中序遍历 中不一定是最后一个访问的结点，因为前序遍历优先访问根结点，而中序遍历会优先访问左子树的节点。因此，前序遍历的最后一个结点不一定是中序遍历的最后一个结点。所以这个选项是错误的。

C. 正确

叶子结点 在中序遍历中是最后一个结点，表示该结点是当前子树的最右边结点。因为没有子树了，前序遍历 会直接遍历到这个叶子结点。因此，对于叶子结点来说，中序遍历 的最后一个结点一定也是 前序遍历 的最后一个结点。所以这个选项是正确的。

D. 错误

这个选项实际上与 C 类似，但顺序不同。如果某个叶子结点是 前序遍历 的最后一个结点，这并不意味着它会在 中序遍历 中也是最后一个结点。例如，如果前序遍历到的最后一个结点在中序遍历中位于左子树，而右子树还有其他结点，中序遍历的最后一个结点将是右子树中的一个结点。因此这个选项是错误的。

结论

在所有选项中，只有 C 选项 正确，即 若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。

进一步解释

前序遍历：根节点 → 左子树 → 右子树。
中序遍历：左子树 → 根节点 → 右子树。

对于叶子结点来说，无论是前序遍历还是中序遍历，叶子结点都只会在子树中的最右边被遍历，因此在它作为中序遍历的最后一个结点时，它也会是前序遍历的最后一个结点。

02.在任何一棵二叉树中，若结点 a 有左孩子 b、右孩子 c，则在结点的先序序列、中序序列、后序序列中，( )。

A. 结点 b 一定在结点 a 的前面

B. 结点 a 一定在结点 c 的前面

C. 结点 b 一定在结点 c 的前面

D. 结点 a 一定在结点 b 的前面

解答 1

正确选项：C

解析

先序遍历、中序遍历、后序遍历的规则：

先序遍历：根节点 → 左子树 → 右子树。
中序遍历：左子树 → 根节点 → 右子树。
后序遍历：左子树 → 右子树 → 根节点。

不论采用哪种遍历方式，总是会先遍历左子树，再遍历右子树。因此，左孩子结点 b 总是会在 右孩子结点 c 之前被访问。

因此，选项 C “结点 b 一定在结点 c 的前面” 是正确的。

错误选项分析：

A 错误：先序遍历中，结点 a 会首先被访问，然后是左孩子结点 b，所以 b 不一定在 a 的前面。
B 错误：在 中序遍历 或 后序遍历 中，结点 c 可能在结点 a 之前被访问，特别是在后序遍历时，a 是最后访问的结点。
D 错误：在 中序遍历 中，左孩子 b 是在结点 a 之前被访问的。

03.设 n、m 为一棵二叉树上的两个结点，在中序遍历时，n 在 m 前的条件是( )。

A. n 在 m 右方

B. n 是 m 的祖先

C. n 在 m 左方

D. n 是 m 的子孙

解答 2

正确选项：C

解析

在 中序遍历 中，按照 “左子树 → 根节点 → 右子树” 的顺序进行遍历。如果结点 n 在结点 m 的前面，意味着 n 必须位于 m 的左子树中。即 n 在 m 的左方。因此，选项 C 是正确的。

错误选项分析：

A 错误：如果 n 在 m 的右方，那么按照中序遍历的规则，m 会在 n 之前被访问。
B 错误：如果 n 是 m 的祖先，n 不一定在中序遍历中位于 m 之前。例如，n 位于 m 的右子树时，m 会先被访问。
D 错误：如果 n 是 m 的子孙，它不一定在 m 前面被访问，尤其当 n 位于 m 的右子树时。

补充解释

在中序遍历中，若想判断结点 n 是否在结点 m 之前，需要观察它们的相对位置，通常情况下，左子树的结点会在 根结点 之前被访问，而右子树的结点会在 根结点 之后被访问。因此，左方优先的原则适用于该遍历方式。

04.设 n、m 为一棵二叉树上的两个结点，在后序遍历时，n 在 m 前的条件是( )。

A. n 在 m 右方

B. n 是 m 的祖先

C. n 在 m 左方

D. n 是 m 的子孙

解答 1

正确选项：D

解析

在 后序遍历 中，按照 “左子树 → 右子树 → 根结点” 的顺序进行遍历，简称 LRN 遍历。因此：

如果 n 是 m 的子孙，那么 n 会被优先遍历，因为子节点总是在根节点之前被访问。
无论 n 位于 m 的左子树还是右子树，后序遍历都会先遍历左右子树，然后再遍历根节点。

因此，如果 n 是 m 的子孙，那么 n 会在 m 前面被访问。故选项 D 是正确的。

错误选项分析：

A 错误：后序遍历是先遍历左子树，再遍历右子树，最后遍历根节点。如果 n 在 m 的右方，n 会在 m 之后被遍历。
B 错误：在后序遍历中，祖先 m 总是在子孙 n 之后被遍历，因为子树总是在根之前遍历。
C 错误：左子树和右子树之间的顺序不能直接推导 n 是否在 m 之前。后序遍历并不直接依赖结点的左方或右方位置。

05.在二叉树中有两个结点 m 和 n，若 m 是 n 的祖先，则使用 ( ) 可以找到从 m 到 n 的路径。

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 层次遍历

解答 2

正确选项：C

解析

在 后序遍历 中，先遍历子树，最后访问根节点。因此，沿着后序遍历退回时，可以找到从子节点 n 到祖先节点 m 的路径。特别是，当我们采用非递归的后序遍历时，栈中会保存从根节点到当前节点的路径信息。当遍历到结点 n 时，栈中记录的路径包含了从根节点到 n 的所有祖先节点，因此可以很容易找到从祖先 m 到子孙 n 的路径。

错误选项分析：

A 错误：先序遍历（根 → 左 → 右）优先访问根节点，这意味着虽然可以找到从 m 到 n 的路径，但不容易记住中间的访问顺序，不是最优选择。
B 错误：中序遍历（左 → 根 → 右）不会保存父节点和子节点的路径信息，因此不能直接找到从 m 到 n 的路径。
D 错误：层次遍历按层逐层遍历节点，虽然可以找到 m 和 n 的相对位置，但不能按树的结构找到从祖先到子孙的路径。

总结

后序遍历是找到从祖先节点到子孙节点路径的最佳选择，因为在退回时可以明确得到路径。
如果要实现非递归的路径查找，栈结构保存的节点信息也能帮助记录从根节点到目标节点的所有祖先节点，从而构建路径。

06.在二叉树的前序序列、中序序列和后序序列中，所有叶子结点的先后顺序 ( )。

A. 都不相同

B. 完全相同

C. 前序和中序相同，而与后序不同

D. 中序和后序相同，而与前序不同

解答 1

正确选项：B

解析

对于 前序遍历、中序遍历 和 后序遍历，虽然访问根节点的顺序不同，但对于叶子节点来说，叶子节点没有子节点，它们在左右子树中的相对位置保持不变。由于遍历规则中，所有遍历方式都是先访问左子树，再访问右子树，因此，叶子结点的先后顺序在三种遍历方式中是完全相同的。

错误选项分析：

A 错误：三种遍历方式的叶子节点的先后顺序并不不同，实际是相同的。
C 错误：叶子节点的先后顺序不仅仅在前序和中序相同，而是在所有遍历方式中相同。
D 错误：叶子节点在前序遍历中与中序和后序遍历的顺序一致。

07.对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左、右孩子中，其左孩子的编号小于其右孩子的编号，可采用 ( ) 次序的遍历实现编号。

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 层次遍历

解答 2

正确选项：C

解析

根据题意，要求每个结点的编号大于其左、右孩子的编号，且左孩子的编号小于右孩子的编号。这意味着必须先遍历子节点再遍历父节点。这种方式正好符合 后序遍历 的顺序特点，后序遍历的顺序是 "左子树 → 右子树 → 根结点"（LRN），这样保证在访问父节点时，子节点已经被访问并赋予了较小的编号，满足题目中的要求。

错误选项分析：

A 错误：先序遍历是先访问根节点，再访问子节点，不满足父节点编号大于子节点编号的要求。
B 错误：中序遍历虽然按照左子树、根节点、右子树的顺序，但并不能保证父节点编号大于所有子节点编号。
D 错误：层次遍历（广度优先遍历）是按照层次从上到下逐层遍历节点，不能保证父节点的编号大于子节点。

总结

叶子结点的先后顺序在前序、中序、后序遍历中是完全相同的，因此答案为 B。
在编号问题中，使用 后序遍历 可以确保父节点的编号大于其左右子节点的编号，因此答案为 C。

08.前序遍历序列为 `A, B, C`，后序遍历序列为 `C, B, A` 的二叉树共有 ( )。

A. 1 棵 B. 2 棵 C. 3 棵 D. 4 棵

解答

正确选项：D

09.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 ( )。

A. 所有的结点均无左孩子 B. 所有的结点均无右孩子 C. 只有一个叶结点 D. 是任意一棵二叉树

答案

C. 只有一个叶结点

解析

前序遍历是 "根左右"，后序遍历是 "左右根"。如果二叉树的前序遍历和后序遍历恰好是彼此的逆序，意味着对于每一个非叶结点，其子结点的顺序必须严格满足一种结构。
二叉树的结构只能是链状，即每一个非叶子结点只有一个孩子，否则，前序和后序遍历的顺序不会完全相反。这种情况下，二叉树中只有一个叶子结点，并且每一个非叶结点的度数为1（即只有一个孩子）。

因此，正确的结论是该二叉树 一定只有一个叶结点，所有非叶结点的度数均为1。

10.设结点 X 和 Y 是二叉树中任意的两个结点。在该二叉树的先序遍历序列中 X 在 Y 之前，而在其后序遍历序列中 X 在 Y 之后，则 X 和 Y 的关系是 ( )。

A. X 是 Y 的左兄弟 B. X 是 Y 的右兄弟 C. X 是 Y 的祖先 D. X 是 Y 的后裔

答案

C. X 是 Y 的祖先

解析

在二叉树的 前序遍历（NLR）中，根结点会先于它的所有子结点被访问，意味着 X 在前序遍历中在 Y 之前，说明 X 在树中的位置比 Y 靠上。
在 后序遍历（LRN）中，子结点会在它的父结点之前被访问，意味着 X 在后序遍历中在 Y 之后，也说明 X 是 Y 的祖先，因为 X 的子结点（如 Y）会先被访问，之后才访问 X。

因此，X 必然是 Y 的祖先，符合选项 C 的描述。

结论

对于题目 1，C 是正确答案：这棵树一定只有一个叶结点。
对于题目 2，C 是正确答案：X 是 Y 的祖先。

11.若二叉树中结点的先序序列是 `a...b...`，中序序列是 `b...a...`，则 ( )。

A. 结点 a 和结点 b 分别在某结点的左子树和右子树中 B. 结点 b 在结点 a 的右子树中 C. 结点 b 在结点 a 的左子树中 D. 结点 a 和结点 b 分别在某结点的两棵非空子树中

答案

C. 结点 b 在结点 a 的左子树中

解析

先序遍历 (Preorder Traversal) 的顺序是先访问根结点，然后访问左子树，再访问右子树。题目给出的先序序列是 a...b...，说明结点 a 是根，结点 b 要么在 a 的左子树中，要么在右子树中。
中序遍历 (Inorder Traversal) 的顺序是先访问左子树，然后访问根结点，最后访问右子树。题目给出的中序序列是 b...a...，说明结点 b 在结点 a 的左侧，即结点 b 在结点 a 的左子树中。
根据中序和先序序列的信息，结点 b 应该在结点 a 的左子树中。

因此，正确答案是 C. 结点 b 在结点 a 的左子树中。

12. 一棵二叉树的前序遍历序列为 `1234567`，它的中序遍历序列可能是 ( )

A. 3124567 B. 1234567 C. 4135627 D. 1463572

答案

B. 1234567

解析

前序遍历 (Preorder Traversal) 的顺序是：根节点、左子树、右子树。题目给出的前序遍历序列是 1234567，表示根结点是 1，接着依次是 2, 3 等。
中序遍历 (Inorder Traversal) 的顺序是：左子树、根节点、右子树。由前序遍历可知，根结点为 1，所以 1 在中序遍历序列的某个位置，左边是它的左子树，右边是它的右子树。
对于选项：
- A. 3124567：此选项不可能，因为 3 是在 1 之前，说明 3 应在根 1 的左子树，而前序遍历中，3 出现在 2 之后，所以不符合。
- B. 1234567：此选项符合条件，1 是根结点，且左子树与右子树按顺序分布。
- C. 4135627：不符合，因为在前序遍历中，1 是根节点，4 应该在 1 的左边，但此序列中 4 出现在根的右边。
- D. 1463572：不符合，因为 6 出现在 1 和 3 之间，与前序遍历的顺序不符。

因此，正确答案是 B. 1234567。

13. 下列序列中，不能唯一地确定一棵二叉树的是 ( )

A. 层次序列和中序序列 B. 先序序列和中序序列 C. 后序序列和中序序列 D. 先序序列和后序序列

答案

D. 先序序列和后序序列

解析

先序序列 (Preorder Traversal) 和 后序序列 (Postorder Traversal) 只提供了根节点的位置信息，不能明确划分左子树和右子树。例如，先序序列为 AB，后序序列为 BA，可以对应多种二叉树结构，无法唯一确定二叉树。
层次序列和中序序列 可以唯一确定一棵二叉树，因为层次序列能明确每层的结点顺序，而中序序列能帮助划分左右子树。
先序序列和中序序列 以及 后序序列和中序序列 可以唯一确定一棵二叉树，因为中序序列可以帮助将树分割为左右子树，而先序或后序序列可以明确根节点的位置。

因此，正确答案是 D. 先序序列和后序序列。

14. 已知一棵二叉树的后序序列为 `DABEC`，中序序列为 `DEBAC`，则先序序列为 ( )

A. ACBED B. DECAB C. DEABC D. CEDBA

后序线索二叉树无法有效地求解后序后继的问题，因为在后序线索中，后继结点的线索指向的是其右孩子，而后序遍历的顺序并不符合查找后继的逻辑。比如，若结点E的后继为B，而后序线索指向的是E的右孩子，这在查找后继时并没有帮助。因此，该选项是正确的。

24. 若 X 是二叉中序线索树中一个有左孩子的结点，且 X 不为根，则 X 的前驱为 ( )

A. X 的双亲 B. X 的右子树中最左的结点 C. X 的左子树中最右的结点 D. X 的左子树中最右的叶结点

答案: C

解释: 在二叉中序线索树中，若某结点 X 有左孩子，则根据中序遍历的顺序“左根右”， X 的前驱结点应该是其左子树中最右的结点。该前驱是中序遍历中在 X 之前访问的最后一个结点，并不一定是叶子结点。

25. ( ) 的遍历仍需要栈的支持

A. 前序线索树 B. 中序线索树 C. 后序线索树 D. 所有线索树

答案: C

解释: 在后序线索树中，最后访问根结点。当从右孩子返回访问父结点时，若右孩子不为空，右指针无法直接指向其后序遍历的后继结点，这使得后序遍历无法通过线索直接完成，需要借助栈的支持。而前序和中序线索树可以通过线索完成遍历，因此它们不需要栈。

26. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是 ()

A. 空或只有一个结点 B. 高度等于其结点数 C. 任一结点无左孩子 D. 任一结点无右孩子

答案: B

解释: 若一棵非空二叉树的先序序列和后序序列正好相反，即“根左右”与“左右根”顺序相反，那么该树结构特殊——树形是一条长链（线性结构），即每个结点最多只有一个孩子。这意味着每个结点都是唯一的孩子，且树的高度等于其结点数。因此，选项 B 为正确答案。

27. 【2009 统考真题】给定二叉树如右图所示。设 N 代表二叉树的根， L 代表根结点的左子树， R 代表根结点的右子树。若遍历后的结点序列是 3175624，则其遍历方式是 ( )

A. LRN B. NRL C. RLN D. RNL

答案: D

解释: 分析遍历后的结点序列 3175624 ，可以看出根结点是在中间被访问的，而右子树的结点在左子树的结点之前被访问。因此，该遍历的顺序是 RNL (右子树-根结点-左子树)，这是一种特殊的遍历方法。本题重点在于理解遍历的思想，而非仅限于三种基本的二叉树遍历方法 (前序、中序、后序遍历)。

28.【2010统考真题】下列线索二叉树中(用虚线表示线索 ),符合后序线索树定义的是( )。

答案：D

解释：

显而易见。

29. 【2011 统考真题】一棵二叉树的前序遍历序列和后序遍历序列分别为 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

答案: C

解释: 前序遍历序列为 NLR ，后序遍历序列为 LRN ，在这个题目中，前序序列与后序序列刚好是完全相反的，因此这棵二叉树的高度为 4，且每个结点只有一个孩子，必须是单链树（即没有结点同时有左右孩子）。根结点 1 在前序序列中第一个位置，在后序序列中最后一个位置，这意味着中序遍历中的 1，2 要么在序列的首位，要么在序列的末位。选项 A、B、D 都符合这一规律，而选项 C 中 2 并不在首或尾，因此不可能是中序遍历序列，故选 C。

30. 【2012 统考真题】若一棵二叉树的前序遍历序列为 a, e, b, d, c，后序遍历序列为 b, c, d, e, a，则根结点的孩子结点是 ( )

A. 只有 e B. 有 e、b C. 有 e、c D. 无法确定

答案: A

解释: 分析前序遍历序列 a, e, b, d, c 和后序遍历序列 b, c, d, e, a 。从前序遍历中可以确定 a 是根结点，并且从前序遍历中可以看到 e 是紧随 a 的结点，因此 e 是 a 的孩子结点。接着，从 e 的孩子结点的前序和后序遍历序列可以进一步得知， e 是 b, d, c 的祖先。因此根结点 a 的直接孩子结点只有 e ，故选 A。

31. 【2013 统考真题】若 X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y，则 X 的右线索指向的是 ( )

A. X 的父结点 B. 以 Y 为根的子树的最左下结点 C. X 的左兄弟结点 Y D. 以 Y 为根的子树的最右下结点

答案: A

解释: 在后序线索二叉树中，结点的“右线索”指向其后序遍历的后继结点。若 X 是叶结点且存在左兄弟结点 Y，则根据后序遍历的规则，X 的后序后继结点为它的父结点。因此，X 的右线索指向其父结点。故选 A。

32. 【2014 统考真题】若对右图所示的二叉树进行中序线索化，则结点 d 的左、右线索指向的结点分别是 ( )

A. e, c B. e, a C. d, c D. b, a

答案: D

解释: 中序线索化是指按照中序遍历（左根右）的顺序，在二叉树中将那些为空的指针域转换为线索，指向遍历过程中该结点的前驱或后继结点。根据右图（假设图中存在某二叉树），通过中序遍历可以判断结点 d 的左线索指向的是结点 b，而 d 的右线索指向的是结点 a。故选 D。

33. 【2015 统考真题】先序序列为 a,b,c,d 的不同二叉树的个数是 ( )

A. 13 B. 14 C. 15 D. 16

答案: B

解释: 给定先序序列 a, b, c, d ，不同二叉树的个数实际上可以通过“Catalan数”来计算。对于 n 个结点，不同的二叉树个数为 C_n ，其公式为：

C_n =

代入 n = 4 ：

C_4 = = 14

因此，先序序列为 a, b, c, d 的不同二叉树的个数为 14。故选 B。

34. 【2017 统考真题】某二叉树的树形如右图所示，其后序序列为 e, a, c, b, d, g, f，树中与结点 a 同层的结点是 ( )

A. b B. d C. c D. g

答案: B

解释:

通过分析给定的后序遍历序列 e, a, c, b, d, g, f ，后序遍历顺序是“先左子树，再右子树，最后父结点”。在此二叉树中，结点 e 为最左边的叶子结点，接着访问它的父结点 a ，然后是 a 的父结点 c 。接着访问右子树，结点 b 及其父结点 d ，再往上是 g 和根结点 f 。

根据层次分析，与结点 a 位于同一层的结点是 d 。故选 B。

35. 【2017 统考真题】要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是( )。

A. 只有左子树 B. 只有右子树 C. 结点的度均为 1 D. 结点的度均为 2

答案: B

解释: 为了使一棵非空二叉树的先序序列和中序序列相同，必须保证每个非叶结点的结构在这两种遍历方式中产生的序列一致。先序遍历（NLR）表示先访问根结点，然后访问左子树，再访问右子树。中序遍历（LNR）表示先访问左子树，再访问根结点，然后访问右子树。

如果所有非叶结点只有右子树，即每个结点没有左子树，那么两种遍历顺序都会先访问父结点，然后继续递归访问右子树，导致先序和中序遍历的结果相同。

因此，正确答案是 B. 只有右子树。

数据结构之二叉树的遍历和线索二叉树选择题

01.在下列关于二叉树遍历的说法中，正确的是：

解答

解析

A. 错误

B. 错误

C. 正确

D. 错误

结论

进一步解释

02.在任何一棵二叉树中，若结点 a 有左孩子 b、右孩子 c，则在结点的先序序列、中序序列、后序序列中，( )。

解答 1

解析

先序遍历、中序遍历、后序遍历的规则：

错误选项分析：

03.设 n、m 为一棵二叉树上的两个结点，在中序遍历时，n 在 m 前的条件是( )。

解答 2

解析

错误选项分析：

补充解释

04.设 n、m 为一棵二叉树上的两个结点，在后序遍历时，n 在 m 前的条件是( )。

解答 1

解析

错误选项分析：

05.在二叉树中有两个结点 m 和 n，若 m 是 n 的祖先，则使用 ( ) 可以找到从 m 到 n 的路径。

解答 2

解析

错误选项分析：

总结

06.在二叉树的前序序列、中序序列和后序序列中，所有叶子结点的先后顺序 ( )。

解答 1

解析

错误选项分析：

07.对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左、右孩子中，其左孩子的编号小于其右孩子的编号，可采用 ( ) 次序的遍历实现编号。

解答 2

解析

错误选项分析：

总结

08.前序遍历序列为 A, B, C，后序遍历序列为 C, B, A 的二叉树共有 ( )。

解答

09.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 ( )。

答案

解析

10.设结点 X 和 Y 是二叉树中任意的两个结点。在该二叉树的先序遍历序列中 X 在 Y 之前，而在其后序遍历序列中 X 在 Y 之后，则 X 和 Y 的关系是 ( )。

答案

解析

结论

11.若二叉树中结点的先序序列是 a...b...，中序序列是 b...a...，则 ( )。

答案

解析

12. 一棵二叉树的前序遍历序列为 1234567，它的中序遍历序列可能是 ( )

答案

解析

13. 下列序列中，不能唯一地确定一棵二叉树的是 ( )

答案

解析

14. 已知一棵二叉树的后序序列为 DABEC，中序序列为 DEBAC，则先序序列为 ( )

答案

15.已知一棵二叉树的先序遍历结果为 ABCDEF，中序遍历结果为 CBAEDF，则后序遍历的结果为 ( )

答案

解析

16.已知一棵二叉树的层次序列为 ABCDEF，中序序列为 BADCFE，则先序序列为 ( )

答案

解析

17.引入线索二叉树的目的是 ( )

答案

解析

18.线索二叉树是一种 ( ) 结构

答案

解析

19. n个结点的线索二叉树上含有的线索数为 ( )

答案

解析

20.**判断线索二叉树中 *p 结点有右孩子结点的条件是 ( )**

答案

解析

一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是 ( )

答案

解析

22.在线索二叉树中，下列说法不正确的是 ( )

08.前序遍历序列为 `A, B, C`，后序遍历序列为 `C, B, A` 的二叉树共有 ( )。

11.若二叉树中结点的先序序列是 `a...b...`，中序序列是 `b...a...`，则 ( )。

12. 一棵二叉树的前序遍历序列为 `1234567`，它的中序遍历序列可能是 ( )

14. 已知一棵二叉树的后序序列为 `DABEC`，中序序列为 `DEBAC`，则先序序列为 ( )

15.已知一棵二叉树的先序遍历结果为 `ABCDEF`，中序遍历结果为 `CBAEDF`，则后序遍历的结果为 ( )

16.已知一棵二叉树的层次序列为 `ABCDEF`，中序序列为 `BADCFE`，则先序序列为 ( )