习题5 树和二叉树课件

1、1 填空题填空题(1)(1)树是树是n（n0）个结点的有限集合。在一棵非空树个结点的有限集合。在一棵非空树中，有（中，有（且仅有一个且仅有一个）根结点，其余结点分成）根结点，其余结点分成m（m=0）个个( (互不相交互不相交) )的有限集合的有限集合，每个集合又是一每个集合又是一棵树。棵树。(2) (2) 树中某结点的子树的个数称为该结点的（树中某结点的子树的个数称为该结点的（ 度度 ），），子树的根结点称为这个结点的子树的根结点称为这个结点的( ( 孩子结点孩子结点 ),),该结点称该结点称为其子树根结点的（为其子树根结点的（双亲结点双亲结点）. . (3) (3) 一棵二叉树的第一棵二叉树

2、的第i（i1）层上最多有层上最多有( ( 2i- -1 ) )个结个结点点, ,一棵有一棵有n(n0)n(n0)个结点的满二叉树共有个结点的满二叉树共有( ( (n+1)/2 (n+1)/2 ) )个叶子结点和个叶子结点和( ( (n-1)/2 (n-1)/2 ) )个非终端结点个非终端结点。 (4) (4) 设高度为设高度为h的的二叉树只有度为二叉树只有度为0 0的和度为的和度为2 2的结点，的结点，该二叉树的结点数可能达到的最大值是该二叉树的结点数可能达到的最大值是( ( 2h-1 -1 ),),最小最小值是（值是（ 2 2 h -1 -1 ）。）。(5)(5)深度为深度为k k的二叉树中

3、，所含叶子的个数最多为的二叉树中，所含叶子的个数最多为( (2 2k k-1-1).).(6)(6)具有具有100100个结点的完全二叉树的叶子结点数为个结点的完全二叉树的叶子结点数为( (5050) )。 (7) (7) 已知一棵度为已知一棵度为3 3的树有的树有2 2个度为个度为1 1的结点，的结点，3 3个度为个度为2 2的结点，的结点，4 4个度为个度为3 3的结点。则该树有的结点。则该树有( (1212) )个叶子结点个叶子结点。(8) (8) 某二叉树的前序遍历序列是某二叉树的前序遍历序列是ABCDEFG,ABCDEFG,中序遍历序中序遍历序列是列是CBDAFGE,CBDAFGE,

4、则其后序遍历序列是则其后序遍历序列是( ( CDBGFEA CDBGFEA ) )。(9)(9)在具有在具有n n个结点的二叉链表中，共有（个结点的二叉链表中，共有（ 2n 2n ) )个指个指针域，其中针域，其中( ( n-1 n-1 ) )个指针域用于指向其左右孩子，个指针域用于指向其左右孩子，剩下的剩下的( ( n+1 n+1 ) )个指针域则是空的。个指针域则是空的。(10)(10)在有在有n n个叶子的哈夫曼树中，叶子结点总数为个叶子的哈夫曼树中，叶子结点总数为( (n n),),分支结点总数为（分支结点总数为（ n-1 n-1 ）。）。1 填空题填空题(续续)(1) (1) 如果结

5、点如果结点A A有有3 3个兄弟，个兄弟，B B是是A A的双亲，则的双亲，则B B的度是的度是( ( D D ) )。 A A1 B1 B2 C2 C3 D3 D4 42 选择题选择题(2) (2) 设二叉树有设二叉树有n n个结点，则其深度为个结点，则其深度为( ( D D ) )。 A An n一一1 B1 Bn Cn C D D不能定不能定 1log2n(3) (3) 二叉树的前序序列和后序序列正好相反，则该二叉树一二叉树的前序序列和后序序列正好相反，则该二叉树一定是定是( ( B B ) )的二叉树。的二叉树。 A A空或只有一个结点空或只有一个结点 B B高度等于其结点数高度等于其

6、结点数 C C任一结点无左孩子任一结点无左孩子 D D任一结点无右孩子任一结点无右孩子(4) (4) 线索二叉树中某结点线索二叉树中某结点R R没有左孩子的充要条件是没有左孩子的充要条件是( ( C C ) )。 A. R.child=NULL B. R.ltag=0 A. R.child=NULL B. R.ltag=0 C. R.ltag=1 D. R.child=NULL C. R.ltag=1 D. R.child=NULL(5) (5) 深度为深度为k k的完全二叉树至少有的完全二叉树至少有( ( B B ) )个结点，至多有个结点，至多有( ( C C ) )个结点。个结点。 A

7、A2 2k-2k-2+1 B+1 B2 2k-1k-1 C C2 2k k-1 D-1 D2 2k-1k-1-1-1 一个高度为一个高度为h h的满二叉树共有的满二叉树共有n n个结点，其中有个结点，其中有m m个叶子结点个叶子结点，则有，则有( ( D D ) )成立。成立。 A An nh+m Bh+m Bh+mh+m2n C2n Cm mh-1 Dh-1 Dn n2m2m一一1 1(7) (7) 任何一棵二叉树的叶子结点在前序、中序、后序遍历序列任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序中的相对次序( ( A A ) )。 A. A. 肯定不发生改变肯定不发生改变 B

8、. B.肯定发生改变肯定发生改变 C. C.不能确定不能确定 D D有时发生变化有时发生变化(9) (9) 设森林中有设森林中有4 4棵树，树中结点的个数依次为棵树，树中结点的个数依次为n1,n1, n2,n2, n3,n3, n4, n4, 则把森林转换成二叉树后，其根结点的右子树上有则把森林转换成二叉树后，其根结点的右子树上有( ( D D ) )个结点。根结点的左子树上有个结点。根结点的左子树上有( ( A A ) )个结点。个结点。 A An1-1 Bn1-1 Bnl Cnl Cnl+n2+n3 Dnl+n2+n3 Dn2+n3+n4n2+n3+n4(8) (8) 如果如果TT是由有序

9、树是由有序树T T转换而来的二叉树，那么转换而来的二叉树，那么T T中结点的中结点的前序序列就是前序序列就是TT中结点的中结点的( ( A A ) )序列，序列，T T中结点的后序序列中结点的后序序列就是就是TT中结点的中结点的( ( B B ) )序列。序列。 A A前序前序 B B中序中序 C C后序后序 D D层序层序(10) (10) 讨论树、森林和二叉树的关系，目的是为了讨论树、森林和二叉树的关系，目的是为了( ( B B ) )。 A A借助二叉树上的运算方法去实现对树的一些运算借助二叉树上的运算方法去实现对树的一些运算 B B将树、森林按二叉树的存储方式进行存储并利用二叉将树、森

10、林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题树的算法解决树的有关问题 C. C. 将树、森林转换成二叉树将树、森林转换成二叉树 D 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,

11、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

12、 C. 4 D. 5(3)(3) 已知一棵度为已知一棵度为m m的树中：的树中：n n1 1个度为个度为1 1的结点，的结点，n n2 2个度个度为为2 2的结点，的结点，n nm m个度为个度为m m的结点，问该树中共有多的结点，问该树中共有多少个叶子结点？少个叶子结点？NoImage4. 解答下列问题解答下列问题(1)(1) 证明：任何满二叉树的分支数证明：任何满二叉树的分支数B=2(n0-1).B=2(n0-1).(2) (2) 证明：已知一棵二叉树的前序序列和中序序列，证明：已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树。则可唯一确定该二叉树。(4) 已知一棵二叉树的中序和后

13、序序列为已知一棵二叉树的中序和后序序列为CBEDAFIGH和和CEDBIFHGA,试构造该二叉树。试构造该二叉树。AEBGCHFDI(5) 给给出叶子结点的权值集合为出叶子结点的权值集合为W=5,2,9,11, 8,3,7的哈夫曼树的构造过程的哈夫曼树的构造过程。 95235101911268715455 算法设计算法设计(1) 设计算法求二叉树的结点个数设计算法求二叉树的结点个数.注：本算法可以用二叉树遍历的所有算法，只要把注：本算法可以用二叉树遍历的所有算法，只要把cout语句语句换成结点的计数就可以了，但是要注意递归中的计数变量应换成结点的计数就可以了，但是要注意递归中的计数变量应该是外

14、部变量。如该是外部变量。如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) )

15、+count( (rt-rchild)+1)+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=

16、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= hr= depth(

17、(rt-rchild);); return (hlhr)?hl+1: 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=r

18、t-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 depth;(3) 设计算法求二叉树的深度设计算法求二叉树的深度.解法三：用层序遍历算法解法三：用层序遍历算法, 设一个指针来表示目前遍历到设一个指针来表示目前遍历到的层数，最底层就是此树的深度。的层数，最底层就是此树的深度。void BiTree:Depth(BiNode

19、*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) 设计算法求二叉树的深度设计算法求二叉树的深度.解法四：用前序遍历算法

20、解法四：用前序遍历算法, 在栈中设两个域，一个表示原遍历结点，一个在栈中设两个域，一个表示原遍历结点，一个表示此结点的层数。表示此结点的层数。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(lengthd

21、epth) depth=length; if (top!= -1) rt=stop.ptr; length=stop-.depth; rt=rt-rchild; /#1 while(6) 以二叉链表为存储结构，在二叉树中删除以值以二叉链表为存储结构，在二叉树中删除以值x为根结点为根结点的子树的子树.解法思想解法思想: 若根结点的值为若根结点的值为x,则删除整个树；否则查找值为则删除整个树；否则查找值为x的结点的的结点的双亲双亲p，然后删除此结点所对应的子树，然后删除此结点所对应的子树,同时修改同时修改p的的左左(或右或右)孩子的指针孩子的指针。最好用前序遍历查找。最好用前序遍历查找,后序遍历删

22、除。后序遍历删除。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) whil

23、e (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 whilevoid BiTree:DeleteX(BiNode *rt, T x) if(r

24、t!=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 )&(p-data=x) Release(p) ; stop-lchild=NULL; #2 while if (top!= -1) p=stop; p=p-rchild; if(p!=NULL )&(p

25、-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!=“ ”) /找此结点的最左边的后代

26、找此结点的最左边的后代 coutAp; /访问访问 s+top=p; /此结点进栈此结点进栈 p=2*p; /转移到左儿子子树转移到左儿子子树 if (top!= -1) p=stop-; p=2*p+1; 算法思想算法思想: 套用前序遍历的原程序，注意查找左右孩子结点套用前序遍历的原程序，注意查找左右孩子结点的地址和判别孩子是否存在的方法的地址和判别孩子是否存在的方法。(8) 编写算法交换二叉树中所有结点的左右子树编写算法交换二叉树中所有结点的左右子树.void BiTree:PostOrderChange( (BiNode *rt) ) if ( (rt=NULL) ) return; e

27、lse 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 &!rt-rchild) coutdata; PostOrder( (rt-lchild) ); PostOrder( (rt-rchild) ); 注注:其实按照其实按照“选择题选择题”的的(7)知知:任何一棵二叉树的叶子结点任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序肯定不发生改在前序、中序、后序遍历序列中的相对次序肯定不发生改变变解法