数据结构教程李春葆课后答案第7章树和二叉树

第7章树和二叉树教材中练习题及参考答案1.有一棵树的括号表示为A(B，C(E，F(G))，D)，回答下面的问题：（1）指出树的根结点。（2）指出棵树的所有叶子结点。（3）结点C的度是多少？（4）这棵树的度为多少？（5）这棵树的高度是多少？（6）结点C的孩子结点是哪些？（7）结点C的双亲结点是谁？答：该树对应的树形表示如图7.2所示。（1）这棵树的根结点是A。（2）这棵树的叶子结点是B、E、G、D。（3）结点C的度是2。（4）这棵树的度为3。（5）这棵树的高度是4。（6）结点C的孩子结点是E、F。（7）结点C的双亲结点是A。图7.2一棵树2.若一棵度为4的树中度为2、3、4的结点个数分别为3、2、2，则该树的叶子结点的个数是多少？答：结点总数n=n0+n1+n2+n3+n4，又由于除根结点外，每个结点都对应一个分支，所以总的分支数等于n-1。而一个度为i（0≤i≤4）的结点的分支数为i，所以有：总分支数ABCDEFG2数据结构教程学习指导=n-1=1×n1+2×n2+3×n3+4×n4。综合两式得：n0=n2+2n3+3n4+1=3+2×2+3×2=14。3.为了实现以下各种功能，其中x结点表示该结点的位置，给出树的最适合的存储结构：（1）求x和y结点的最近祖先结点。（2）求x结点的所有子孙。（3）求根结点到x结点的路径。（4）求x结点的所有右边兄弟结点。（5）判断x结点是否是叶子结点。（6）求x结点的所有孩子。答：（1）双亲存储结构。（2）孩子链存储结构。（3）双亲存储结构。（4）孩子兄弟链存储结构。（5）孩子链存储结构。（6）孩子链存储结构。4.设二叉树bt的一种存储结构如表7.1所示。其中，bt为树根结点指针，lchild、rchild分别为结点的左、右孩子指针域，在这里使用结点编号作为指针域值，0表示指针域值为空；data为结点的数据域。请完成下列各题：（1）画出二叉树bt的树形表示。（2）写出按先序、中序和后序遍历二叉树bt所得到的结点序列。（3）画出二叉树bt的后序线索树（不带头结点）。表7.1二叉树bt的一种存储结构12345678910lchild00237580101datajhfdbacegirchild0009400000答：（1）二叉树bt的树形表示如图7.3所示。jihgfdecbajihgfdecba第7章树形结构3图7.3二叉树bt的逻辑结构图7.4二叉树bt的后序线索化树（2）先序序列：abcedfhgij中序序列：ecbhfdjiga后序序列：echfjigdba（3）二叉树bt的后序序列为echfjigdba，则后序线索树如图7.4所示。5.含有60个叶子结点的二叉树的最小高度是多少？答：在该二叉树中，n0=60，n2=n0-1=59，n=n0+n1+n2=119+n1，当n1=0且为完全二叉树时高度最小，此时高度h=log2(n+1)=log2120=7。所以含有60个叶子结点的二叉树的最小高度是7。6.已知一棵完全二叉树的第6层（设根结点为第1层）有8个叶子结点，则该完全二叉树的结点个数最多是多少？最少是多少？答：完全二叉树的叶子结点只能在最下面两层，所以结点最多的情况是第6层为倒数第2层，即1～6层构成一棵满二叉树，其结点总数为26-1=63。其中第6层有25=32个结点，含8个叶子结点，则另外有32-8=24个非叶子结点，它们中每个结点有两个孩子结点（均为第7层的叶子结点），计为48个叶子结点。这样最多的结点个数=63+48=111。结点最少的情况是第6层为最下层，即1～5层构成一棵满二叉树，其结点总数为25-1=31，再加上第6层的结点，总计31+8=39。这样最少的结点个数为39。7.已知一棵满二叉树的结点个数为20～40之间，此二叉树的叶子结点有多少个？答：一棵高度为h的满二叉树的结点个数为2h-1，有：20≤2h-1≤40。则h=5，满二叉树中叶子结点均集中在最底层，所以叶子结点个数=25-1=16个。8.已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，给出该二叉树树形表示。答：该二叉树的构造过程和二叉树如图7.5所示。4数据结构教程学习指导图7.5二叉树的构造过程9.给定5个字符a～f，它们的权值集合W={2，3，4，7，8，9}，试构造关于W的一棵哈夫曼树，求其带权路径长度WPL和各个字符的哈夫曼树编码。答：由权值集合W构建的哈夫曼树如图7.6所示。其带权路径长度WPL=(9+7+8)×2+4×3+(2+3)×4=80。各个字符的哈夫曼树编码：a：0000，b：0001，c：001，d：10，e：11，f：01。图7.6一棵哈夫曼树10.假设二叉树中每个结点的值为单个字符，设计一个算法将一棵以二叉链方式存储的二叉树b转换成对应的顺序存储结构a。933151832879541111100000abcfde根：a左中序:cbed，右中序:hgijf左后序:cedb，右后序:hjigf根：b左中序:c，右中序:ed左后序:c，右后序:ed根：c左中序:空，右中序:空左后序:空，右后序:空根：d左中序:e，右中序:空左后序:e，右后序:空根：e左中序:空，右中序:空左后序:空，右后序:空根：f左中序:hgij，右中序:空左后序:hjig，右后序:空根：g左中序:h，右中序:ij左后序:h，右后序:ji根：h左中序:空，右中序:空左后序:空，右后序:空根：j左中序:空，右中序:空左后序:空，右后序:空根：i左中序:空，右中序:j左后序:空，右后序:j第7章树形结构5解：设二叉树的顺序存储结构类型为SqBTree，先将顺序存储结构a中所有元素置为‘#’（表示空结点）。将b转换成a的递归模型如下：f(b，a，i)a[i]='#';当b=NULLf(b，a，i)由b结点data域值建立a[i]元素;其他情况f(b-lchild，a，2*i);f(b-rchild，a，2*i+1)调用方式为：f(b，a，1)（a的下标从1开始）。对应的算法如下：voidCtree(BTNode*b,SqBTreea,inti){if(b!=NULL){a[i]=b-data;Ctree(b-lchild,a,2*i);Ctree(b-rchild,a,2*i+1);}elsea[i]='#';}11.假设二叉树中每个结点值为单个字符，采用顺序存储结构存储。设计一个算法，求二叉树t中的叶子结点个数。解：用i遍历所有的结点，当i大于等于MaxSize时，返回0。当t[i]是空结点时返回0；当t[i]是非空结点时，若它为叶子结点，num增1；否则递归调用num1=LeftNode(t，2*i)求出左子树的叶子结点个数num1，再递归调用num2=LeftNode(t，2*i+1)求出右子树的叶子结点个数num2，置num+=num1+num2。最后返回num。对应的算法如下：intLeftNode(SqBTreet,inti){//i的初值为1intnum1,num2,num=0;if(iMaxSize){if(t[i]!='#'){if(t[2*i]=='#'&&t[2*i+1]=='#')num++;//叶子结点个数增1else{num1=LeftNode(t,2*i);num2=LeftNode(t,2*i+1);num+=num1+num2;}returnnum;}elsereturn0;}elsereturn0;}12.假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法计算一棵给定二叉树b中的所有单分支结点个数。解：计算一棵二叉树的所有单分支结点个数的递归模型f(b)如下：f(b)=0若b=NULL6数据结构教程学习指导f(b)=f(b-lchild)+f(b-rchild)+1若b结点为单分支f(b)=f(b-lchild)+f(b-rchild)其他情况对应的算法如下：intSSonNodes(BTNode*b){intnum1,num2,n;if(b==NULL)return0;elseif((b-lchild==NULL&&b-rchild!=NULL)||(b-lchild!=NULL&&b-rchild==NULL))n=1;//为单分支结点elsen=0;//其他结点num1=SSonNodes(b-lchild);//递归求左子树中单分支结点数num2=SSonNodes(b-rchild);//递归求右子树中单分支结点数return(num1+num2+n);}上述算法采用的是先序遍历的思路。13.假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法求二叉树b中最小值的结点值。解：设f(b，min)是在二叉树b中寻找最小结点值min，其递归模型如下：f(b，min)不做任何事件若b=NULLf(b，min)当b-datamin时置min=b-data;其他情况f(b-lchild，min);f(b-rchild，min);对应的算法如下：voidFindMinNode(BTNode*b,char&min){if(b-datamin)min=b-data;FindMinNode(b-lchild,min);//在左子树中找最小结点值FindMinNode(b-rchild,min);//在右子树中找最小结点值}voidMinNode(BTNode*b)//输出最小结点值{if(b!=NULL){charmin=b-data;FindMinNode(b,min);printf(Min=%c\n,min);}}14.假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法将二叉链b1复制到二叉链b2中。解：当b1为空时，置b2为空树。当b1不为空时，建立b2结点（b2为根结点），置b2-data=b1-data；递归调用Copy(b1-lchild，b2-lchild)，由b1的左子树建立b2的左子树；递归调用Copy(b1-rchild，b2-rchild)，由b1的右子树建立b2的右子树。对应的算法如下：第7章树形结构7voidCopy(BTNode*b1,BTNode*&b2){if(b1==NULL)b2=NULL;else{b2=(BTNode*)malloc(sizeof(BTNode));b2-data=b1-data;Copy(b1-lchild,b2-lchild);Copy(b1-rchild,b2-rchild);}}15.假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法，求二叉树b中第k层上叶子结点个数。解：采用先序遍历方法，当b为空时返回0。置num为0。若b不为空，当前结点的层次为k，并且b为叶子结点，则num增1，递归调用num1=LevelkCount(b-lchild，k，h+1)求出左子树中第k层的结点个数num1，递归调用num2=LevelkCount(b-rchild，k，h+1)求出右子树中第k层的结点个数num2，置num+=num1+num2，最后返回num。对应的算法如下：intLevelkCount(BTNode*b,intk,inth){//h的初值为1intnum1,num2,num=0;if(b!=NULL){if(h==k&&b-lchild==NULL&&b-rchild==NULL)num++;num1=LevelkCount(b-lchild,k,h+1);num2=LevelkCount(b-rchild,k,h+1);num+=num1+num2;returnnum;}return0;}intLevelkleft(BTNode*b,intk//返回二叉树b中第k层上叶子结点个数{returnLevelkCount(b,k,1);}16.假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计