第4章 自测练习题参考答案
- 格式：doc
- 大小：130.00 KB
- 文档页数：4
第4章 自测练习题参考答案
1．有一棵树如题图4-1所示，求出树的叶子结点、非终端结点、各结点的度、树的度和树深。
解：
（1）叶子结点：E、F、G、H、K、J
（2）非终端结点：A、B、C、D、I
（3）各结点的度：度为3的结点：A、C
度为2的结点：D
度为1的结点：B、I
度为0的结点：E、F、G、H、K、J
（4）树的度：3
（5）树深：4
2．具有三个结点的二叉树有多少种不同的形态?请分别画出。
解：具有三个结点的二叉树有5种不同的形态，如下所示：
3．如果一棵树有n1个度为1的结点，n2个度为2的结点，……，n m个度为m的结点，则该树共有多少个叶子结点?可参考二叉树性质3的证明方法来思考m叉树问题。
解: 设树中有n0 个叶子结点，那么树中总结点数N为：
N＝n0 +n1+…+nm （a）
由于树中除根结点外，其它各结点都有仅有一个分支指向它，所以树中的总结点数恰好比分支数少1。设B为树中总分支数，即有：
B＝N-1
另外，除度为0的结点没有分支外，每个度为k的结点有k个分支，所以总分支数又为：
B＝1×n1+2×n2+…+m×nm
即总结点数为：
N＝n1+2×n2+…+m×nm+1 （b）
由式(a)和式(b)有：
n0 +n1+…+nm＝ n1+2×n2+…+m×nm+1
即得：n0＝1×n2+2×n3+…+（i-1）×ni +（m-1）×nm+1
＝∑（i-1）×ni +1 （i=2～m）
4.已知一棵完全二叉树的第8层有8个结点，请求出该二叉树的叶子结点数。
解:
第7层共有27-1=64个结点，其中4个结点为第8层上的8个结点的双亲结点，故：
该二叉树的叶子结点数=64-4+8=68个。
A
B D
J I E
K H G F C
5.二叉树结点数据采用顺序存储如下所示:
1 2 3 4 5 6 7 8 9 10 … 14 15 … 19 20
E A F D H C G I
B
(1)画出二叉树表示。
(2)写出先根、中根和后根遍历结果。
解: (1)二叉树：。
(2)先根遍历序列：EADCBFHGI
中根遍历序列：ABCDEFGHI
后根遍历序列：BCDAGIHFE
6．请思考：什么情况下二叉树的先根遍历序列与中根遍历序列相同；什么情况下二叉树的先根遍历序列与后根遍历序列相同？
解:当二叉树中的各结点只有左孩子结点时，二叉树的先根遍历序列与中根遍历序列相同；
当二叉树只有一个根结点时，二叉树的先根遍历序列与后根遍历序列相同。
7．现有按中根遍历二叉树的结果为：ABC，请画出可以得到这一结果的全部二叉树。
解：
8．已知遍历某二叉树后的中根遍历序列CDBAFGEIHJ和后根遍历序列DCBGFIJHEA，试画出该二叉树。
解：根据二叉树后的中根遍历和后根遍历的特点，其中根遍历序列和后根遍历序列的形式如下所示：
显然，后根历序列中的最后一个结点就是二叉树的根结点，然后再在中根序列中找出根结点所在位置。根据根结点的位置可以将中根序列划分为两部分，其中在根结点之前的子序列为左子树的中根序列，而根结点之后的子序列为右子树的中根序列。由于左子树的后根序中根遍历序列：
后根遍历序列： 左子树中根序列 根 右子树中根序列
左子树中根序列 右子树中根序列 根 C
B
A C
A
B B A
C B
A C A
C B I H
G D
B F
C A E 列长度应与中根序列长度相等，因此可以从二叉树的后根历序列中找出左子树的后根序列，同也可以找出右子树的后根序列。
这样，我们可以根据左、右子树的中根序列和后根序列，按照上述方法继续划分，直到划分的子序列为空。在这个划分过程中，可以逐步构造出唯一的一棵二叉树。
构造过程如下图（a）～(f)所示：
11.根据一组权值{1，2，3，4，5，6}构造一棵哈夫曼树，求出其带权路径长度和树深。
解：(1) 哈夫曼树
(2) 带权路径长度WPL=（1+2）*4+3*3 +（4+5+6）*2=51
树深：5
A
C
D
B F
G
E
I
H
J
(a) B A
F
G
E
I
H
J C
D
(b) C
D B A
F
G
E
I
H
J
(c)
E
F
G
C
D B A
I
H
J
(d) F
G
E
C
D B A
I
H
J
(e) J H
I F
G E
C
D B A
(f)
3
2 1 6
3 9
4 5 12
6 21 12．在一段文字中10个常用汉字及出现的频度如下：
的 地 得 于 个 和 在 再 是 有
26 6 4 15 7 6 8 5 18 5
试为这些常用汉字设计哈夫曼编码表。
解：
字符 编码
的 10
地 0101
得 11110
于 110
个 0111
和 0110
在 1110
再 11111
是 00
有 0100 0 0
0
有 11
6 5 7 13
6 32
15 58
26 24 100
42
18
17
8 9
5 4 地 和 个 在
得 再 于 是 的
1 0 0
0
0 0
0 1 1
1 1 1 1 1 1
