习题5树和二叉树.ppt

1 填空题,(1)树是n（n0）个结点的有限集合。在一棵非空树中，有（且仅有一个）根结点，其余结点分成m（m=0）个(互不相交)的有限集合，每个集合又是一棵树。,(2) 树中某结点的子树的个数称为该结点的（ 度 ），子树的根结点称为这个结点的( 孩子结点 ),该结点称为其子树根结点的（双亲结点）.,(3) 一棵二叉树的第i（i1）层上最多有( 2i-1 )个结点,一棵有n(n0)个结点的满二叉树共有( (n+1)/2 )个叶子结点和( (n-1)/2 )个非终端结点。,(4) 设高度为h的二叉树只有度为0的和度为2的结点，该二叉树的结点数可能达到的最大值是( 2h-1 ),最小值是（ 2 h -1 ）。,(5)深度为k的二叉树中，所含叶子的个数最多为(2k-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 )。 A1 B2 C3 D4,2 选择题,(2) 设二叉树有n个结点，则其深度为( D )。 An一1 Bn 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 )个结点。 A2k-2+1 B2k-1 C2k-1 D2k-1-1,一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有( D )成立。 Anh+m Bh+m2n Cmh-1 Dn2m一1,(7) 任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序( A )。 A. 肯定不发生改变 B.肯定发生改变 C.不能确定 D有时发生变化,(9) 设森林中有4棵树，树中结点的个数依次为n1, n2, n3, n4, 则把森林转换成二叉树后，其根结点的右子树上有( D )个结点。根结点的左子树上有( A )个结点。 An1-1 Bnl Cnl+n2+n3 Dn2+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的树中：n1个度为1的结点，n2个度为2的结点，nm个度为m的结点，问该树中共有多少个叶子结点？,解：设该树中共有n0个叶子结点。则该树中总结点个数为 n= n0+ n1 + nm. 而分支数为n-1= n1 +2n2 +3n3 + mnm,所以 n0 =1+n2 +2n3 + (m-1)nm,4. 解答下列问题,(1) 证明：任何满二叉树的分支数B=2(n0-1). (2) 证明：已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树。,(4) 已知一棵二叉树的中序和后序序列为CBEDAFIGH和CEDBIFHGA,试构造该二叉树。,D,I,(5) 给出叶子结点的权值集合为W=5,2,9,11, 8,3,7的哈夫曼树的构造过程。,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; / coutnum ,(1) 设计算法求二叉树的结点个数.,(3) 设计算法求二叉树的深度.,注：本算法也可以用二叉树遍历的所有算法。但是在用前序和中序算法时要注意深度如何来确定。,解法一： int BiTree:depth(BiNode *rt) if (rt =NULL) return 0; else hl= depth(rt-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 ,(3) 设计算法求二叉树的深度.,解法三：用层序遍历算法, 设一个指针来表示目前遍历到的层数，最底层就是此树的深度。 void BiTree:Depth(BiNode *rt) int depth=0, flag=0;/depth为树的深度，flag为当前遍历到的层数 front=rear=-1; /采用顺序队列，并假定不会发生上溢 if (rt!=NULL) Q+rear=rt; / Q为队列 while (front!=rear) q=Q+front; if (q-lchild!=NULL) Q+rear=q-lchild; if (q-rchild!=NULL) Q+rear=q-rchild; if(front=flag) depth+; flag=rear; coutdepth; ,(3) 设计算法求二叉树的深度.,解法四：用前序遍历算法, 在栈中设两个域，一个表示原遍历结点，一个表示此结点的层数。 template void BiTree:DepthProOrder(BiNode *rt) top= -1; length=0; /采用顺序栈s，并假定不会发生上溢 while (rt!=NULL | | top!= -1) while (rt!= NULL) /找此结点的最左边的后代 s+top.ptr=rt; /此结点进栈 stop.depth=+length; rt=rt-lchild; /转移到左儿子子树 #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; elsep=rt; top= -1; /采用顺序栈s，并假定不会发生上溢 while (p!=NULL | | top!= -1) while (p!= NULL) /找此结点的最左边的后代 s+top=p; /此结点进栈 if(p-lchild!=NULL ) /#1 while ,void BiTree:DeleteX(BiNode *rt, T x) if(rt!=NULL) if(rt-data=x) Release(rt); rt=NULL; elsep=rt; top= -1; /采用顺序栈s，并假定不会发生上溢 while (p!=NULL | | top!= -1) while (p!= NULL) /找此结点的最左边的后代 s+top=p; /此结点进栈 p=p-lchild; /转移到左儿子子树 if(p!=NULL ) /#1 while ,(7) 一棵具有n个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历.,void BiTree:PreOrder_Seq(int rt) top= -1; p=rt; /采用顺序栈s，并假定不会发生上溢 while (p=length) ,算法思想: 套用前序遍历的原程序，注意查找左右孩子结点的地址和判别孩子是否存在的方法。,(8) 编写算法交换二叉树中所有结点的左右子树.,void BiTree:PostOrderChange(BiNode *rt) if (rt=NULL) return; else PostOrder(rt-lchild); PostOrder(rt-rchild); temp=rt-lchild; rt-lchild=rt-rchild; rt-rchild=temp; ,解法思想: 使用任何遍历算法，把“coutdata”改成左右孩子指针交换即可。,(2) 设计算法按照前序次序打印二叉树中的叶子结点.,void BiTree:leaf(BiNode *rt) if (rt=NULL) return; else if(rt-lchild=NULL ,注:其实按照“选择题”的(7)知:任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序肯定不发生改变 解法思想: 使用任何遍历算法，把“coutdata”改成判断此结点是否为叶子结点。,(4) 设计算法:输出二叉树后序遍历的逆序.,void BiTree:PostOrder_1(BiNode *rt) if (rt=NULL) return; else coutdata; PostOrder(rt-rchild); PostOrder(rt-lchild); ,解法思想: 太简单啦！,(5)以二叉链表为存储结构，编写算法求二叉树中值x的结点的双亲.,void BiTree:PreOrder