第4章 自测练习题参考答案
1．有一棵树如题图4-1所示，求出树的叶子结点、非终端结点、各结点的度、树的度和树深。
C
解：
（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个。
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)二叉树：。
E
(2)先根遍历序列：EADCBFHGI
中根遍历序列：ABCDEFGHI
后根遍历序列：BCDAGIHFE
6．请思考：什么情况下二叉树的先根遍历序列与中根遍历序列相同；什么情况下二叉树的先根遍历序列与后根遍历序列相同？
解:当二叉树中的各结点只有左孩子结点时，二叉树的先根遍历序列与中根遍历序列相同；
当二叉树只有一个根结点时，二叉树的先根遍历序列与后根遍历序列相同。
7．现有按中根遍历二叉树的结果为：ABC，请画出可以得到这一结果的全部二叉树。
解：
B
8．已知遍历某二叉树后的中根遍历序列CDBAFGEIHJ和后根遍历序列DCBGFIJHEA，试画出该二叉树。
解：根据二叉树后的中根遍历和后根遍历的特点，其中根遍历序列和后根遍历序列的形式如下所示：
左子树中根序列  右子树中根序列  根
    显然，后根历序列中的最后一个结点就是二叉树的根结点，然后再在中根序列中出根结点所在位置。根据根结点的位置可以将中根序列划分为两部分，其中在根结点之前的子序列为左子树的中根序列，而根结点之后的子序列为右子树的中根序列。由于左子树的后根序列长度应与中根序列长度相等，因此可以从二叉树的后根历序列中出左子树的后根序列，同也可以出右子树的后根序列。
这样，我们可以根据左、右子树的中根序列和后根序列，按照上述方法继续划分，直到划分的子序列为空。在这个划分过程中，可以逐步构造出唯一的一棵二叉树。
构造过程如下图（a）～(f)所示：
(c)
(b)
(a)
     
     
(d)
(e)
(f)
11.根据一组权值{1，2，3，4，5，6}构造一棵哈夫曼树，求出其带权路径长度和树深。
解：(1) 哈夫曼树
21
(2) 带权路径长度WPL=（1+2）*4+3*3 +（4+5+6）*2=51
树深：5
12．在一段文字中10个常用汉字及出现的频度如下：
          的  地  得  于  个  和  在  再  是  有
          26  6  4  15  7  6  8  5  18  5
试为这些常用汉字设计哈夫曼编码表。
解：
1
字符
编码
的
10
地
0101
得
11110
于
110
个
0111
和
0110
在
1110
再
11111
是
00
有
0100
0
1
1
1
1
0
0
1
1
0
1
0
0
0
a
e
i
sp
y
t
u

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。