叉树作业解答.docVIP

二叉树作业解答 计科1304 周华毅 201308010411 1、定义一个结点的度数(degree)为其非空子结点的数目。作为满二叉树定理的推论，用归纳法证明任何二叉树中度数为 2的结点数目为叶结点数目减 1。 证明：设二叉树中度数为2的结点的个数为N2，叶结点的个数为N0 初始情况：N2=0，也就是没有度数为2的结点的非空二叉树只有一个叶结点，或者有一个度数为1的根结点和一个叶结点，显然此时N2=N0-1；N2=1，也就是有一个度数为2的根结点和两个叶结点，显然此时N2=N0-1也成立。 归纳假设：假设任意一棵有n-1个度数为 2的结点非空二叉树T有n个叶结点。 归纳步骤：假设树T有n个度数为 2的结点，再分两种情况讨论： (一)、假设树T至少有一个左右子结点均为叶结点的度数为 2的结点I，现在将其两个叶结点去掉，则结点I变为叶结点，并设变为树T’，由归纳假设可知，树T’ 有n-1个度数为 2的结点，有n个叶结点。所以再回过头来把度数为2的结点I加上，变回树T，则度数为 2的结点数加1，变为n个，而叶结点加2，但是由于树T’的叶结点I变为了度数为 2的结点，所以叶结点数要再减1，总个数为n+1个。结论成立。 (二)、假设树T没有一个左右子结点均为叶结点的度数为 2的结点，实际上此时度数为2的结点与叶结点之间不管有多少个度数为1的结点，都可以等同于情况一，可以发现分析过程中并未涉及到度数为1的结点，所以情况二中结论也是成立的。 综上所述：任何二叉树中度数为 2的结点数目为叶结点数目减 1。 2、编写一个递归函数 search ，传入参数为一棵二叉树（不是二叉查找树）和一个值K，如果值K出现在树中则返回true,否则返回false。 解： Template class Key, class Elem , class KEComp Bool search (BinNode Elem * subroot, Key K ){ if(subroot==NULL) return false; else if(subroot-data==K) return true; else return search(subroot-left,K)search(subroot-right,K); } 3、编写一个递归函数计算二叉树的高度。 解： 运用递归函数实现左子树和右子树的深度探索，先遍历二叉树的左子树，然后遍历右子树，以此循环下去，直到左右子树的子树都为空时，比较左右子树的深度，最后得出结果。 templateclassElem int height(BinNodeElem*subroot){ if(subroot==NULL) return 0; //Empty subtree return 1+max(height(subroot-left()),height(subroot-right())); } 4、画出对下列存储于数组中的值执行 buildheap后得到的最大值堆： 10 5 12 3 2 1 8 7 9 4 解： 一共进行了5次交换，依次是（9-3），（4-2），（12-10），（9-5），（7-5） 5、假设某字母表各个字母的权如下： Q Z F M T S O E 2 3 10 10 10 15 20 30 (a)按照这个字母表，一个包含n个字母的字符串采用Huffman编码在最差情况下需要多少位？怎样的串会出现最差情况？ (b)按照这个字母表，包含n个字母的字符串采用 Huffman编码在最佳情况下需要多少位？怎样的串会出现最佳情况？ (c)按照一个字母表，一个字母平均需要多少位？ 解：根据以上各个字母的权值建立的Huffman树如下图所示 (a)由图可知，当字符串由五位编码的字母Q、Z组成时，会出现最坏情况； 一个包含n个字母的字符串采用Huffman编码在最差情况下需要5n位 (b)由图可知，当字符串由两位编码的字母O、E组成时，会出现最佳情况； 一个包含n个字母的字符串采用Huffman编码在最佳情况下需要2n位 (c)先计算字母的权值和各自位数的乘积累加和 A=（30x2）+（20x2）+（15x3）+（10x3）+(10x3)+（10x4）+（3x5）+(2x5)=270 再计算各个字母的权值累加和 B=30+20+15+10+10+10+3+2=100 所以，一个字母平均需要的位数P=A/B=2.7