第6章 树和二叉树 作业

《第6章 树和二叉树 作业》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树和二叉树作业1、假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树的树边集合为{(e,i),(b,e),(b,d),(a,b),(g,j),(c,g),(c,f),(h,l),(c,h),(a,c)}，用树型表示法表示该树，并回答下列问题：①哪个是根结点?哪些是叶子结点?哪个是g的双亲?哪些是g的祖先?哪些是g的孩子?那些是e的子孙?哪些是e的兄弟?哪些是f的兄弟?②b和n的层次各是多少?树的深度是多少?以结点c为根的子树的深度是多少?2、一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果

2、按层次顺序(同层自左至右)从1开始对全部结点编号，问：①各层的结点数是多少?②编号为i的结点的双亲结点(若存在)的编号是多少?③编号为i的结点的第j个孩子结点(若存在)的编号是多少?④编号为i的结点的有右兄弟的条件是什么?其右兄弟的编号是多少?3、设有如图6-27所示的二叉树。①分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。②写出该二叉树的先序、中序、后序遍历序列。4、已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵二叉树，然后给出该树的后序遍历序列。5、设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCE

3、AFHG和DECBHGFA，请画出这棵二叉树，然后给出该树的先序序列。6、已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif和gdbkeihfca，请画出这棵二叉树对应的中序线索树和后序线索树。7、以二叉链表为存储结构，请分别写出求二叉树的结点总数及叶子结点总数的算法。8、设图6-27所示的二叉树是森林F所对应的二叉树，请画出森林F。9、设有一棵树，如图6-28所示。①请分别用双亲表示法、孩子表示法、孩子兄弟表示法给出该树的存储结构。②请给出该树的先序遍历序列和后序遍历序列。③请将这棵树转换成二叉树。10、设给定权值集合w={3,5,7,8,11,1

4、2}，请构造关于w的一棵huffman树，并求其加权路径长度WPL。11、假设用于通信的电文是由字符集{a,b,c,d,e,f,g,h}中的字符构成，这8个字符在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。①请画出对应的huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。②求出每个字符的huffman编码。