第六章树与二叉树

第六章树与二叉树

一．选择题

1．下面关于二叉树的结论正确的是____________。

A．二叉树中，度为 0 的结点个数等于度为 2 的结点个数加 1。 B．二叉树中结点个数必大于 0。

C．完全二叉树中，任何一个结点的度，或者为 0，或者为 2。 D．二叉树的度是 2。

分析：该题目主要考查二叉树逻辑结构的特点。正确答案为 A。二叉树中叶

子结点的个数为 n0 ，度为 2 的结点的个数为 n2，度为 1 的结点个数为 n1， 树中结点总数为 n，则 n= n0+ n2+ n1。除根节点没有双亲外，每个结点都有 且仅有一个双亲，所以有 n-1= n1+ 2n2 作为孩子的结点，因此有 n0= n2+1。 二叉树中结点个数可以为 0，称为空树，所以 B 错。满二叉树中，任何一个 结点的度，或者为 0，或者为 2。完全二叉树中，任何一个结点的度，或者

为 0，或者为 1，或者为 2。所以 C 错。二叉树的度可以是 0、1、2。所以 D 错。

2．设 X 是树 T 中的一个非根结点，B 是 T 所对应得二叉树，在 B 中，X 是 其双亲的右孩子，下列结论正确的是____________。

A．在树 T 中，Ｘ是其双亲的第一个孩子。 B．在树 T 中，Ｘ一定无右边 兄弟。

C．在树 T 中，Ｘ一定是叶子结点。 D．在树 T 中，Ｘ一定有左边 兄弟。

分析：该题目主要考查树和二叉树的转换。根据树和二叉树转换的规则可 以得到 D 为正确答案。

3．一棵三叉树中，已知度为 3 的结点数等于度为 2 的结点数，且树中叶结 点的数目为 13，则度为 2 的结点数目为____________。 A．4 B．2 C．3 D．5

分析：该题目主要考查多叉树逻辑结构的特点。根据选择题第 1 小题的思

路，有 n0+n1+n2+n3=n，n-1=n1+2n2+3n3，n0、n1、n2、n3 分别为度是 0，1，2， 3 的结点数，n 为树的结点总数。在本题中，n0=13，n2=n3。正确答案为 A。 4．设 n、m 为一棵二叉树上的两个结点，在中序遍历时，n 在 m 之前的条件 是____________。

A．n 在 m 右方 B．n 是 m 祖先 C．n 在 m 左方 D．n 是 m 子 孙

分析：该题目主要考查二叉树的遍历。根据二叉树的形态和中序遍历算法，

当 n 在 m 左边时，结点 n 首先被遍历。当 n 是 m 祖先时，它们之间的关系 无法确定，不妨假设 n 是根结点，m 是其左孩子，则 m 在 n 之前；m 是其右 孩子，则 n 在 m 之前。正确答案为 C。

5．对一个满二叉树，m 个树枝，n 个结点，深度为 h，则____________。 A．n=h+m B．h+m=2n C．m=h-1 D．n=2 h -1

分析：该题目主要考查满二叉树的定义，根据满二叉树定义，正确答案为 D。 6．一棵有 n 个结点的 k 叉树，树中所有结点的度之和为____________。 A．n-1 B．kn C．n 2 D．2n

分析：该题目主要考查树的结点和度之间的关系。由树的度的定义可知结

点的度即为与之相连的子结点的个数，而只有根结点不是连在其他的结点 上，所以和为 n-1。答案为 A。

7．以二叉链表作为二叉树的存储结构，在有 n 个结点的二叉链表中(n>0)， 链表中空链域的个数为____________。

A．2n-1 B．n-1 C．n+1 D．2n+1

分析：该题目主要考查二叉树的链式存储结构。每个结点共有两个链域， 即共有 2n 个链域，n 个结点构成的二叉树中至少有 n-1 个链接指针才能将 n 个结点连接在一起，即已经用去 n-1 个指针域，则空链域为 2n-(n-1)=n+1 个。答案为 C。

8．设森林中有 3 棵树，其中第 1、第 2 和第 3 棵树的结点个数分别为 n1、 n2 、n3 ，则与森林对应的二叉树中根结点的右子树上的结点个数是 ____________。

A．n1 B．n1+ n2 C． n3 D．n2+n3

分析：该题目主要考查森林和二叉树之间的转换关系。森林中的第一棵树 对应于二叉树根结点及其左子树，第 2 和第 3 棵树对应于二叉树中根结点 的右子树，则其结点个数为 n2+n3。答案为 D。

9．将含有 150 个结点的完全二叉树从根这一层开始，每一层从左到右依次 对结点进行编号，根结点的编号为 1，则编号为 69 的结点的双亲结点的编 号为____________。

A．33 B．34 C．35 D．36

分析：该题目主要考查完全二叉树的逻辑结构。由二叉树的性质 5 可知， 结点 69 的双亲结点编号为?69/2?=34。所以答案为 B。

10．在一棵二叉树结点的先序序列、中序序列、后序序列中，所有叶子结 点的先后顺序__________。

A．都不相同 B．先序和中序相同，而与后序不同 C．完全相同 D．中序和后序相同，而与先序不同

分析：该题目主要考查二叉树的遍历。无论哪种遍历所得的序列都是在 “左”、“右”两结点的空隙中插入“根”结点的排列，即左、右结点的顺

序固定不变，改变的是“根”结点，叶子结点的先后顺序都不变。答案为 C。 11．如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径 长度最小，则该树称为____________。

A．哈夫曼树 B．平衡二叉树 C．二叉树 D．完全二叉树

分析：该题目主要考查哈夫曼树的定义。利用哈夫曼树算法构造出的具有 最小带权外部路径长度的扩充二叉树，所构造的二叉树对于给定的权值， 带权路径长度最小。答案为 A。

12．树的先根序列和其对应的二叉树的 是一样的，树的后根序列和 其对应的二叉树的 是一样的。

A．先序序列 B．中序序列 C．后序序列 D．按层次遍历序 列

分析：该题目主要考查树和二叉树的转换关系。考虑树的根结点及其 n 个 子树，当转换为二叉树后，根结点和最左子树的根结点的位置不变,而其它 子树的根结点都成为其相邻左子树根结点的右孩子。这样的转换是递归过

程。观察这样的结构变化，得到答案为 A，B。

13．若一个具有 N 个顶点，K 条边的无向图是一个森林(N>K),则该森林中必 有_____棵树。

A．K B．N C．N-K D．1

分析：该题目主要考查森林的概念，树的顶点和边的关系。设此森林中有 m 棵树，每棵树具有的顶点数为 vi (1≤i≤m)，则 v1+v2+…+vm=N (1)

(v1-1)+(v2-1)+…+(vm-1)=K (2)

(1)-(2)得： m=N-K。所以答案是 C。

14．欲实现任意二叉树的后序遍历的非递归算法而不必使用栈结构，最佳 方案是二叉树采用___________存储结构。

A．三叉链表 B．广义表 C．二叉链表 D．顺序

分析：该题目主要考查二叉树的存储结构和非递归遍历算法。此题答案为 A。 三叉链表是将双亲表示法和孩子兄弟表示法结合起来，既能方便地从双亲 查找孩子，又能方便地从孩子查找双亲。

15．一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值 都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采 用___________遍历方式就可以得到这棵二又树上所有结点的递减序列。 A．先序 B．中序 C．后序 D．层次

分析：该题目主要考查二叉树的遍历。由于中序遍历的顺序是先中序遍历 左子树，再访问根结点，最后中序遍历右子树。这样可以保证，对任一结 点其左孩子总在它的左边，其右孩子总在它的右边。当二叉树满足题述条 件时，其中序序列一定是个递减序列。答案为 B。

16．对含有___________个结点的非空二叉树，采用任何一种遍历方式，其 结点访问序列均相同。

A．0 B．1 C．2 D．不存在这样的二叉树

分析：该题目主要考查二叉树的三种遍历次序的关系。三种遍历方式的不 同点，在于访问根结点的时机不同。当一棵二叉树仅含一个根结点时，不 管采用哪种遍历方式，所得到的结点序列总是相同的。此题答案为 B。 17．对___________进行相应的遍历仍需要栈的支持。 A．先序线索树 B．中序线索树 C．后序线索树 D．A 与 B

分析：该题目主要考查线索树的遍历。由于后序 遍历先访问子树后访问根结点，从本质上要求运 行栈中存放祖先的信息，即使对二叉树进行后序 线索化，仍然不能脱离栈的支持对此二叉树进行

遍历，比如图 6.3 所示的后序线索树，没有栈的支持就无法对其进行后序 遍历。

当访问到结点②时，由于没有线索指向②的后序后继③，而且没有指 图6.3后序线索树

针返回到②的父结点④，因此对此二叉线索树的后序遍历无法进行，除非 使用栈。

然而对于先序线索树进行先序遍历或者中序线索树进行中序遍历，则

可以不使用栈就能够遍历，值得提到的是中序线索树，又称为对称线索树，

对它不仅可以方便地进行中序遍历，而且能够在没有栈的支持的情况下， 对其进行先序和后序遍历。所以答案为 C。

18．已知 n 个结点的二叉树具有最小路径长度时，其深度为 k，那么第 k 层 上的结点数为________。

A. n-2 k-2 +1 B. n-2 k-1 +1 C. n-2 k +1 D. n-2 k-1

分析：该题目主要考查二叉树的形态和最小路径长度的关系。结点数确定 的二叉树具有最小路径长度时，形态上类似于完全二叉树，最大层次 k 上 的结点任意分布，其它 k-1 层上的结点构成了一个满二叉树。所以可以根

据二叉树的性质 2，得到从 1 层到 k-1 层上的结点总数为 2 k-1 -1，从而第 k 层上的结点数为 n-2 k-1 +1。答案为 B。 二．判断题

1．按中序遍历二叉树时，某个结点(有右子树)的直接后继是它的右子树中 第一个被访问的结点。 正确

分析：该题目主要考查二叉树的中序遍历。这种说法正确。因为中序遍历 按 LDR 的顺序进行，若以某结点为其直接后继，必须是右子树中第一个被 访问的结点。

2．有 1 个以上结点的二叉树，已知先序和后序遍历序列，能唯一确定一棵 二叉树。 错误

分析：该题目主要考查二叉树的遍历的性质。这种说法不正确。如已知先 序为 12，后序遍历为 21，则可以有两棵二叉树。 图 6.4

两个不同的二叉树

3．完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。 正确

分析：该题目主要考查完全二叉树的逻辑结构。深度为 k 的，有 n 个结点 的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 到 n 的结点一一对应时，称为完全二叉树。根据此定义，若完全二叉树中某结 点无左孩子，则其必定没有右孩子，因此是叶结点。所以这种说法是正确 的。

4．将一棵树转换成二叉树后，根结点没有左子树。 错误

分析：该题目主要考查树和二叉树的转换。树转换成二叉树满足“左孩子， 右兄弟”规则。只有当树结点个数为 1 时，树转换成二叉树后，根结点没 有左子树。

6．用二叉树的先序遍历和中序遍历可以导出二叉树的后序遍历。 正确

分析：该题目主要考查二叉树的遍历和逻辑结构。用二叉树的先序遍历和 中序遍历可以确定二叉树的逻辑结构，就可以进一步导出二叉树的后序遍 历。通常已知二叉树的先序遍历和后序遍历，无法确定一棵二叉树。

7．若一个叶子结点是某二叉树中序遍历序列的最后一个结点，那么它也是 该二叉树的先序遍历序列的最后一个结点。 正确

分析：该题目主要考查二叉树的遍历。当一个叶子结点是某二叉树中序遍 历的最后一个结点，则它一定位于二叉树的右子树上最右端，无论先序遍 历或中序遍历，右子树上的最右端的叶子结点肯定最后访问。若题目中的 叶子结点替换成普通结点，则命题不成立。 三．填空题

1．森林 T 转化为二叉树 B，B 中某结点在森林中为叶子结点的条件为 ___________。

答案：B 中左子树为空的结点

分析：该题目主要考查森林和二叉树的转化。当 B 中左子树为空时，意味 着该结点没有孩子结点。

2．N 个结点的二叉树按某种遍历规则对结点从 1 到 N 依次递增编号，如果 (1) 任一结点的编号等于它的左子树中的最小编号减 1，则为 ___________遍历；

(2) 某结点右子树中最小编号等于左子树中的最大编号加 1，则为 ___________遍历。 答案：先序，后序。

分析：该题目主要考查二叉树的结构和遍历。对于先序遍历，因为首先访 问根结点，再先序遍历左子树，最后先序遍历右子树，所以根结点编号等 于左子树的根结点编号减 1。对于后序遍历，因为首先后序遍历左子树，然 后后序遍历右子树，最后访问根结点，所以右子树中最小编号等于左子树 中的最大编号加 1。

3．一棵高度为 H 的满 K 叉树，按层次从 1 开始编号，则； (1) 第 i 层结点的数目为：___________；

(2) 编号为 n 的结点的父结点的编号为：___________；

(3) 编号为 n 的结点的第 i 个孩子的编号为：___________；

(4) 编号为 n 的结点有右兄弟的条件是：___________，右兄弟的编号 为____________。 答案：(1)K i-1 (2) ?(n-1)/K? (3) K(n-1)+1+i (4)n≤?n-1/K? *K n+1

分析：该题目主要考查对二叉树定义和性质的理解。对满 K 叉树的而言，

它与二叉树的基本性质是相同的，区别是 K 值，当 K=2 时， K 叉树为二叉树。 结合二叉树性质，通过归纳，可以得到上述答案。

4．如果某二叉树中有 30 个叶结点，另有 30 个结点仅有一个孩子结点，则 该二叉树中共有___________个结点。 答案：89

分析：该题目主要考查二叉树结点之间的关系。设 i、j、k 分别为二叉树 中度为 0、1、2 的结点数目，则 n=i+j+k。根据二叉树的性质，i=k+1，有 n=i+j+i-1=30+30+30-1=89，所以二叉树中有个 89 结点。

5．由带权为 3，9，6，2，5 的 5 个叶子结点构成一棵哈夫曼树，则带权路 径长度为_______。 答案：55

分析：该题目主要考查哈夫曼树的概念。解本题的关键是建立这 5 个叶子 结点的哈夫曼树。

6．设 F 是一个森林，B 是由 F 转换得到的二叉树，F 中有 n 个非终端结点， 则 B 中右指针域空的结点有_____个。 答案：n+1

分析：该题目主要考查森林和二叉树的转化。

7．设 n 为哈夫曼树的叶子结点数目，则该哈夫曼树共有___________个结 点。

答案：2n－1

分析：该题目主要考查哈夫曼树的结构。哈夫曼树虽然带有权值，但其形 式仍然是一棵普通的二叉树，二叉树的性质仍然适用于它。不过哈夫曼树 中没有单分支结点，它只有双分支结点和叶结点，因此，由二叉树的性质 可得出一个推论：N＝ 1 2n

。其中，N 表示哈夫曼树的结点总数， n

表示哈夫

曼树中的叶结点数。因此正确答案为 1 2n 。

8．n 个结点的完全二叉树，编号最大的非叶结点是___________号结点，编 号最小的叶结点是___________号结点。 答案：?n/2? ?n/2? +1

分析：该题目主要考查完全二叉树的结构。n 个结点的完全二叉树，编号最 大的叶结点就是 n 号结点，它的双亲结点就是编号最大的非叶结点。根据 完全二叉树的性质，n 的双亲为?n/2?。编号最大的非叶结点的右边一个结 点，即?n/2?+1 号结点，是编号最小的叶结点。

9．完全二叉树的第 7 层有 8 个结点，则此完全二叉树的叶子结点数为____。 768 个结点的完全二叉树有____个叶子结点？19 个结点的哈夫曼树有 ______个叶子结点？ 答案：36 386 10

分析：本题主要考查完全二叉树和哈夫曼树的结构。由性质 1 可知：第 7 层上最多有 2 7-1 =64 个结点。因此，该完全二叉树的第 7 层上有 64-8=56 个 空子树。第 7 层一定是最高层。这样，它共有 56/2+8=36 个叶子结点。 n 个结点完全二叉树的叶子结点数为?n/2?，768/2=386 个叶子结点。 19 个结点的哈夫曼树有叶子结点 n0, 满足 n＝2n0-1，可得叶子结点数为 10。

四．应用题

1．设一棵度为 k 的树中有 n1 个度为 1 的结点， n2 个度为 2 的结点，?， nk 个度为 k 的结点，求该树上有多少叶子结点？

分析与解答：该题目主要考查树的基本概念和结构。 根据两个等式：求结点总数：n=n0+n1+n2+?+nk

求树枝总数：n-1= n1+2n2+?+knk

因此， 0 n =1+ 2 n +2 3 n +… +(k-1) k n =1+? ? k

2 i i ] n ) 1 i [(

2．将图 6.5 所示的树转换为二叉树。

分析与解答：该题目主要考查树和二叉树的转化。 如图 6.6(a,b,c)所示。 图 6.6

3．满足下列条件的非空二叉树具有什么形状？ (1) 先序和中序相同；

(2) 中序和后序相同；○ L ○ I ○ F ○ G ○ H ○ J ○ A ○ C ○ D ○ B ○ E ○ K ○ M 图6.5树

○ L ○ I ○ F ○ G ○ H ○ J ○ A ○ C ○ D ○ B ○ E ○ K ○ M (a) 加线后

(b) 抹线后○ L

○ I ○ F ○ G ○ H ○ J ○ A ○ C ○ D ○ B ○ E ○ K ○ M ○ A

○ C ○ B ○ D ○ F

○ K ○ G ○ E ○ M ○ L ○ H ○ J ○ I (c) 旋转后

(3) 先序和后序相同；

分析与解答：该题目主要考查二叉树的结构和遍历的性质。

(1) 先序和中序相同：只有一个结点或没有左子树的二叉树(右单支树)； (2) 中序和后序相同：只有一个结点或没有右子树的二叉树(左单支树)； (3) 先序和中序相同：只有一个结点的二叉树。

4．已知二叉树左右子树都含有 m 个结点，当 m=3 时，试构造满足如下要求 的所有二叉树。

(1) 左右子树的先序与中序序列相同。

(2) 左子树的中序与后序序列相同，右子树的先序与中序序列相同。

分析与解答：该题目由上题引申得到，主要考查二叉树的结构和遍历的性 质，如图 6.7 所示。 (1) (2) 图 6.7

5．试证明：任一棵高度为 h>1 的二叉树，其内部结点(除根、叶子之外的结 点)的数目小于 2 h-1 -1，而叶子结点数目小于或等于 2 h-1 。 分析与解答：该题目主要考查二叉树的逻辑结构。

性质 2：n≤2 h -1，即 n0+n1+n2≤2 h -1 (a) 性质 3：n0=n2+1 (b)

考查高度为 h 时结点最多的二叉树——满二叉树：其 n1=0。这样，(a) 式简化为：

n0+n2≤2 h -1 (c)

由(b)和(c)，可求得：n0≤2 h-1 ，n2≤2 h-1 -1(n2 中包含一个根结点)，因此， 对于高度为 h(>1)的任意二叉树，叶结点的数目 n0≤2 h-1 (满二叉树时取等 号)；而内部结点的数目=n1+n2-1≤2 h-1 -1+(n1-1)<2 h-1 -1。

6．一棵有11个结点的二叉树的存储情况如图6.8所示， Left[i]和Right[i] 分别为 i 结点左、右孩子，根结点为序号 3 的结点。画出该二叉树并给出先 序、中序和后序遍历该树的结点序列。 1 2 3 4 5 6 7 8 9 10 11

6 ∧ 7 ∧ 8 ∧ 5 ∧ 2 ∧∧ Left[i] m f a k b l c r d s e Data[i]

∧∧ 9 ∧ 10 4 11 ∧ 1 ∧∧ Right[i] 图 6.8 二叉树的存储情况

分析与解答：该题目主要考查二叉树的静态链表存储结构以及二叉树的性 质 5。该二叉树的表示如图 6.9 所示。其各种遍历如下： 先序遍历：acbrsedfmlk 中序遍历：rbsceafdlkm 后序遍历：rsbecfklmda 图 6.9

7．二叉树结点数值采用顺序存储结构，如图 6.10 所示。 图 6.10 顺序存储结构的二叉树

(1)画出二叉树表示； 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 20

e a f d g c j h i b ○ c ○ a ○ b ○ d

○ r ○ l ○ s ○ e ○ m ○ f ○ k

(2)写出先序遍历，中序遍历和后序遍历的结果；

(3)写出结点值 c 的父结点，其左、右孩子； (4)画出把此二叉树和还原成森林的图。

分析与解答：该题目主要考查二叉树的顺序存储结构(即将二叉树看成完全 二叉树)和遍历，着重考察二叉树的性质 5。 (1)该二叉树如图 6.11 所示。 图 6.11

(2)本题二叉树的各种遍历结果如下： 先序遍历：eadcbjfghi 中序遍历：abcdjefhgi 后序遍历：bcjdahigfa

(3)根据二叉树的性质 5 可知，指点值为 c 的存储位置为 10，故其父结点的 位置为 10/2=5，其父结点值为 d；同样，其左孩子的存储位置为 2*10=20， 值为 b，而右孩子的存储位置为 2*10+1=21，值为空，则没有右孩子。 (4)还原成的森林如图 6.12 所示。 图 6.12 图 6.11 所对应的森林 8．对如图 6.13 所示的森林： ○ e

○ a ○ f ○ d ○ g ○ c ○ j ○ h ○ i ○ b

○ f ○ i ○ e ○ a

○ b ○ j ○ d ○ c

○ h ○ g

(1)求各树的先根序列和后根序列。 (2)求森林的前序序列和后序序列。 (3)将此森林转换为相应的二叉树。

(4)给出(a)所示树的双亲表示法、孩子表示法及孩子兄弟表示法等 3 种存 储结构，并指出哪些存储结构易于求祖先，哪些易于求指定结点的后代？ 分析与解答：该题目主要考查树和森林的遍历，森林和二叉树的转换。 (1) 各树的先根序列和后根序列，如表 6-1 所示。 表 6-1 树 a b c

先根序列 ABCDEF GHIJK LMPQRNO 后根序列 BDEFCA IJKHG QRPMNOL (2) 森林的前序序列和后序序列。 前序序列：ABCDEFGHIJKLMPQRNO 后序序列：BDEFCAIJKHGQRPMNOL

(3) 森林所对应的二叉树如图 6.14 所示。

将森林转换为二叉树的方法：各树的根互为兄弟，设左边的孩子为长 子；然后从最左边的树开始，按长子为左孩子、右邻兄弟为右孩子的方法 转换。○ A ○ B ○ C

○ F ○ E ○ D (a) ○ G

○ K ○ J ○ H ○ I (b) ○ L ○ R ○ Q ○ P

○ O ○ N ○ M (c) 图 6.13

(4) ①孩子表示法、双亲表示法、孩子兄弟表示法分别如图 6.15(a,b,c) 所示。

(a) (b) data parent 1 A 0 2 B 1 3 C 1 4 D 3 5 E 3 6 F 3 ○ A ○ L ○ H ○ F ○ C ○

G ○ B ○ K ○ D ○ J ○

I ○ N ○ R ○ E ○ M ○ Q ○ P ○ O

图6.14 由森林转换得到的二叉树 data child 1 A 2 B ∧ 3 C 4 D ∧ 5 E ∧ 6 F ∧ 2 5 4

3 ∧ 6 ∧ ∧ B A ∧ ∧ E ∧ D C ∧ ∧ F ∧ (c)

图 6.15

双亲表示法易于求祖先。孩子表示法、孩子兄弟表示法易于求后代。

9．设二叉树的存储结构如图 6.16 所示，其中 bt 为二叉树的根指针， lchild， rchild 分别为左右孩子的指针域，data 为结点的数据域(存放结点本身的 信息)。请完成下列各步： (1) 画出二叉树的树形结构。

(2) 画出该二叉树的后序线索化二叉树。

分析与解答：该题目主要考查二叉树的存储结构及线索化。 (1) 该二叉树的树形结构图，如图 6.17(a)所示。 图 6.16 二叉树静态链表结构

(2) 后序线索化二叉树如图 6.17(b)所示。

(a) 对应的二叉树 (b)后序线索化 1 2 3 4 5 6 7 8 9 10 lchild 0 0 2 3 7 5 8 0 10 1 data j h f d b a c e g i rchild 0 0 0 9 4 0 0 0 0 0 bt ○ a ○ b

○ f ○ d ○ e ○ c ○ h ○ g ○ j ○ i

图 6.17 第 9 题解答

10．设电文由 6 个字符 A，B，C，D，E，F 组成，它们在电文中出现的次数 分别为：10,4,8,3，2,7。试画出用于编码的哈夫曼树，并列出每个字符的 编码。

分析与解答：该题目主要考查哈夫曼树及应用。对应的哈夫曼树如图 6.18 所示： 图 6.18

对应的哈夫曼编码为 A(10)：11 B(4)：100 C(8)：01 D(3)：1011 E(2)：1010 F(7)：00

11．如图 6.19 所示的哈夫曼树可得到字母 F,G,H,I 和 J 的编码， (1)设某字母串经编码后为“011101011101”，译出原串， (2)说明哈夫曼编码和 ASCII 编码的异同。 (3)为什么采用哈夫曼编码？

分析与解答：该题目主要考查哈夫曼树及应用。 (1) 根据图 6.19，可以得到原串是 GIHJG。

(2) 相同点：都是用 0、1 代码来表示字母或数字。图 6.19

不同点：不同的哈夫曼编码代表一个字母的位数不固定，哈夫曼编码 是前缀编码；ASCII 码是 8 位表示的固定长度的编码。 (3) 采用哈夫曼编 ○ 2 ○ 34 ○ 19

○ 8 ○ 7 ○ 15 ○ 4 ○ 10 ○ 9 ○ 3 ○ 5 0 0 1 1 1 0 1 0

F G H I J

码能提高编码效率，也能提高存储和传输效率。

12．已知二叉树的存储结构为二叉链表，阅读下面算法。

typedef struct node { DateType data;

struct node *next; }ListNode;

typedef ListNode *LinkList; LinkList Leafhead=NULL; void Inorder(BTree T) { LinkList s; if (T)

{ Inorder(T->lchild); 图 6.20 if ((!T->lchild ) && (!T->rchild))

{ s=(ListNode*)malloc(sizeof(ListNode)); s->data=T->data; s->next=Leafhead; Leafhead=s; }

Inorder(T->rchild); } }

对于如图 6.20 所示的二叉树：

(1) 画出执行上述算法后所建立的结构。 (2) 说明该算法的功能。

分析与解答：该题目主要考查二叉树遍历的应用。 ○ E ○ A

○ B ○ C ○ D

○ H ○ F ○ G

(1) 执行上述算法后所建立的结构为如图 6.21 所示的链表。 图 6.21

(2) 该算法的功能是用中序遍历递归算法对二叉树进行遍历，将二叉树 中叶结点数据域的值作为单链表结点的值，并用头插法建立一个以

Leafhead 为头指针的逆序单链表(即按二叉树中叶结点数据从右至左链接 成一个链表)。

13．假设二叉树 t 的结点有 4 个字段，它们分别是：data、1child、rchild、 parent，其中 data 存放结点值，1child 和 rchild 分别指向左子结点和右 子结点，parent 指向父结点。在下列程序中，非递归函数 mid_order(t)实 现了对二叉树 t 的中序遍历。 typedef struct node{ int data;

struct node *lchild, *rchild; struct node *parent; }Node;

void mid_order(Node *t) { Node *p, *q; p=NULL; q=t; do{

while(q!= NULL) { (1) ;

q=q->lchild; F

D ∧ H G

leafhead }

if ( (2) )

{ printf(“]”, p->data); (3) ; }

while (p!= NULL&& q==NULL) { do{ q=p; (4) ;

}while (p!= NULL&& q==p->rchild); if (p!= NULL)

{ printf(“5%d”,p->data); (5) ; } }

}while( (6) )；

printf (“\\n”); }

分析与解答：该题目主要考查二叉树遍历的非递归算法。让 p 为 q 的父指 针，首先沿着二叉树的左孩子指针找到最左下角的孩子，然后判断其左子

树是否为空，不为空则遍历右子树，否则沿着 parent 指针向上，直到 parent 为空为止。

(1)p=q;(2)p(3)q=p->rchild(4)p=q->parent(5)q=p->rchild (6)p

14．一棵以孩子兄弟表示法存储，递归算法 numberofleaf 计算并返回根为 r 的树中叶子结点的个数(NULL 代表空指针)。

typedef struct tnode {

struct tnode *firstson,*nextbrother; }TNode;

int numberofleaf(TNode *r) { int num;

if(r==NULL) num=0;

else if(r->firstson==NULL) num= (1) +

numberrofleaf(r->nextbrother); else (2) ;

return(num); }

分析与解答：该题目主要考查树遍历的应用和孩子兄弟表示法存储结构。 此题要求熟悉树的孩子兄弟表示法与二叉链表的联系和区别，必须了解树

的孩子兄弟表示法中叶结点的特点。若根结点指针为空，则叶结点数目为 0。 只有那些 firstson 为空的结点是叶结点。因而问题的答案为： (1) 1; (2) num=numberofleaf(r->firstson)+ numberofleaf(r->nextbrother)

五．算法设计题

1．已知深度为 h 的二叉树以一维数组 BT[1..2 h -1]作为其存储结构。请写 一算法，求该二叉树中叶结点的个数。

分析：该题目主要考查二叉树的顺序存储结构。以二叉树对应的完全二叉 树的层次次序在数组 BT 中存放二叉树的结点值，若 BT[i]不为零，则完全 二叉树层次次序中第 i 个位置对应的二叉树结点存在，否则，结点不存在。 在二叉树的顺序存储结构中，结点 i 的左孩子(若存在)的编号为 2i，右孩 子(若存在)的编号为 2i+1。对于顺序存储结构的二叉树适合层次遍历。 算法描述如下：

int leafnum(int BT[ ] , int h) { int len,i,count;

len=pow(2,h)-1; /*获取顺序表的长度*/ count=0;

for (i=1;i<=len;i++)

if (BT[i]!=0) /*i 位置存在结点，再判断是否为叶 子结点*/ { if (i*2>len)

/*当前结点的左孩子位置已经大于存储区长度，所以没有孩 子，必定是叶子结点 */ count++;

else if ((BT[i*2+1]==0)&&(BT[i*2]==0))/*当前结点没 有左孩子和右孩子*/ count++; }

本文来源：https://www.bwwdw.com/article/b3vd.html