第六章树习题答案

第六章树习题答案一、基础知识题6.1.假设在树中，结点x是结点y的双亲时,用(x,y)来表示树边.已知一棵树边的集合为{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法出此树，并回答下列问题：(1)哪个是根结点?(2)哪些是叶结点?(3)哪个是g的双亲?(4)哪些是g的祖先?(5)哪些是g的孩子?(6)哪些是e的子孙?(7)哪些是e的兄弟?哪些是f的兄弟?(8)结点b和n的层次各是多少?(9)树的深度是多少?(10)以结点c为根的子树的深度是多少?(11)树的度数是多少?a是根结点；dmnfjkl是叶结点；c是g的双亲；c,a是g的祖先；j,k是g的孩子；imn是e的子孙；d是e的兄弟；g,h是f的兄弟；b的层次是2；n的层次是5；树的深度是5；以c为根的子树深度是3；树的度数是3；6.2一棵度为2的有序树与一棵二叉树有何区别?答：一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。6.3试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。6.4已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，...nm个度为m的结点，问该树中有多少片叶子?解：设该树中的叶子数为n0个。该树中的总结点数为n个，则有：n=n0+n1+n2+…+nm(1)又有除根结点外，树中其他结点都有双亲结点，且是唯一的(由树中的分支表示)，所以，有双亲的结点数为：n-1=0*n0+1*n1+2*n2+…+m*nm(2)联立(1)(2)方程组可得：叶子数为：n0=1+0*n1+1*n2+2*n3+...+(m-1)*nm6.5一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：(1)各层的结点数目是多少?(2)编号为i的结点的双亲结点(若存在)的编号是多少?(3)编号为i的结点的第j个孩子结点(若存在)的编号是多少?(4)编号为i的结点的有右兄弟的条件是什么?其右兄弟的编号是多少?解：(1)层号为h的结点数目为kh-1(2)编号为i的结点的双亲结点的编号是：|_(i-2)/k_|+1(不大于(i-2)/k的最大整数。也就是(i-2)与k整除的结果.以下/表示整除。(3)编号为i的结点的第j个孩子结点编号是：k*(i-1)+1+j;(4)编号为i的结点有右兄弟的条件是(i-1)能被k整除右兄弟的编号是i+1.6.6高度为h的完全二叉树至少有多少个结点?至多有多少个结点?解：高度为h的完全二叉树至少有2h-1个结点，至多有2h-1个结点(也就是满二叉树)。6.7在具有n个结点的k叉树(k=2)的k叉链表表示中，有多少个空指针?解：n个结点的K叉树共有n*k个指针域，已使用的指针域为n-1,所以空指针的个数为：n(k-1)+1;6.8假设二叉树包含的结点数据为1，3，7，12。(1)画出两棵高度最大的二叉树；(2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。解：(1)高度最大的两棵二叉树如图：○1○1/\○3○3/\○7○7/\○2○2/\○12○12(2)两棵完全二叉树如下：○12○12/\/\○7○3○7○3/\/\○1○2○2○16.9试找出分别满足下面条件的所有二叉树：(1)前序序列和中序序列相同；(2)中序序列和后序序列相同；(3)前序序列和后序序列相同；(4)前序、中序、后序序列均相同。答：(1)前序序列和中序序列相同的二叉树是：空二叉树或没有左子树的二叉树(右单支树)。(2)中序序列和后序序列相同的二叉树是：空二叉树或没有右子树的二叉树(左单支树)。(3)前序序列和后序序列相同的二叉树是：空二叉树或只有根的二叉树。(4)前序、中序、后序序列均相同的二叉树：空树或只有根结点的二叉树。6.10试采用顺序存储方法和链接存储方法分别画也6.30所示各二叉树的存储结构。解：(2)链式存储结构：6.11分别写出图6.30(下图)所示各二叉树的前序、中序和后序序列。解：(a)前序序列：12345中序序列：24531后序序列：54321(b)前序序列：12345中序序列：13542后序序列：54321(c)前序序列：12357864中序序列：17583524后序序列：78563421(d)前序序列：124735689中序序列：742153896后序序列：7425896316.12若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。(1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。(2)已知一棵二叉树的在序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。(3)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。解：(1)已知二叉树的前序序列为ABDGHCEFI和中序序列GDHBAECIF，则可以根据前序序列找到根结点为A，由此，通过中序序列可知它的两棵子树包分别含有GDHB和ECIF结点，又由前序序列可知B和C分别为两棵子树的根结点...以此类推可画出所有结点：○A/\○B○C//\○D○E○F/\/○G○H○I(2)以同样的方法可画出该二叉树：○A/\○B○F\\○C○G/\\○D○E○H(3)这两棵不同的二叉树为：○A○A/\○B○B6.13对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出此二叉树。解：类似于上一题的分析方法，可画出二叉树的所有结点：○A/\○B○C/\\○D○E○F/\/G○H○○I\○J6.14试画出图6.30(下图)所示各二叉树的前序、中序和后序线索树及相应的线索链表。答：略6.15在何种线索树中，线索对求指定结点在相应次序下的前趋和后继并无帮助?答：分别在前序线索二叉树和后序线索二叉树中查找前趋和后继时，线索无帮助作用。6.16对图6.31所示的森林：(1)求各树的前序序列和后序序列；(2)求森林的前序序列和后序序列；(3)将此森林转换为相应的二叉树；(4)给出(a)所示树的以亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代?解：(1)(a)的前序序列：ABCDEF后序序列：BDEFCA(b)的前序序列：GHIJK后序序列：IJKHG(c)的前序序列：LMPQRNO后序序列：QRPMNOL(2)此森林的前序序列：ABCDEFGHIJKLMPQRNO01345678902345790123456789*123456789012345678012345689023456789*1234567890123456789*1234567890123456789*12345678901234567890123456789此森林的后序序列：BDEFCAIJKHGQRPMNOL(3)森林转化为二叉树的过程见动画：(4)略6.17画出图6.32(下图)所示的各二叉树所对应的森林。解：各二叉树所对应森林如下：(a)○A(b)○A/○B/○C(c)○A○B○C(d)○A○C|○B(e)○A○C○F○I/\|○B○E○L/|\○D○H○K||○G○J6.18高度为h的严格二叉树至少有多少个结点?至多有多少个结点?答：所谓严格二叉树是指该树中没有度数为1的分支结点的二叉树。所以：高度为h的的严格二叉树至少有2h-1个结点；至多有2h-1个结点(即满二叉树)。6.19在什么样的情况下，等长编码是最优的前缀码?答:在每个字符的使用概率相同的情况下，也即在哈夫曼树中每片叶子的权重相等的时候，等长编码是最优的前缀码。6.20下述编码哪一组不是前缀码?{00,01,10,11},{0,1,00,11},{0,10,110,111}答：第二组不是前缀码。因为0，1分别是00和11的前缀。(前缀码是指该编码集中的任一编码不是其他编码的前缀)6.21假设用于通信的电文由字符集{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}.(1)为这8个字母设计哈夫曼编码。(2)若用这三位二进制数(0…7)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?解：(1)哈夫曼编码根据上图可得编码表：a:1001b:01c:10111d:1010e:11f:10110g:00h:1000(2)用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.612.61/3=0.87=87%其平均码长是等长码的87%。所以平均压缩率为13%。二、算法设计题6.22二叉树的遍历算法可写为通用形式。例如通用的中序遍历为：voidInorder(BinTree,T,void(*visit)(DataTypex)){if(T){Inorder(T-lchild,Visit);//遍历左子树Visit(T-data);//通过函数指针调用它所指的函数来访问结点Inorder(T-rchild,Visit);//遍历右子树}}其中Visit是一个函数指针，它指向形如voidf(DataTypex)的函数。因此我们可以将访问结点的操作写在函数f中通过调用语句Inorder(root,f)将f的地址传递给Visit,来执行遍历操作。请写一个打印结点数据的函数，通过调用上述算法来完成书中6.3节的中序遍历。解：函数如下：voidPrintNode(BinTreeT){printf(%c,T-data);}//定义二叉树链式存储结构typedefcharDataType;//定义DataType类型typedefstructnode{DataTypedata;structnode*lchild,*rchild;//左右孩子子树}BinTNode;//结点类型typedefBinTNode*BinTree;//二叉树类型voidInorder(BinTreeT,void(*Visit)(DataTypex)){if(T){Inorder(T-lchild,Visit);//遍历左子树Visit(T-data);//通过函数指针调用它所指的函数访问结点Inorder(T-rchild,Visit);//遍历右子树}}6.23以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。解：(1)求结点数的递归定义为：若为空树，结点数为0若只有根结点，则结点数为1；否则，结点数为根结点的左子树结点数+右子树结点数+1(2)求叶子数的递归定义为：若为空树，叶子数为0若只有根结点，则叶子数为1；否则，叶子数为根结点的左子树叶子数+右子树叶子数typedefcharDataType;//定义DataType类型typedefstructnode{DataTypedata;structnode*lchild,*rchild;//左右孩子子树}BinTNode;//结点类型typedefBinTNode*BinTree;//二叉树类型intNode(BinTreeT){//算结点数if(T)if(T-lchi