自测练习题参考答案.docVIP

第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 解：具有三个结点的二叉树有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） 解:: 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．请思考：什么情况下二叉树的先根遍历序列与中根遍历序列相同；什么情况下二叉树的先根遍历序列与后根遍历序列相同？ 解:解： 8．已知遍历某二叉树后的中根遍历序列CDBAFGEIHJ和后根遍历序列DCBGFIJHEA，试画出该二叉树。 解：根据二叉树后的中根遍历和后根遍历的特点，其中根遍历序列和后根遍历序列的形式如下所示： 显然，后根历序列中的最后一个结点就是二叉树的根结点，然后再在中根序列中找出根结点所在位置。根据根结点的位置可以将中根序列划分为两部分，其中在根结点之前的子序列为左子树的中根序列，而根结点之后的子序列为右子树的中根序列。由于左子树的后根序列长度应与中根序列长度相等，因此可以从二叉树的后根历序列中找出左子树的后根序列，同也可以找出右子树的后根序列。 这样，我们可以根据左、右子树的中根序列和后根序列，按照上述方法继续划分，直到划分的子序列为空。在这个划分过程中，可以逐步构造出唯一的一棵二叉树。 构造过程如下图（a）～(f)所示： 解：解：A B D J I E K H G F C 0 A F B D G H 100 C I E B C A C A B C A B B A C A B C 中根遍历序列 后根遍历序列 左子树中根序列中根序列 左子树中根序列中根序列 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) 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) 24 26 58 15 0 32 6 13 地 7 5 6 11 1 1 1 1 21 6 12 0 0 1 0 5 4 9 3 6 0 1 1 2 3 1 0 0 a e i sp y t u 有 18 42