习题五和上机答案

《习题五和上机答案》由会员分享，可在线阅读，更多相关《习题五和上机答案（28页珍藏版）》请在装配图网上搜索。

1、细心整理习题五5.1 确定一棵树边的集合为(I,M),(I,N),(E,I),(B,E),(B,D),(A,B),(G,J),(G,K),(C,G),(C,F),(TABLE,L),(C,TABLE),(A,C)，画出这棵树，并答复以下问题： 哪个是根结点？ 哪些是叶子结点？ 哪个是结点的双亲？ 哪些是结点的祖先？ 哪些是结点的孩子？ 哪些是结点的子孙？ 哪些是结点的兄弟？哪些是结点的兄弟？ 结点和的层次号分别是什么？ 树的深度是多少？ 以结点为根的子树的深度是多少？解：依题意，树的表示如图 8.23 所示。1根结点是：a 2叶子结点是：d，m，n，f，j，k，l 3g 的双亲是：c 4g 的

2、祖先是：a，c 5g 的孩子是：j，k 6e 的子孙是：i，m，n7e 的兄弟是 d，f 的兄弟是 g，h 8b 的层次是 2，n 的层次是 5 9树的深度是 5 10以结点 c 为根的子树的深度是 3 11树的度数是 35.2 一棵度为2的树与一棵二叉树有何区分？解：二叉树的度也可以为1。5.3 试分别画出具有3个结点的树和3个结点的二叉树的全部不同形态。解：二叉树：5.4 一棵深度为N的满叉树有如下性质：第N层上的结点都是叶子结点，其余各层上每个结点都有棵非空子树。假如按层次依次从起先对全部结点编号，问 各层的结点数目是多少？ 编号为n 的结点的父结点假设存在的编号是多少？ 编号为n 的结

3、点的第i个儿子假设存在的编号是多少？ 编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？解： 1第 i 层的结点数为 ki-1。 2编号为 n 的结点的双亲点为：(n-2)/k+1。 3编号为 n 的结点的第 i 个孩子结点为：(n-1)*k+i+1。 4编号为 n 的结点有右兄弟的条件是(n-1) % k0，其右兄弟的编号是 n+1。5.5 确定一棵度为m的树中有n1个度为的结点，n2个度为的结点，nm个度为m的结点，问该树中有多少个叶子结点？解：依题意：设 n 为总的结点个数，n0为叶子结点即度为 0 的结点的个数，那么有：n=n+ n+n+.+n 又有：n-1=度的总数，即：n-

4、1= n*1+ n*2+.+ n*m -式得： 1= n- n-2n-.-(m-1) n 那么有： n=1+ n+2n+.+(m-1) n =1+ 5.6 试列出以下二叉树的终端结点、非终端结点以及每个结点的层次 题5.6解：终端结点：E、G、H非终端结点：A、B、C、D、F结点ABCDEFGH层次122333445.7 对于5.6题中给出的二叉树，分别列出先根次序、中根次序、后根次序的结点序列。解：先根次序：ABDGCEFH中根次序：DGBAECHF后根次序：GDBEHFCA5.8 在二叉树的依次存储构造中，事实上隐含着双亲的信息，因此可和三叉链表对应。假设每个指针域占个字节的存储空间，每个

5、信息占个字节的存储空间。试问对于一棵有n个结点的二叉树，且在依次存储构造中最终一个结点的下标为m，在什么条件下依次存储构造比二叉链表更节约空间？解：K+4*n0) /*栈不为空时循环*/ p=stacktop; /*退栈并访问该结点*/ top-; printf(%d ，p-data);if (p-right!=NULL) /*右孩子入栈*/ top+; stacktop=p-right; if (p-left!=NULL) /*左孩子入栈*/ top+; stacktop=p-left; 后序遍历：依据后序遍历二叉树的递归定义，转换成非递归函数时接受一个栈保存返回的结点，先扫描根结点的全部左

6、结点并入栈，出栈一个结点，然后扫描该结点的右结点并入栈，再扫描该右结点的全部左结点并入栈，当一个结点的左右子树均访问后再访问该结点，如此这样，直到栈空为止。在访问根结点的右子树后，当指针 p 指向右子树树根时，必需登记根结点的位置，以便在遍历右子树之后正确返回，这就产生了一个问题：在退栈回到根结点时如何区分是从左子树返回还是从右子树返回。这里接受两个栈 stack 和 tag，并用一个共同的栈顶指针，一个存放指针值，一个存放左右子树标记0 为左子树，1 为右子树。退栈时在退出结点指针的同时区分是遍历左子树返回的还是遍历右子树返回的，以确定下一步是接着遍历右子树还是访问根结点。因此，实现此题功能

7、的函数如下： void postorder(btree *b) btree* stackMaxsize,*p; int tagMaxsize; int top=0; p=b; do while(p!=NULL) /*扫描左结点,入栈*/ top+; stacktop=p; tagtop=0; p=p-left; if(top0) if(tagtop=1) /*左右结点均已访问过,那么访问该结点*/ printf(%c ,stacktop-data); top-; else p=stacktop; if(top0) p=p-right; /*扫描右结点*/ tagtop=1; /*表示当前结点的

8、右子树已访问过*/ while(p!=NULL|top!=0); 5.12 假设在二叉链表中增设两个域：双亲域parent以指示其双亲结点；标记域mark：，以区分在遍历过程中到达该结点时应当接着向左或向右或访问该结点。试以此存储构造编写不用栈的后序遍历的算法。解：typedef struct int data; EBTNode *lchild; EBTNode *rchild; EBTNode *parent; enum 0,1,2 mark; EBTNode,EBitree; /有mark域和双亲指针域的二叉树结点类型 void PostOrder_Nonrecursive(EBitree

9、 T)/后序遍历二叉树的非递归算法,不用栈 p=T; while(p) switch(p-mark) case 0: p-mark=1; if(p-lchild) p=p-lchild; /访问左子树 break; case 1: p-mark=2; if(p-rchild) p=p-rchild; /访问右子树 break; case 2: visit(p); p-mark=0; /复原mark值 p=p-parent; /返回双亲结点 /PostOrder_Nonrecursive分析:此题思路与上一题完全一样,只不过结点的mark值是储存在结点中的,而不是暂存在堆栈中,所以访问完毕后要将

10、mark域复原为0,以备下一次遍历.5.13 试编写算法在一棵以二叉链表存储的二叉树中求这样的结点：它在前序序列中处第个位置。解：int c,k; /这里把k和计数器c作为全局变量处理 void Get_PreSeq(Bitree T)/求先序序列为k的结点的值 if(T) c+; /每访问一个子树的根都会使前序序号计数器加1 if(c=k) printf(Value is %dn,T-data); exit (1); else Get_PreSeq(T-lchild); /在左子树中查找 Get_PreSeq(T-rchild); /在右子树中查找 /if/Get_PreSeq main()

11、 . scanf(%d,&k); c=0; /在主函数中调用前,要给计数器赋初值0 Get_PreSeq(T,k);/main5.14 试以二叉链表作存储构造，编写计算二叉树中叶子结点数目的递归算法。解：依题意：计算一棵二叉树的叶子结点数的递归模型如下： 因此，实现此题功能的函数如下： int leafs(btree *b) int num1，num2; if (b=NULL) return(0); else if (b-left=NULL & b-right=NULL) return(1); else num1=leafs(b-left); num2=leafs(b-right); retu

12、rn(num1+num2); 5.15 以二叉链表作存储构造，编定算法将二叉树中全部结点的左、右子树相互交换。解：依题意：交换二叉树的左、右子树的递归模型如下：因此，实现此题功能的函数如下： btree *swap(btree *b) btree *t，*t1，*t2; if (b=NULL) t=NULL; else t=(btree *)malloc(sizeof(btree); /*复制一个根结点*/ t-data=b-data;t1=swap(b-left); t2=swap(b-right); t-left=t2; t-right=t1; return(t); 5.16 确定一棵二叉

13、树以二叉链表作存储构造，编写完成以下操作的算法：对于树中每个元素值为x的结点，删去以它为根的子树，并释放相应的空间。解：依题意：设 print 是以嵌套括号表示输出一个二叉树，此题的算法是：先判定根结点数据域是否为 x，假设是那么干脆输出该二叉树；否那么调用的函数对应的递归模型如下：因此，实现此题功能的函数如下： btree *delsubtree(btree *b，int x) btree *s; if (b!=NULL) if (b-data=x) /*根结点值等于 x 的状况，干脆删除*/ print(b); s=NULL; else s=finddel(b，x); return(s);

14、 btree *finddel(btree *p，int x) btree *s; if (p!=NULL) if (p-left!=NULL & p-left-data=x) print(p-left); p-left=NULL; if (p-right!=NULL & p-right-data=x) print(p-right); p-right=NULL; s=finddel(p-left，x); p-left=s; s=finddel(p-right，x); p-right=s; return(p); void print(btree *b) if (b!=NULL) printf(%

15、d，b-data); if (b-left!=NULL | b-right!=NULL) printf(); print(b-left); if (b-right!=NULL) printf(，); print(b-right); printf(); 5.17 确定一棵以二叉链表作存储构造的二叉树，试编写复制这棵二叉树的非递归算法。解：依题意：复制一棵二叉树的递归模型如下：因此，实现此题功能的递归函数如下： btree *copy(btree *b) btree *p; if (b!=NULL) p=(btree *)malloc(sizeof(btree); p-data=b-data; p

16、-left=copy(b-left); p-right=copy(b-right); return(p); else return(NULL); 5.18 确定一棵以二叉链表为存储构造的二叉树，试编写层次依次同一层自左向右遍历二叉树的算法。解：依题意：本算法要接受一个队列 q，先将二叉树根结点入队列，然后退队列，输出该结点，假设它有左子树，便将左子树根结点入队列，假设它有右子树，便将右子树根结点入队列，如此直到队列空为止。因为队列的特点是先进先出，从而到达按层次依次遍历二叉树的目的。 因此，实现此题功能的函数如下： #define MAXLEN 100void translevel(btree

17、 *b) struct node btree *vecMAXLEN; int f，r; q; q.f=0; /*置队列为空队列*/ q.r=0; if (b!=NULL) printf(%d ，b-data); q.vecq.r=b; /*结点指针进入队列*/ q.r=q.r+1;if (b!=NULL) printf(%d ，b-data); q.vecq.r=b; /*结点指针进入队列*/ q.r=q.r+1; while (q.fleft!=NULL) /*输出左孩子，并入队列*/ printf(%d ，b-left-data); q.vecq.r=b-left; q.r=q.r+1;

18、if (b-right!=NULL) /*输出右孩子，并入队列*/ printf(%d ，b-right-data); q.vecq.r=b-right; q.r=q.r+1; 5.19 试以二叉链表作存储构造，编写算法判别给定二叉树是否为完全二叉树。解：int IsFull_Bitree(Bitree T)/判定二叉树是否完全二叉树,是那么返回1,否那么返回0 InitQueue(Q); flag=0; EnQueue(Q,T); /建立工作队列 while(!QueueEmpty(Q) DeQueue(Q,p); if(!p) flag=1; else if(flag) return 0;

19、 else EnQueue(Q,p-lchild); EnQueue(Q,p-rchild); /不管孩子是否为空,都入队列 /while return 1;/IsFull_Bitree分析:该问题可以通过层序遍历的方法来解决.与62.相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,那么序列中会含有空指针.5.20 确定一棵完全二叉树存在于依次存储构造A(1:max)中，A1:n含结点值。试编写算法由此依次结点建立该二叉树的二叉链表。解：Status CreateBitree_SqList(Bitree &T,S

20、qList A)/依据依次存储构造建立二叉链表 Bitree ptrA.last+1; /该数组储存与sa中各结点对应的树指针 if(!A.last) T=NULL; /空树 return; ptr1=(BTNode*)malloc(sizeof(BTNode); ptr1-data=A.elem1; /建立树根 T=ptr1; for(i=2;idata=A.elemi; j=i/2; /找到结点i的双亲j if(i-j*2) ptrj-rchild=ptri; /i是j的右孩子 else ptrj-lchild=ptri; /i是j的左孩子 return OK;/CreateBitree_

21、SqList5.21 编写一个算法，输出以二叉树表示的算术表达式，假设该表达式中含有括号，那么在输出时应当添上，确定二叉树的存储构造为二叉链表。解：Status Print_Expression(Bitree T)/按标准形式输出以二叉树存储的表达式 if(T-data是字母) printf(%c,T-data); else if(T-data是操作符) if(!T-lchild|!T-rchild) return ERROR; /格式错误 if(T-lchild-data是操作符&T-lchild-data优先级低于T-data) printf(); if(!Print_Expression

22、(T-lchild) return ERROR; printf(); /留意在什么状况下要加括号 else if(!Print_Expression(T-lchild) return ERROR; if(T-rchild-data是操作符&T-rchild-data优先级低于T-data) printf(); if(!Print_Expression(T-rchild) return ERROR; printf(); else if(!Print_Expression(T-rchild) return ERROR; else return ERROR; /非法字符 return OK;/Pri

23、nt_Expression5.22 一棵二叉树的直径定义为，从二叉树的根结点到全部叶子结点的路径长度的最大值。假设以二叉链表作存储构造，试编写算法求给定二叉树的直径和其长度等于直径的一条路径即从根到该叶子结点的序列。解：int maxh; Status Printpath_MaxdepthS1(Bitree T)/求深度等于树高度减一的最靠左的结点 Bitree pathd; maxh=Get_Depth(T); /Get_Depth函数见6.44 if(maxhdata); exit; /打印输出路径 else if(T-lchild) Find_h(T-lchild,h+1); if(T-

24、rchild) Find_h(T-rchild,h+1); pathh=NULL; /回溯/Find_h 5.23 试分别画出以下各二叉树的先序、中序、后序的线索二叉树。 (a) (b) (c) (d) (e)A 题5.23解：a先序、中序、后序的线索二叉树都是：b前序： 中序和后序一样：ABCABCc前序和中序一样： 后序：ABCABCd前序： 中序：ABCABC后序：ABCe前序：BCDEFIGHJKMA中序：BCDEFIGHJKMA后序：BCDEFIGHJKMA5.24 试编写一个算法，在中序线索二叉树中，结点p之下插入一棵以结点x为根，只有左子树的中序全线索化二叉树，使x为根的二叉树成

25、为p的左子树，假设p原来有左子树，那么令它为x的右子树。完成插入之后二叉树应保持线索化特性。解：Status Insert_BiThrTree(BiThrTree &T,BiThrTree &p,BiThrTree &x)/在中序线索二叉树T的结点p下插入子树x if(!p-ltag&!p-rtag) return INFEASIBLE; /无法插入 if(p-ltag) /x作为p的左子树 s=p-lchild; /s为p的前驱 p-ltag=Link; p-lchild=x; q=x; while(q-lchild) q=q-lchild; q-lchild=s; /找到子树中的最左结点,

26、并修改其前驱指向s q=x; while(q-rchild) q=q-rchild; q-rchild=p; /找到子树中的最右结点,并修改其前驱指向p else /x作为p的右子树 s=p-rchild; /s为p的后继 p-rtag=Link; p-rchild=x; q=x; while(q-rchild) q=q-rchild; q-rchild=s; /找到子树中的最右结点,并修改其前驱指向s q=x; while(q-lchild) q=q-lchild; q-lchild=p; /找到子树中的最左结点,并修改其前驱指向p return OK;/Insert_BiThrTree 5

27、.25 确定一棵以线索链表作存储构造的中序线索二叉树，试编写在此二叉树上找后序后继的算法。解：在中序线索二叉树中求结点后继的算法：由于是中序线索二叉树，后继有时可干脆利用线索得到，rtag 为 0 时须要查找，即右子树中最左下的子孙便为后继结点。本函数如下：tbtree *succ(tbtree *p) btree *q; if (p-rtag=1) return(p-right); /*由后继线索干脆得到*/ else q=p-right; while (q-ltag=0) q=q-left; return(q); 以此给出中序遍历二叉树的非递归算法：只要从头结点启程，反复找到结点的后继，直

28、至完毕。本函数如下：void thinorder(tbtree) btree *t，*h; /*t：原二叉树的根结点指针，h：中序线索二叉树头结点*/ if (t!=NULL) p=h; do printf(%d ，p-data); p=succ(p); while (p!=NULL); 5.26 将以下森林转化为相应的二叉树，并按中序遍历进展线索化： 题5.26解：二叉树：129341012141311515线索二叉树：1293410121413115155.27 画出和题5.23所示各二叉树相应的森林：解： ABC(c) ABC(d) BEHKGJCFIMDA(e)5.28 对以下存储构造

29、分别写出计算树的深度的算法： 双亲表示法； 孩子链表表示法； 孩子兄弟表示法。解：1int GetDepth_PTree(PTree T)/求双亲表表示的树T的深度 maxdep=0; for(i=0;i=0;j=T.nodesj.parent) dep+; /求每一个结点的深度 if(depmaxdep) maxdep=dep; return maxdep;/GetDepth_PTree2int GetDepth_CTree(CTree A)/求孩子链表表示的树A的深度 return SubDepth(A.r);/GetDepth_CTree int SubDepth(int T)/求子树T

30、的深度 if(!A.nodesT.firstchild) return 1; for(sd=1,p=A.nodesT.firstchild;p;p=p-next) if(d=SubDepth(p-child)sd) sd=d; return sd+1;/SubDepth 3int GetDepth_CSTree(CSTree T)/求孩子兄弟链表表示的树T的深度 if(!T) return 0; /空树 else for(maxd=0,p=T-firstchild;p;p=p-nextsib) if(d=GetDepth_CSTree(p)maxd) maxd=d; /子树的最大深度 retu

31、rn maxd+1; /GetDepth_CSTree5.29 假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。解：ABEGDCIFHJ5.30 证明：树中结点u是结点v的祖先，当且仅当在先序序列中u在v之前，且在后序序列中u在v之后。5.31 证明：在结点数大于的哈夫曼树中不存在度为的结点。5.32 设有一组权1,4,9,16,25,36,49,64,81,100，试画出其哈夫曼树，并计算加权的路径长度。解：385416619219818510011936495564253014165WPL=1*7+4*7+9*6+16*5+25*4+36*3+4

32、9*3+64*3+81*2+100*2=11085.33 假设用于通讯的电文仅由个字母组成，字母在电文中出现的频率分别为，。试为这个字母设计哈夫曼编码，运用的二进制表示形式是另一编码方案。对于上述实例，比拟两这方案的优缺点。解：设这8个字母分别是：A、B、C、D、E、F、G、H。哈夫曼树：如以下图。所以：A：0010B：10 C：00000D：0001 E：01F：00001 G：11H：0011100402166028113219517371025.34 证明：由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。证明：接受递归法证明。 当 n=1 时，前序序列和中序序列均只有一个元素，且一

33、样，即为树的根，由此惟一确定了一棵二叉树。假设 nm-1 时命题均成立，那么证明 n=m 时亦成立。 假设前序序列为 a1，a2，.，am，中序序列为 b1，b2，.，bm。 因为前序序列由前序遍历二叉树所得，那么 a1即为根结点的元素，又中序序列由中序遍历二叉树所得，那么在中序序列中必能找到和 a1值一样的元素，设为 bj，由此可以得到b1，.，bj-1为左子树的中序序列，bj+1，.bm为右子树的中序序列。假设 j=1，即 b1为根，此时二叉树的左子树为空，a2，.，am为右子树的前序序列，b2，.，m为右子树的中序序列。右子树上的结点数为 m-1，由此，这二个序列惟一确定了右子树，就惟一

34、确定了二叉树。 假设 j=m，即 bm为根，此时二叉树的右子树为空，那么子序列a2，.，am和b1，.，bm-1一确定左子树。假设 2jm-1，那么子序列a2，.，aj和b1，.，bj1惟一确定了左子树，子序列aj+1，.，am和bj+1，.，bm惟一确定了右子树。 由此，证明白惟一的根及其左、右子树只能构成一棵确定的二叉树。 5.35 确定一棵二叉树的前序序列和中序序列分别存在于两个一维数组中，试编写算法建立该二叉树的二叉链表。解：此题的算法如下： 设前序序列和中序序列分别存放在两个一维数组 pre(1，n)和 ind(1，n)中，按前序序列pre(i，j)和中序序列 ind(u，v)构造二

35、叉树，其根结点指针为 s。btree *void bintree(i，j，u，v) int i，j，u，v; int k，l; btree *head，*s; head=NULL; /*根指针初始化，head 为空树*/ if (j=i) head=(btree *)malloc(sizeof(btree); /*建立根结点*/head-data=prei; k=u; while (indk!=prei) k+; /*在中序序列中查找根结点*/ l=i+k-u; /*l 为左子树中最右下结点在前序序列中的位置*/ if (k=u) head-left=NULL; else s=bintree(

36、i+1，l，u，k-1); /*构造左子树*/ head-left=s; if (k=v) head-right=NULL; else s=bintree(l+1，j，k+1，v); /*构造右子树*/ head-right=s; return(head); 第五章上机内容：5.1、建立一棵二叉排序树并中序遍历。(依据题目完善程序)#include “ stdio.h”#include “malloc.h”struct node char data； struct node *lchild , *rchild； bnode；typedef struct node * blink；blink a

37、dd(blink bt,char ch) if(bt=NULL) bt=nalloc(sizeof(bnode)； bt-data = ch； bt-lchild = bt-rchild =NULL； else if ( ch data) bt-lchild = add(bt-lchid ,ch)； else bt-rchild = add(bt-rchild,ch)；return bt；void inorder(blink bt) if(bt) inorder(bt- lc )； printf“%c”, bt-data ； inorder(bt- rc )； main() blink roo

38、t = NULL； int i,n； char x； scanf“%c”,&n)； for(i=1；idata=k; bt-lc=creat(bt-lc); bt-rc=creat(bt-rc); return(bt);void inorder(JD *bt) if(bt!=NULL) inorder(bt-lc); printf(%c,bt-data); inorder(bt-rc); void postorder(JD *bt) if(bt!=NULL) postorder(bt-lc); postorder(bt-rc); printf(%c,bt-data); main() JD *b

39、t,*p; p=creat(bt); printf(ninorder:n); inorder(p); printf(npostorder:n); postorder(p); getch();5.3、编写程序，实现按层次遍历二叉树。解：void leverorder(JD *bt) JD *p,*queueN; int i=0,j=0; for(i=0;ilc!=NULL) queuei+=bt-lc; if(bt-rc!=NULL) queuei+=bt-rc; printf(%3d,queuej+-data); bt=queuej; 5.4、建立由合法的表达式字符串确定的只含二元操作符的非空

40、表达式树，其存储构造为二叉链表，用二叉树的遍历算法求该中缀表达式对应的后缀、前缀表达式。解：#define NULL 0typedef struct tree char data; struct tree *lc,*rc;JD;JD *creat(JD *bt) char k; scanf(%d,&k); if(k=0) bt=NULL; else bt=(JD *)malloc(sizeof(JD); bt-data=k; bt-lc=creat(bt-lc); bt-rc=creat(bt-rc); return(bt);void preorder(JD *bt) if(bt!=NULL) printf(%cz,bt-data); preorder(bt-lc); preorder(bt-rc); void postorder(JD *bt) if(bt!=NULL) postorder(bt-lc); postorder(bt-rc); printf(%c,bt-data); main() JD *bt,*p; p=creat(bt); printf(ninorder:n); preorder(p); printf(npostorder:n); postorder(p); getch();