习题五和上机答案

习题五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 （3）g 的双亲是：c （4）g 的祖先是：a，c （5）g 的孩子是：j，k （6）e 的子孙是：i，m，n（7）e 的兄弟是 d，f 的兄弟是 g，h （8）b 的层次是 2，n 的层次是 5 （9）树的深度是 5 （10）以结点 c 为根的子树的深度是 3 （11）树的度数是 35.2 一棵度为2的树与一棵二叉树有何区别？解：二叉树的度也可以为1。5.3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。解：二叉树：5.4 一棵深度为N的满叉树有如下性质：第N层上的结点都是叶子结点，其余各层上每个结点都有棵非空子树。如果按层次顺序从开始对全部结点编号，问 各层的结点数目是多少？ 编号为n 的结点的父结点（若存在）的编号是多少？ 编号为n 的结点的第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-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 在二叉树的顺序存储结构中，实际上隐含着双亲的信息，因此可和三叉链表对应。假设每个指针域占个字节的存储空间，每个信息占个字节的存储空间。试问对于一棵有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; 后序遍历：根据后序遍历二叉树的递归定义，转换成非递归函数时采用一个栈保存返回的结点，先扫描根结点的所有左结点并入栈，出栈一个结点，然后扫描该结点的右结点并入栈，再扫描该右结点的所有左结点并入栈，当一个结点的左右子树均访问后再访问该结点，如此这样，直到栈空为止。在访问根结点的右子树后，当指针 p 指向右子树树根时，必须记下根结点的位置，以便在遍历右子树之后正确返回，这就产生了一个问题：在退栈回到根结点时如何区别是从左子树返回还是从右子树返回。这里采用两个栈 stack 和 tag，并用一个共同的栈顶指针，一个存放指针值，一个存放左右子树标志（0 为左子树，1 为右子树）。退栈时在退出结点指针的同时区别是遍历左子树返回的还是遍历右子树返回的，以决定下一步是继续遍历右子树还是访问根结点。因此，实现本题功能的函数如下： 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; /*表示当前结点的右子树已访问过*/ 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 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值是储存在结点中的,而不是暂存在堆栈中,所以访问完毕后要将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() . 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); return(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 已知一棵二叉树以二叉链表作存储结构，编写完成下列操作的算法：对于树中每个元素值为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); 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(%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-left=copy(b-left); p-right=copy(b-right); return(p); else return(NULL); 5.18 已知一棵以二叉链表为存储结构的二叉树，试编写层次顺序（同一层自左向右）遍历二叉树的算法。解：依题意：本算法要采用一个队列 q，先将二叉树根结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树根结点入队列，若它有右子树，便将右子树根结点入队列，如此直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树的目的。 因此，实现本题功能的函数如下： #define MAXLEN 100void translevel(btree *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; 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; 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,SqList 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_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(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;/Print_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-rchild) Find_h(T-rchild,h+1); pathh=NULL; /回溯/Find_h 5.23 试分别画出下列各二叉树的先序、中序、后序的线索二叉树。 (a) (b) (c) (d) (e)A 题5.23解：（a）先序、中序、后序的线索二叉树都是：（b）前序： 中序和后序（一样）：ABCABC（c）前序和中序（一样）： 后序：ABCABC（d）前序： 中序：ABCABC后序：ABC（e）前序：BCDEFIGHJKMA中序：BCDEFIGHJKMA后序：BCDEFIGHJKMA5.24 试编写一个算法，在中序线索二叉树中，结点p之下插入一棵以结点x为根，只有左子树的中序全线索化二叉树，使x为根的二叉树成为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; /找到子树中的最左结点,并修改其前驱指向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.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); 以此给出中序遍历二叉树的非递归算法：只要从头结点出发，反复找到结点的后继，直至结束。本函数如下：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 对以下存储结构分别写出计算树的深度的算法： 双亲表示法； 孩子链表表示法； 孩子兄弟表示法。解：（1）int GetDepth_PTree(PTree T)/求双亲表表示的树T的深度 maxdep=0; for(i=0;i=0;j=T.nodesj.parent) dep+; /求每一个结点的深度 if(depmaxdep) maxdep=dep; return maxdep;/GetDepth_PTree（2）int GetDepth_CTree(CTree A)/求孩子链表表示的树A的深度 return SubDepth(A.r);/GetDepth_CTree int SubDepth(int T)/求子树T的深度 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 （3）int 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; /子树的最大深度 return 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+49*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 时，前序序列和中序序列均只有一个元素，且相同，即为树的根，由此惟一确定了一棵二叉树。假设 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，由此，这二个序列惟一确定了右子树，就惟一确定了二叉树。 若 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)构造二叉树，其根结点指针为 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(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 add(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) inor