第 6 章 树和二叉树
一、选择题
1.D 2.B 3.C 4.D 5.D 6.A 7.1C 7.2A 7.3C 7.4A 7.5
C
8.B
9.C 10.D 11.B 12.E 13.D 14.D 15.C 16.B 17.C 18.C 19.
B
20.
D
21.A 22.A 23.C 24.C 25.C 26.C 27.C 28.C 29.B 30.C 31.
D
32.B
33.A 34.D 35.B 36.B 37.C 38.B 39.B 40.B 41.1
F
41.2
B
42.
C
43.B
44.C 45.C 46.B 47.D 48.B 49.C 50.A 51.C 52.C 53.C 54.
D
55.
C
56.B 57.A 58.D 59.D 60.B 61.1
B
61.2
A
61.3
G
62.B 63.B 64.
D
65.
D
66.1
C
66.2
D
66.3
F
66.4
H
66.5
I
部分答案解释如下。
12. 由 二 叉 树 结 点 的 公 式 ： n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1 ， 因 为 n=1001, 所 以
1002=2n0+n1,在完全二叉树树中，n1 只能取 0 或 1,在本题中只能取 0，故 n=501，因此选 E。
42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的 A 和 B
均对，单支树的特点是只有一个叶子结点，故 C 是最合适的，选 C。A 或 B 都不全。由本题可解答 44 题。
47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后
继），共 2 个空链域。
52．线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有 n+1 个空链域。
二、判断题
1.× 2.× 3.× 4. √ 5. √ 6. √ 7.√ 8.× 9. √ 10.× 11.× 12.×
13.× 14.√ 15.× 16.× 17.√ 18.√ 19.× 20.√ 21.× 22.√ 23.× 24.×
25.√ 26.× 27.× 28.× 29.√ 30.× 31.× 32.√ 33.× 34.× 35.× 36.√
37.√ 38.× 39.× 40.× 41.
(3)
42.√ 43.√ 44.× 45.√ 46.× 47.× 48.×
49.√ 50.√
部分答案解释如下。
6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。
19．任何结点至多只有左子树的二叉树的遍历就不需要栈。
24. 只 对 完 全 二 叉 树 适 用 ， 编 号 为 i 的 结 点 的 左 儿 子 的 编 号 为 2i(2i<=n) ， 右 儿 子 是
2i+1（2i+1<=n）
37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。
38 . 新插入的结点都是叶子结点。
42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点
的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖
先）。
44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索
