第五六章程序题

1、 第五章、数组和广义表习题 typedef char ElemType; typedef enumATOM,LISTElemTag; typedef struct GLNode ElemTag tag; union ElemType e; struct struct GLNode *hp,*tp; ptr; ; *GList; 1、求广义表的表头 GList Head(GList ls) GList p; if(ls-tag=ATOM) p=ls-ptr.hp; return p; 2、求广义表的表尾 GList Tail(GList ls) GList p; if(ls-tag=LIST)

2、p=ls-ptr.tp; return p; 3、求广义表的深度 int Depth(GList ls) int max,dep; GList p; if(!ls) return 1; if(ls-tag=ATOM) return 0; else for(max=0,p=ls;p;p=p-ptr.tp) dep=Depth(p-ptr.hp); if(depmax) max=dep; return max+1; 第六章程序设计题 1、统计二叉树中叶子结点的个数 方法1. void CountLeaf (BiTree T, int& count)/ 先序遍历二叉树，以 count 返回二

3、叉树中叶子结点的数目 if ( T ) if (!T-Lchild)& (!T-Rchild)count+; / 对叶子结点计数 CountLeaf( T-Lchild, count); CountLeaf( T-Rchild, count); / if 方法2.int CountLeaf (BiTree T)/返回指针T所指二叉树中所有叶子结点个数 if (!T ) return 0; if (!T-lchild & !T-rchild) return 1; else m = CountLeaf( T-lchild); n = CountLeaf( T-rchild); re

4、turn (m+n); /else / CountLeaf2、统计所有结点的个数、统计所有结点的个数int Count (BiTree T)/返回指针T所指二叉树中所有结点个数 if (!T ) return 0; if (!T-lchild & !T-rchild) return 1; else m = Count ( T-lchild); n = Count ( T-rchild); return (m+n+1); /else / CountLeaf3、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)算法基本思想算法基本思想: : 从二叉树深度的定义可知，二叉树的二叉树的深度应为

5、其左、右子树深度的最大值加深度应为其左、右子树深度的最大值加1 1。由此，需先分别求得左、右子树的深度，需先分别求得左、右子树的深度，算法中“访问结点”的操作为:求得左、求得左、右子树深度的最大值，然后加右子树深度的最大值，然后加 1 1 。 首先分析二叉树的深度二叉树的深度和它的左左、右子右子树深度树深度之间的关系。int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (

6、depthLeft depthRight ? depthLeft : depthRight); return depthval;求二叉树的深度 void BiTreeDepth(BiTree T, int level, int &depth)/ T指向二叉树的根，level 为 T 所指结点所在层次，其初值为1，depth 为当前求得的最大层次,其初值为0if (T)if (leveldepth) depth=level; BiTreeDepth(T-Lchild, level+1, depth);BiTreeDepth(T-Rchild, level+1, depth);4、在二叉树

7、上查询某个结点 void locate(BiTree T,ElemType x,BiTree& p)/ 若二叉树 T 中存在和 x 相同的元素，则 p 指向该结点，否则 p 的值不变，p 的初值为 NULLif (T) if (T-data=x) p=T;locate(T-lchild, x, p);locate(T-rchild, x, p); 5: 5: 假设二叉树采用二叉链存储结构假设二叉树采用二叉链存储结构, ,设计一个算法判断两棵设计一个算法判断两棵二叉树是否相似二叉树是否相似, ,所谓二叉树所谓二叉树t1t1和和t2t2是相似的指的是是相似的指的是t1t1和和t2t2都是空

8、的二叉树；或者都是空的二叉树；或者t1t1和和t2t2的根结点是相似的的根结点是相似的, ,以及以及t1t1的的左子树和左子树和t2t2的左子树是相似的且的左子树是相似的且t1t1的右子树与的右子树与t2t2的右子树是的右子树是相似的。相似的。解：判断两棵二叉树是否相似的递归模型解：判断两棵二叉树是否相似的递归模型f()f()如下：如下： f(t1,t2)=true 若若t1=t2=NULL f(t1,t2)=false 若若t1、t2之一为之一为NULL,另一不为另一不为NULL f(t1,t2)=f(t1-lchild,t2-lchild) & f(t1-rchild,t2-rch

9、ild) 其他情况其他情况 int Like(BiTree t1,BiTree t2)/*t1t1和和t2t2两棵二叉树相似时返回两棵二叉树相似时返回1,1,否则返回否则返回0 0*/ int like1,like2; if (t1=NULL & t2=NULL) return 1; else if (t1=NULL | t2=NULL) return 0; else like1=Like(t1-lchild, t2-lchild); like2=Like(t1-rchild, t2-rchild); return (like1 & like2); /*返回返回like1lik

10、e1和和like2like2的与的与*/ 例例6: 编写按层次（同一层从左至右）遍历二叉树的算编写按层次（同一层从左至右）遍历二叉树的算法。法。void LayerOrder(Bitree T)/层序遍历二叉树层序遍历二叉树 InitQueue(Q); EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p); visit(p); if(p-lchild) EnQueue(Q,p-lchild); if(p-rchild) EnQueue(Q,p-rchild); 例7、具有n个结点的完全二叉树，已经顺序存储在一维数组A1.n中，下面的算法是将A中顺序存储

11、的二叉树变为二叉链表存储的完全二叉树 #define n 10 TElemType An+1; void CreaBiTree(BiTree &T,int i) T=(BiTree)malloc(sizeof(BiTNode); T-data=Ai; if(i*2lchild,i*2); else T-lchild=NULL; if(i*2+1rchild,i*2+1); else T-rchild=NULL; 例8、统计度为1的结点个数 int OneChild(BiTree bt) int num1,num2; if(bt=NULL) return 0; else if(bt-lc

12、hild=NULL&bt-rchild!=NULL)| (bt-lchild!=NULL&bt-rchild=NULL) return 1; else num1=OneChild(bt-lchild); num2=OneChild(bt-rchild); return(num1+num2); 例9、统计度为2的结点个数 int TwoChild(BiTree bt) int num1,num2; if(bt=NULL) return 0; else num1=TwoChild(bt-lchild); num2=TwoChild(bt-rchild); if(bt-lchild!

13、=NULL&bt-rchild!=NULL) return (num1+num2+1); else return (num1+num2); 例10、判断一颗二叉树是否是满二叉树 int IsFull_BiTree(BiTree bt) BiTree QueueMAXNODE,p; int front,rear; int flag=0; if(bt=NULL) return TRUE; front=-1; rear=0; Queuerear=bt; while(front!=rear) front+; p=Queuefront; if(!p) flag=1; else if(flag)

14、return FALSE; else rear+;Queuerear=p-lchild;rear+;Queuerear=p-rchild; return TRUE; 例11、一棵n个结点的完全二叉树存放在二叉树的顺序存储结构中，试编写非递归算法对该树进行先根遍历。 按照题目要求，附加一个工作栈以完成对该树的非递归遍历，思路如下：（1）每访问一个结点，将此结点压入栈，查看此结点是否有左子树，若有，访问左子树，转（1）执行。（2）从栈弹出一结点，如果此结点有右子树，访问右子树并转第（1）步执行，否则转第（2）步执行。Void preorder(datatype an,int n ) INISTAC

15、K(sd); /*初始工作栈sd*/ I=1; PUSH(sd,0); If (i=n) visite(aI); /*访问此结点*/ PUSH(sd,I); J=2*I; /* 取左子树*/ While(!EMPTY(sd) /*若栈sd 非空*/ while(j=n) /*若2I=n,则该结点有左子树*/ PUSH(sd,j); /*进栈*/ I=j; j=2*I; /*取左子树*/ Visite(aI); /*访问此结点*/ I=pop(sd); /*出栈*/ J=2*I+1; /*取右子树*/ 例13、试编写一个将百分制转换成五分制的算法，要求其时间性能尽可能地高（即平均比较次数尽可能少

16、）。假定学生成绩的分布情况如下（）分数0-5960-6970-7980-8990-100比例0.00.1 void tran(float score) if(score=70) if(score=80) grade=C; /*7079 */ else if(score=60) grade=D; /*6069 */ else grade=E; /*059 */ （？哈夫曼树？）例14、设棵二叉树以二叉链表为存储结构，结点结构为lchild |data |rchild 。设计一个算法，求在前根序列中处于第k个位置的结点。 Bitreptr search(bitreptr t ,int k)if (t!=null)