第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）树深：42．具有三个结点的二叉树有多少种不同的形态?请分别画出。解：具有三个结点的二叉树有5种不同的形态，如下所示：3．如果一棵树有n1个度为1的结点，n2个度为2的结点，……，nm个度为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个。ABDJIEKHGFC5.二叉树结点数据采用顺序存储如下所示:12345678910…1415…1920EAFDHCGIB(1)画出二叉树表示。(2)写出先根、中根和后根遍历结果。解:(1)二叉树：。(2)先根遍历序列：EADCBFHGI中根遍历序列：ABCDEFGHI后根遍历序列：BCDAGIHFE6．请思考：什么情况下二叉树的先根遍历序列与中根遍历序列相同；什么情况下二叉树的先根遍历序列与后根遍历序列相同？解:当二叉树中的各结点只有左孩子结点时，二叉树的先根遍历序列与中根遍历序列相同；当二叉树只有一个根结点时，二叉树的先根遍历序列与后根遍历序列相同。7．现有按中根遍历二叉树的结果为：ABC，请画出可以得到这一结果的全部二叉树。解：8．已知遍历某二叉树后的中根遍历序列CDBAFGEIHJ和后根遍历序列DCBGFIJHEA，试画出该二叉树。解：根据二叉树后的中根遍历和后根遍历的特点，其中根遍历序列和后根遍历序列的形式如下所示：显然，后根历序列中的最后一个结点就是二叉树的根结点，然后再在中根序列中找出根结点所在位置。根据根结点的位置可以将中根序列划分为两部分，其中在根结点之前的子序列为左子树的中根序列，而根结点之后的子序列为右子树的中根序列。由于左子树的后根序中根遍历序列：后根遍历序列：左子树中根序列根右子树中根序列左子树中根序列右子树中根序列根CBACABBACBACACBIHGDBFCAE列长度应与中根序列长度相等，因此可以从二叉树的后根历序列中找出左子树的后根序列，同也可以找出右子树的后根序列。这样，我们可以根据左、右子树的中根序列和后根序列，按照上述方法继续划分，直到划分的子序列为空。在这个划分过程中，可以逐步构造出唯一的一棵二叉树。构造过程如下图（a）～(f)所示：11.根据一组权值{1，2，3，4，5，6}构造一棵哈夫曼树，求出其带权路径长度和树深。解：(1)哈夫曼树(2)带权路径长度WPL=（1+2）*4+3*3+（4+5+6）*2=51树深：5ACDBFGEIHJ(a)BAFGEIHJCD(b)CDBAFGEIHJ(c)EFGCDBAIHJ(d)FGECDBAIHJ(e)JHIFGECDBA(f)321639451262112．在一段文字中10个常用汉字及出现的频度如下：的地得于个和在再是有2664157685185试为这些常用汉字设计哈夫曼编码表。解：字符编码的10地0101得11110于110个0111和0110在1110再11111是00有0100000有1165713632155826241004218178954地和个在得再于是的100000011111111