【2017年整理】第4章 自测练习题参考答案.doc

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