树与二叉树习题参考答案

习题五参考答案备注：红色字体标明的是与书本内容有改动的内容一、选择题.对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行（B）遍历操作相同。先根 B.中根C.后根 D.层次.在哈夫曼树中，任何一个结点它的度都是（C）。0或1 B.1或2C.0或2 D.0或1或2.对一棵深度为h的二叉树，其结点的个数最多为（D）。2h B.2h-1 C.2h-1 D.2h-1.一棵非空二叉树的先根遍历与中根遍历正好相同，则该二叉树满足（A）所有结点无左孩子 B.所有结点无右孩子C.只有一个根结点 D.任意一棵二叉树一棵非空二叉树的先根遍历与中根遍历正好相反，则该二叉树满足（B）A.所有结点无左孩子 B.所有结点无右孩子C.只有一个根结点 D.任意一棵二叉树6.假设一棵二叉树中度为1的结点个数为5,度为2的结点个数为3,则这棵二叉树的叶结点的个数是（C）A.2 B.3C.4 D.5.若某棵二叉树的先根遍历序列为ABCDEF,中根遍历序列为CBDAEF,则这棵二叉树的后根遍历序列为（B）。A.FEDCBA B.CDBFEA C.CDBEFA D.DCBEFA.若某棵二叉树的后根遍历序列为DBEFCA,中根遍历序列为DBAECF,则这棵二叉树的先根遍历序列为（B）。A.ABCDEF B.ABDCEF C.ABCDFE D.ABDECF.根据以权值为｛2,5,7,9,12｝构造的哈夫曼树所构造的哈夫曼编码中最大的长度为（B）A.2 B.3C.4 D.510.在有n个结点的二叉树的二叉链表存储结构中有（C）个空的指针域。A.n-1 B.nC.n+1 D.0二、填空题在一棵度为m的树中，若度为1的结点有n1个，度为2的结点有n2个，……，度为m的结点有nm个，则这棵树中的叶结点的个数为1+n2+2n3+3n4+•••+（m-1）nm。一棵具有n个结点的二叉树，其深度最多为n，最少为[log2n]+1。一棵具有100个结点的完全二叉树，其叶结点的个数为50。37以｛5,9,12,13,20,30｝为叶结点的权值所构造的哈夫曼树的带权路径长度是217。有m个叶结点的哈夫曼树中，结点的总数是2m-1。若一棵完全二叉树的第4层（根结点在第0层）有7个结点，则这棵完全二叉树的结点总数是11。22在深度为k的完全二叉树中至少有k个结点，至多有2k-1个结点。对一棵树转换成的二叉树进行先根遍历所得的遍历序列为ABCDEFGH,则对这棵树进行先根遍历所得的遍历序列为ABCDEFGH。二叉树常用的存储结构是二叉链式存储结构，树常用的存储结构是孩子兄弟链表存储结构。对森林进行后根遍历操作等同于从左到右对森林中的每一棵树进行后根遍历操作，并且对森林的后根遍历序列与对森林所对应的二叉树的中根遍历序列相同。四、算法设计题编写一个基于二叉树类的统计叶结点数目的成员函数。参考答案：publicintcountLeafNode(BiTreeNodeT){//统计叶结点数目intcount=0;if(T!=null){if(T.getLchild()==null&&T.getRchild()==null){++count;//叶结点数增1}else{count+=countLeafNode(T.getLchild());//加上左子树上叶结点数count+=countLeafNode(T.getRchild());//加上右子树上的叶结点数}}returncount;}编写一个基于二叉树类的查找二叉树结点的成员函数。参考答案：publicBiTreeNodesearchNode(BiTreeNodeT,Objectx){//在以T为根结点的二叉树中查找值为x的结点，若找到，则返回该结点，否则返回空值if(T!=null){if(T.getData().equals(x))returnT;else{BiTreeNodelresult=searchNode(T.getLchild(),x);//在左子树上查找return(lresult!=null?lresult:searchNode(T.getRchild(),x));//若左子树上没找到，则到右子树上找}}returnnull;}编写算法求一棵二叉树的根结点root到一个指定结点p之间的路径并输出。参考答案：//求根结点到指定结点的路径过程中，采用了后踉遍历的思想，最终求得的路径保存在一个链栈中，其中根结点处于栈顶位置，指定结点处于栈底位置。//下面用到的二叉树结点类BiTreeNode在书中第5章中已给出publicLinkStackgetPath(BiTreeNoderoot,BiTreeNodep){BiTreeNodeT=root;LinkStackS=newLinkStack();//构造链栈if(T!=null){S.push(T);//根结点进栈Booleanflag;//访问标记BiTreeNodeq=null;//q指向刚被访问的结点while(!S.isEmpty()){while(S.peek()!=null)//将栈顶结点的所有左孩子结点入栈S.push(((BiTreeNode)S.peek()).getLchild());S.pop();//空结点退栈while(!S.isEmpty()){T=(BiTreeNode)S.peek();//查看栈顶元素if(T.getRchild()==null||T.getRchild()==q){if(T.equals(p)){//对栈S进行倒置，以保证根结点处于栈顶位置LinkStackS2=newLinkStack();while(!S.isEmpty())S2.push(S.pop());returnS2;)S.pop();//移除栈顶元素q=T;//q指向刚被访问的结点flag=true;//设置访问标记}else{S.push(T.getRchild());//右孩子结点入栈flag=false;//设置未被访问标记}if(!flag)break;}}}returnnull;}编写算法统计树(基于孩子兄弟链表存储结构)的叶子数目。参考答案：//下面用到的孩子兄弟链表结构中的结点类CSTreeNode在书中第5章中已给出publicintcountLeafNode(CSTreeNodeT){intcount=0;if(T!=null){if(T.getFirstchild()==null)++count;//叶结点数增1elsecount+=countLeafNode(T.getFirstchild());//加上孩子上叶结点数count+=countLeafNode(T.getNextsibling());//加上兄弟上叶结点数}returncount;}编写算法计算树(基于孩子兄弟链表存储结构)的深度。参考答案：publicinttreeDepth(CSTreeNodeT){if(T!=null){inth1=treeDepth(T.getFirstchild());inth2=treeDepth(T.getNextsibling());returnh1+1>h2?h1+1:h2;)return0;)四、上机实践题编写一个程序实现：先建立两棵以二叉链表存储结构表示的二叉树，然后判断这两棵二叉树是否相等并输出测试结果。参考答案：packagech05Exercise;importch05.BiTreeNodeJ微材第5章中有此类的描述publicclassExercise5_4_1{publicbooleanisEqual(BiTreeNodeT1,BiTreeNodeT2){〃判断两棵树是否相等，若相等则返回true,否则返回falseif(T1==null&&T2==null)//同时为空returntrue;if(T1!=null&&T2!=null)//同时非空进行比较if(T1.getData().equals(T2.getData()))//根结点数据元素是否相等if(isEqual(T1.getLchild(),T2.getLchild()))//左子树是否相等if(isEqual(T1.getRchild(),T2.getRchild()))//右子树是否相等returntrue;returnfalse;)//测试主方法publicstaticvoidmain(String[]args){//创建根结点为T1的二叉树BiTreeNodeD1=newBiTreeNode('D');BiTreeNodeG1=newBiTreeNode('G');BiTreeNodeH1=newBiTreeNode('H');BiTreeNodeE1=newBiTreeNode('E',G1,null);BiTreeNodeB1=newBiTreeNode('B',D1,E1);BiTreeNodeF1=newBiTreeNode('F',null,H1);BiTreeNodeC1=newBiTreeNode('C',F1,null);BiTreeNodeT1=newBiTreeNode('A',B1,C1);//创建根结点为T2的二叉树BiTreeNodeD2=newBiTreeNode('D');BiTreeNodeG2=newBiTreeNode('G');BiTreeNodeH2=newBiTreeNode('H');BiTreeNodeE2=newBiTreeNode('E',G2,null);

BiTreeNodeB2=newBiTreeNode('B',D2,E2);BiTreeNodeF2=newBiTreeNode('F',null,H2);BiTreeNodeC2=newBiTreeNode('C',F2,null);BiTreeNodeT2=newBiTreeNode('A',B2,C2);//创建根结点为T3的二叉树BiTreeNodeE3=newBiTreeNode('E');BiTreeNodeF3=newBiTreeNode('F');BiTreeNodeD3=newBiTreeNode('D',F3,null);BiTreeNodeB3=newBiTreeNode('B',null,D3);BiTreeNodeC3=newBiTreeNode('C',null,E3);BiTreeNodeT3=newBiTreeNode('A',B3,C3);Exercise5_4_1e=newExercise5_4_1();if(e.isEqual(T1,T2))System.out.println("T1、elseSystem.out.println("T1if(e.isEqual(T1,T2))System.out.println("T1、elseSystem.out.println("T1、if(e.isEqual(T1,T3))System.out.println("T1、elseSystem.out.println("T1、T2两棵二叉树相等！”);T2两棵二叉树不相等！”);T3两棵二叉树相等！”);T3两棵二叉树不相等！”);))运行结果:.编写一个程序实现：先建立一棵以孩子兄弟链表存储结构表示的树，然后输出这棵树的先根遍历序列和后根遍历序列。参考答案：packagech05Exercise;importch05.CSTreeNode; //教材第5章中有此类的描述publicclassExercise5_4_2{//创建一棵树publicCSTreeNodecreateBiTree(){CSTreeNodeD=newCSTreeNode('D');CSTreeNodeE=newCSTreeNode('E');CSTreeNodeC=newCSTreeNode('C',D,E);CSTreeNodeB=newCSTreeNode('B',null,C);CSTreeNodeA=newCSTreeNode('A',B,null);returnA;)//先根遍历树的递归算法publicvoidpreRootTraverse(CSTreeNodeT){if(T!=null){System.out.print(T.getData());//访问根结点preRootTraverse(T.getFirstchild());//访问孩子结点preRootTraverse(T.getNextsibling());//访问兄弟结点))//后根遍历树的递归算法publicvoidpostRootTraverse(CSTreeNodeT){if(T!=null){postRootTraverse(T.getFirstchild());//访问孩子结点System.out.print(T.getData());//访问根结点postRootTraverse(T.getNextsibling());//访问兄弟结点))publicstaticvoidmain(String[]args){Exercise5_4_2e=newExercise5_4_2();CSTreeNoderoot=e.createBiTree();//调试先根遍历System.out.println("该树的先根遍历为：")；e.preRootTraverse(root);//调试后根遍历System.out.println("\n该树的后根遍历为：")；e.postRootTraverse(root);))运行结果：.编写一个基于构造哈夫曼树和哈夫曼编码的HuffmanCoding类的测试程序，使其实现先建立一棵哈夫曼树，然后再根据这棵哈夫曼树来构造并输出其哈夫曼编码。参考答案：packagech05Exercise;importch05.HuffmanNode;//教材第5章中有此类的描述〃构造哈夫曼树和哈夫曼编码的HuffmanCoding类classHuffmanTree{//求赫夫曼编码的算法，W存放n个字符的权值(均>0)publicint[][]huffmanCoding(int[]W){intn=W.length;//字符个数intm=2*n-1;//赫夫曼树的结点数HuffmanNode[]HN=newHuffmanNode[m];inti;for(i=0;i<n;i++)HN[i]=newHuffmanNode(W[i]);//构造n个具有权值的结点for(i=n;i<m;i++){//建赫夫曼树//在HN[0..i-1]选择不在赫夫曼树中且weight最小的两个结点mini和min2HuffmanNodemini=selectMin(HN,i-1);min1.setFlag(1);HuffmanNodemin2=selectMin(HN,i-1);min2.setFlag(1);//构造mini和min2的父结点，并修改且父结点的权值HN[i]=newHuffmanNode();mini.setParent(HN[i]);min2.setParent(HN[i]);HN[i].setLchild(mini);HN[i].setRchild(min2);HN[i].setWeight(min1.getWeight()+min2.getWeight());)//从叶子到根逆向求每个字符的赫夫曼编码int[][]HuffCode=newint[n][n];//分配n个字符编码存储空间for(intj=0;j<n;j++){intstart=n-1;//编码的开始位置，初始化为数组的结尾for(HuffmanNodec=HN[j],p=c.getParent();p!=null;c=p,p=p.getParent())//从叶子到根逆向求编码if(p.getLchild().equals(c))//左孩子编码为0HuffCode[j][start--]=0;else//右孩子编码为1HuffCode[j][start--]=1;HuffCode[j][start]=-1;//编码的开始标志为-1，编码是-1之后的