《1个结点的度为2,其余度为1。2、已知二叉树有50个叶子》.ppt

作业： 1、任意一个有n个结点的二叉树，已知它有m个叶子结点，证明非叶子结点中有m-1个结点的度为2，其余度为1。 2、已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 1、证明：设度为1的结点有n1个，为2的有n2个，则总结点为： n=n1+n2+m 又：n=B+1 B为分支数 B=n1+2n2 则：n=n1+2n2+1 故：n1+n2+m=n1+2n2+1 有：n2=m-1 2、设度为0、1、2的结点数及总结点数分别为n0、n1、n2、n。则： n0=50 n=n0+n1+n2 n-1=n1+2n2 得：n2=49 故：n-1=n1+2*49 n=n1+99 所以当n1=0时，n最少，所以n至少有99个结点。 作业： 1、假定一棵二叉树的广义表表示为(a(b(c),d(e,f)))，分别写出它的先序、中序、后序和层次遍历的结果。 2、已知一棵二叉树的先序和中序序列，求该二叉树的后序序列。 先序：ABCDEFGHIJ 中序：CBAEFDIHJG 3、已知一棵二叉树的中根和后根序列，求该二叉树的深度和度为2、度为1和叶子结点数。 中根：CBDEAGIHJF 后根：CEDBIJHGFA 4、一个二叉树的先序、中序和后序分别如下，其中一部分未显示出来，试求出空格处的内容，并画出该二叉树。 先序：__B__F__ICEH__G 中序：D__KFIA__EJC__ 后序：__K__FBHJ__G__A 答: ABDFKICEHJG DBKFIAHEJCG DKIFBHJEGCA 作业： 1、将二叉树转换为森林。 A B E D C F G H I J 2、将森林转换为二叉树。 1 2 A H I K J C D E F G 3、已知二叉树的结点类型为： typedef struct node { ElemType data; struct node *left,*right; //指向左右孩子 } BTree; 下面函数返回二叉树中值为X的结点所在的层号，补充合适内容。 int NodeLevel(BTree *bt,ElemType X) { if (bt==NULL) return 0; //空树层号为0 else if (bt-data==X) return 1; //根结点层号为1 else { int c1=NodeLevel(bt-left,X); if (c1=1) _____(1)_____; int c2=NodeLevel(bt-right,X); if (c2=1) _____(2)_______; if ____(3)______; else return 0; //若树中不存在X，则返回0 } } c1++; c2++; (c1=1 || c2=1) return c1c2?c1:c2 作业： 1、如果一棵Huffman树T有n0个叶子结点，那么，树T有多少个结点？给出求解过程。 提示：Huffman树只有度为2和0的结点，又n0=n2+1,n=no+n2 故：n=2n0-1 2、有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点构造一棵Huffman树，并计算带权路径长度。 3、在一份电文中共使用了五种字符，即a,b,c,d,e,它们的出现频率依次为4,7,5,2,9,试画出对应的Huffman树，并求出每个字符的Huffman编码。 练习：根据图的邻接矩阵画出图 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 练习：画出下图的关联矩阵 B D A C 1 2 3 4 5 6 A B C D 4 3 2 1 5 6 作业： 1、用邻接矩阵存储图时