搜索
⑴假设在树中，结点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的层次各是多少?树的深度是多少?以结点c为根的子树的深度是多少?根节点：a叶子节点：i,d,j,f,lg的双亲节点:cg的祖先：c,ag的孩子：je的子孙：ie的兄弟：df的兄弟：g,hb的层次：2树的深度：4以结点c为根的子树的深度：3⑵一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：①各层的结点数是多少?②编号为i的结点的双亲结点(若存在)的编号是多少?③编号为i的结点的第j个孩子结点(若存在)的编号是多少?④编号为i的结点的有右兄弟的条件是什么?其右兄弟的编号是多少?(1)设层号为i的结点数目为m=k^(i-1)(2)编号为i的结点的双亲结点的编号是：[(i+k-2)/k](不大于(i+k-2)/k的最大整数。也就是(i+k-2)与k整除的结果.以下/表示整除。(3)编号为i的结点的第j个孩子结点编号是：k*(i-1)+1+j;(4)编号为i的结点有右兄弟的条件是(i-1)能被k整除右兄弟的编号是i+1.⑶设有如图6-27所示的二叉树。①分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。②写出该二叉树的先序、中序、后序遍历序列。顺序存储结构：agfedcb00hnm00k链式存储结构abc⋀⋀de⋀⋀fg⋀⋀k⋀⋀h⋀⋀n⋀⋀m先序：abdehkcfgmn中序：dbhekafcmgn后序：dhkebfmngca⑷已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵二叉树，然后给出该树的后序遍历序列。ABCDGHEFI后序：GHDBEIFCA⑸设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG和DECBHGFA，请画出这棵二叉树，然后给出该树的先序序列。ABFCGDEH先序遍历：ABCDEFGH⑹已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif和gdbkeihfca，请画出这棵二叉树对应的中序线索树和后序线索树。二叉树：中序线索树：abcdfgkhei后序线索树：abcdfgkhei⑺以二叉链表为存储结构，请分别写出求二叉树的结点总数及叶子结点总数的算法叶子节点数：#defineMAX_NODE50intsearch_leaves(BTNode*T){BTNode*Stack[MAX_NODE],*p=T;inttop=0,num=0;if(T!=NULL){stack[++top]=p;while(top0){p=stack[top--];if(p-Lchild==NULL&&p-Rchild==NULL)num++;if(p-Rchild!=NULL)stack[++top]=p-Rchild;if(p-Lchild!=NULL)stack[++top]=p-Lchild;NULLNULLNULL}}return(num);}⑻设图6-27所示的二叉树是森林F所对应的二叉树，请画出森林F。森林F：abkedhcfgmn⑼设有一棵树，如图6-28所示。①请分别用双亲表示法、孩子表示法、孩子兄弟表示法给出该树的存储结构。②请给出该树的先序遍历序列和后序遍历序列。③请将这棵树转换成二叉树双亲表示法：a-1b0c0m0d1e1h2k2g2f3n3012345678910孩子表示法：abcmd⋀e⋀h⋀k⋀g⋀f⋀n⋀0123456789103⋀1245⋀8⋀67910⋀孩子兄弟表示法：abdcehmkfgn先序：abdechkgmfn后序：edgkhnfmcba二叉树：abdcehmkfng⑽设给定权值集合w={3,5,7,8,11,12}，请构造关于w的一棵huffman树，并求其加权路径长度WPL。12735811WPL=12*2+3*4+5*4+7*3+8*2+11*2=115⑾假设用于通信的电文是由字符集{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编码。0.19(b)0.21(g)0.32(e)0.06(d)0.07(a)0.10(h)0.02(c)0.03(f)然后根据左0右1写出a=1010b=00c=10000d=1001e=11f=10001g=01h=101110101111100000