习题5树和二叉树

1 填空题,(1),树是,n,（,n,0,）,个结点的有限集合。在一棵非空树中，有（,且仅有一个,）根结点，其余结点分成,m,（,m,=0,）,个,(,互不相交,),的有限集合,，,每个集合又是一棵树。,(2),树中某结点的子树的个数称为该结点的（,度,），,子树的根结点称为这个结点的,(,孩子结点,),该结点称为其子树根结点的（,双亲结点,）,.,(3),一棵二叉树的第,i,（,i,1,）,层上最多有,(,2,i,-,1,),个结点,一棵有,n(n0),个结点的满二叉树共有,(,(n+1)/2,),个叶子结点和,(,(n-1)/2,),个非终端结点,。,(4),设高度为,h,的,二叉树只有度为,0,的和度为,2,的结点，该二叉树的结点数可能达到的最大值是,(,2,h,-1,),最小值是（,2,h,-1,）。,(5),深度为,k,的二叉树中，所含叶子的个数最多为,(,2,k,-1,).,(6),具有,100,个结点的完全二叉树的叶子结点数为,(,50,),。,(7),已知一棵度为,3,的树有,2,个度为,1,的结点，,3,个度为,2,的结点，,4,个度为,3,的结点。则该树有,(,12,),个叶子结点。,(8),某二叉树的前序遍历序列是,ABCDEFG,中序遍历序列是,CBDAFGE,则其后序遍历序列是,(,CDBGFEA,),。,(9),在具有,n,个结点的二叉链表中，共有（,2n,),个指针域，其中,(,n-1,),个指针域用于指向其左右孩子，剩下的,(,n+1,),个指针域则是空的。,(10),在有,n,个叶子的哈夫曼树中，叶子结点总数为,(,n,),分支结点总数为（,n-1,）。,1 填空题,(,续,),(1),如果结点,A,有,3,个兄弟，,B,是,A,的双亲，则,B,的度是,(,D,),。,A,1 B,2 C,3 D,4,2,选择题,(2),设二叉树有,n,个结点，则其深度为,(,D,),。,A,n,一,1 B,n C,D,不能定,(3),二叉树的前序序列和后序序列正好相反，则该二叉树一定是,(,B,),的二叉树。,A,空或只有一个结点,B,高度等于其结点数,C,任一结点无左孩子,D,任一结点无右孩子,(4),线索二叉树中某结点,R,没有左孩子的充要条件是,(,C,),。,A.R.child=NULL B.R.ltag=0,C.R.ltag=1 D.R.child=NULL,(5),深度为,k,的完全二叉树至少有,(,B,),个结点，至多有,(,C,),个结点。,A,2,k-2,+1 B,2,k-1,C,2,k,-1 D,2,k-1,-1,一个高度为,h,的满二叉树共有,n,个结点，其中有,m,个叶子结点，则有,(,D,),成立。,A,n,h+m B,h+m,2n C,m,h-1 D,n,2m,一,1,(7),任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序,(,A,),。,A.,肯定不发生改变,B.,肯定发生改变,C.,不能确定,D,有时发生变化,(9),设森林中有,4,棵树，树中结点的个数依次为,n1,n2,n3,n4,则把森林转换成二叉树后，其根结点的右子树上有,(,D,),个结点。根结点的左子树上有,(,A,),个结点。,A,n1-1 B,nl C,nl+n2+n3 D,n2+n3+n4,(8),如果,T,是由有序树,T,转换而来的二叉树，那么,T,中结点的前序序列就是,T,中结点的,(,A,),序列，,T,中结点的后序序列就是,T,中结点的,(,B,),序列。,A,前序,B,中序,C,后序,D,层序,(10),讨论树、森林和二叉树的关系，目的是为了,(,B,),。,A,借助二叉树上的运算方法去实现对树的一些运算,B,将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题,C.,将树、森林转换成二叉树,D,体现一种技巧，没有什么实际意义,(11),下列编码中，,(,B,),不是前缀编码。,A.(00,01,10,11),B.(0,1,00,11),C.(0,10,110,111)D.(1,01,000,001),(12),为,5,个使用频率不等的字符设计哈夫曼编码，不可能的方案是,(,C,).,A.111,110,10,01,00 B.000,001,010,011,1,C.100,11,10,1,0 D.001,000,01,11,10,(13),为,5,个使用频率不等的字符设计哈夫曼编码，不可能的方案是,(,D,).,A.000,001,010,011,1 B.0000,0001,001,01,1,C.000,001,01,10,11 D.00,100,101,110,111,(14),设哈夫曼编码的长度不超过,4,，若已经对两个字符编码为,1,和,01,，则最多还可以为,(,C,),个字符编码,.,A.2 B.3 C.4 D.5,(3),已知一棵度为,m,的树中：,n,1,个度为,1,的结点，,n,2,个度为,2,的结点，,，,n,m,个度为,m,的结点，问该树中共有多少个叶子结点？,解：设该树中共有,n,0,个叶子结点。则该树中总结点个数为,n=n,0,+n,1,+n,m,.,而分支数为,n-1=n,1,+2n,2,+3n,3,+mn,m,所以,n,0,=1+n,2,+2n,3,+(m-1)n,m,4.,解答下列问题,(1),证明：任何满二叉树的分支数,B=2(n0-1).,(2),证明：已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树。,(4),已知一棵二叉树的中序和后序序列为,CBEDAFIGH,和,CEDBIFHGA,试构造该二叉树。,A,E,B,G,C,H,F,D,I,(5),给,出叶子结点的权值集合为,W=5,2,9,11,8,3,7,的哈夫曼树的构造过程,。,9,5,2,3,5,10,19,11,26,8,7,15,45,5,算法设计,(1),设计算法求二叉树的结点个数,.,注：本算法可以用二叉树遍历的所有算法，只要把,cout,语句换成结点的计数就可以了，但是要注意递归中的计数变量应该是外部变量。如,int num=0;,int BiTree:count,(,BiNode*rt,),countsub(rt);,return num;,void BiTree:countSub,(,BiNode*rt,),if,(,rt!=NULL,),num+;,countSub,(,rt,-,lchild,),;,countSub,(,rt,-,rchild,),;,其他解法一：,int,BiTree:count,(,BiNode*rt,),if,(,rt=NULL,),return 0;,else return,count,(,rt,-,lchild,),+count,(,rt,-,rchild,)+1,;,其他解法二：用前序遍历的非递归算法,int,BiTree:CountPreOrder(BiNode*rt),top=-1;p=rt;,num=0,;/,采用顺序栈,s,，并假定不会发生上溢,while(p!=NULL|top!=-1),while(p!=NULL)/,找此结点的最左边的后代,num+,;/,访问,s+top=p;/,此结点进栈,p=p-lchild;/,转移到左儿子子树,if(top!=-1)p=stop-;p=p-rchild;,return num,;,/cout,lchild,);,hr=,depth,(,rt,-,rchild,);,return(hlhr)?hl+1:,hr+1;,(3),设计算法求二叉树的深度,.,解法二：用后序遍历的非递归算法,这是栈的最大顶就是此树的深度。,void BiTree:DepthPostOrder(BiNode*rt),depth=0;,top=-1;/,采用顺序栈，并假定栈不会发生上溢,while(rt!=NULL|top!=-1),while(rt!=NULL),s+top.ptr=rt;,stop.flag=1;,rt=rt-lchild;,if(top=depth)depth=top+1;,while(top!=-1&stop.flag=2),rt=stop-.ptr;,if(top!=-1)stop.flag=2;,rt=stop.ptr-rchild;,coutThe depth of the tree is lchild!=NULL)Q+rear=q-lchild;if(q-rchild!=NULL)Q+rear=q-rchild;,if(front=flag)depth+;flag=rear;,coutlchild;/,转移到左儿子子树,#2 while,if(lengthdepth)depth=length,;,if(top!=-1),rt=stop.ptr;,length=stop-.depth;,rt=rt-rchild;,/#1 while,(6),以二叉链表为存储结构，在二叉树中删除以值,x,为根结点的子树,.,解法思想,:,若根结点的值为,x,则删除整个树；否则查找值为,x,的结点的,双亲,p,，然后删除此结点所对应的子树,同时修改,p,的左,(,或右,),孩子的指针,。最好用前序遍历查找,后序遍历删除。,void BiTree:DeleteX(BiNode*rt,T x),if(rt=NULL)return;,if(rt-data=x)Release(rt);,else,DeleteX(rt-lchild,x);,DeleteX(rt-rchild,x);,void BiTree:DeleteX(BiNode*rt,T x),if(rt!=NULL),if(rt-data=x)Release(rt);rt=NULL;,else,p=rt;top=-1;/,采用顺序栈,s,，并假定不会发生上溢,while(p!=NULL|top!=-1),while(p!=NULL)/,找此结点的最左边的后代,s+top=p;/,此结点进栈,if(p-lchild!=NULL)&(p-lchild-data=x),Release(p-lchild);p-lchild=NULL;,if(p-rchild!=NULL)&(p-rchild-data=x),Release(p-rchild);p-rchild=NULL;,p=p-lchild;,#2 while,if(top!=-1)p=stop-;p=p-rchild;,/#1 while,void BiTree:DeleteX(BiNode*rt,T x),if(rt!=NULL),if(rt-data=x)Release(rt);rt=NULL;,else,p=rt;top=-1;/,采用顺序栈,s,，并假定不会发生上溢,while(p!=NULL|top!=-1),while(p!=NULL)/,找此结点的最左边的后代,s+top=p;/,此结点进栈,p=p-lchild;/,转移到左儿子子树,if(p!=NULL)&(p-data=x),Release(p);stop-lchild=NULL;,#2 while,if(top!=-1),p=stop,;p=p-rchild;,if(p!=NULL)&(p-data=x),Release(p);stop-rchild=NULL;,top-;,/#1 while,(7),一棵具有,n,个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历,.,void BiTree:PreOrder_Seq(int rt),top=-1;p=rt;/,采用顺序栈,s,，并假定不会发生上溢,while(,(p=length)&(Ap!=“”),|top!=-1),while(,(p=length)&(Ap!=“”),),/,找此结点的最左边的后代,cout,lchild,),;,PostOrder,(,rt,-,rchild,),;,temp=rt-lchild;,rt-lchi