已知它有m个叶子结点,证明非叶子结点中有m-1个结点的.ppt

《已知它有m个叶子结点,证明非叶子结点中有m-1个结点的.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、作业：1、任意一个有n个结点的二叉树，已知它有m个叶子结点，证明非叶子结点中有m-1个结点的度为2，其余度为1。2、已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？1、证明：设度为1的结点有n1个，为2的有n2个，则总结点为：n=n1+n2+m又：n=B+1B为分支数B=n1+2n2则：n=n1+2n2+1故：n1+n2+m=n1+2n2+1有：n2=m-12、设度为0、1、2的结点数及总结点数分别为n0、n1、n2、n。则：n0=50n=n0+n1+n2n-1=n1+2n2得：n2=49故：n-

2、1=n1+2*49n=n1+99所以当n1=0时，n最少，所以n至少有99个结点。10/7/2021作业：1、假定一棵二叉树的广义表表示为(a(b(c),d(e,f)))，分别写出它的先序、中序、后序和层次遍历的结果。2、已知一棵二叉树的先序和中序序列，求该二叉树的后序序列。先序：ABCDEFGHIJ中序：CBAEFDIHJG3、已知一棵二叉树的中根和后根序列，求该二叉树的深度和度为2、度为1和叶子结点数。中根：CBDEAGIHJF后根：CEDBIJHGFA4、一个二叉树的先序、中序和后序分别如下，其中一部分未显

3、示出来，试求出空格处的内容，并画出该二叉树。先序：__B__F__ICEH__G中序：D__KFIA__EJC__后序：__K__FBHJ__G__A答:ABDFKICEHJGDBKFIAHEJCGDKIFBHJEGCA10/7/2021作业：1、将二叉树转换为森林。ABEDCFGHIJ2、将森林转换为二叉树。12AHIKJCDEFG10/7/20213、已知二叉树的结点类型为：typedefstructnode{ElemTypedata;structnode*left,*right;//指向左右孩子}BTree

4、;下面函数返回二叉树中值为X的结点所在的层号，补充合适内容。intNodeLevel(BTree*bt,ElemTypeX){if(bt==NULL)return0;//空树层号为0elseif(bt->data==X)return1;//根结点层号为1else{intc1=NodeLevel(bt->left,X);if(c1>=1)_____(1)_____;intc2=NodeLevel(bt->right,X);if(c2>=1)_____(2)_______;if____(3)______;elsere

5、turn0;//若树中不存在X，则返回0}}c1++;c2++;(c1>=1

6、

7、c2>=1)returnc1>c2?c1:c210/7/2021作业：1、如果一棵Huffman树T有n0个叶子结点，那么，树T有多少个结点？给出求解过程。提示：Huffman树只有度为2和0的结点，又n0=n2+1,n=no+n2故：n=2n0-12、有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点构造一棵Huffman树，并计算带权路径长度。3、在一份电文中共使用了五种字符，即a,b,c,d,e,它们

8、的出现频率依次为4,7,5,2,9,试画出对应的Huffman树，并求出每个字符的Huffman编码。10/7/2021练习：根据图的邻接矩阵画出图10/7/2021练习：画出下图的关联矩阵BDAC123456ABCD43215610/7/2021作业：1、用邻接矩阵存储图时，矩阵元素个数与顶点个数是否相关？与边的条数是否有关？（与顶点相关，与边无关）2、在什么情况下，Prim算法和Kruskual算法生成不同的最小生成树？（具有相同权的边时）3、给出一个带权图的邻接矩阵（

9、顶点编号1~8），如下：10/7/2021(1)给出在该图上从顶点1出发进行DFS遍历的结果序列，并根据此判断该图是否为连通图？(2)画出该图的邻接链表。(3)画出按Prim算法构造的最小生成树（森林）。4、给定如下网G（顶点编号1~6）。(1)画出该图的邻接链表存储结构。(2)根据该图的邻接链表存储结构，从顶点1出发，调用BFS和DFS算法遍历该图，给出可能经过的顶点序列。(3)给出采用Kruskual算法构造最小生成树的过程。164352910561187710/7/2021作

10、业：1、某带权有向图及其邻接链表如图。(1)给出深度优先搜索顺序。(2)将该图作为AOE网，写出C的最早开始时间和活动FC的最晚开始时间。(3)用Dijstral算法计算源点A到其它各点的最短路径；BCEADFG12333211151234ACDB5EFG67B1C2D3^C3E1^E2^F3^G1^C1G5^^10/7/2021答案：DFS结果：ABCEGDFC的最早开