第五六章程序題

1、 第五章、數(shù)組和廣義表習(xí)題 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; 第六章程序設(shè)計(jì)題 1、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù) 方法1. void CountLeaf (BiTree T, int& count)/ 先序遍歷二叉樹，以 count 返回二

3、叉樹中葉子結(jié)點(diǎn)的數(shù)目 if ( T ) if (!T-Lchild)& (!T-Rchild)count+; / 對(duì)葉子結(jié)點(diǎn)計(jì)數(shù) CountLeaf( T-Lchild, count); CountLeaf( T-Rchild, count); / if 方法2.int CountLeaf (BiTree T)/返回指針T所指二叉樹中所有葉子結(jié)點(diǎn)個(gè)數(shù) 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、統(tǒng)計(jì)所有結(jié)點(diǎn)的個(gè)數(shù)、統(tǒng)計(jì)所有結(jié)點(diǎn)的個(gè)數(shù)int Count (BiTree T)/返回指針T所指二叉樹中所有結(jié)點(diǎn)個(gè)數(shù) 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、求二叉樹的深度、求二叉樹的深度(后序遍歷后序遍歷)算法基本思想算法基本思想: : 從二叉樹深度的定義可知，二叉樹的二叉樹的深度應(yīng)為

5、其左、右子樹深度的最大值加深度應(yīng)為其左、右子樹深度的最大值加1 1。由此，需先分別求得左、右子樹的深度，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點(diǎn)”的操作為:求得左、求得左、右子樹深度的最大值，然后加右子樹深度的最大值，然后加 1 1 。 首先分析二叉樹的深度二叉樹的深度和它的左左、右子右子樹深度樹深度之間的關(guān)系。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 所指結(jié)點(diǎn)所在層次，其初值為1，depth 為當(dāng)前求得的最大層次,其初值為0if (T)if (leveldepth) depth=level; BiTreeDepth(T-Lchild, level+1, depth);BiTreeDepth(T-Rchild, level+1, depth);4、在二叉樹

7、上查詢某個(gè)結(jié)點(diǎn) void locate(BiTree T,ElemType x,BiTree& p)/ 若二叉樹 T 中存在和 x 相同的元素，則 p 指向該結(jié)點(diǎn)，否則 p 的值不變，p 的初值為 NULLif (T) if (T-data=x) p=T;locate(T-lchild, x, p);locate(T-rchild, x, p); 5: 5: 假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu), ,設(shè)計(jì)一個(gè)算法判斷兩棵設(shè)計(jì)一個(gè)算法判斷兩棵二叉樹是否相似二叉樹是否相似, ,所謂二叉樹所謂二叉樹t1t1和和t2t2是相似的指的是是相似的指的是t1t1和和t2t2都是空

8、的二叉樹；或者都是空的二叉樹；或者t1t1和和t2t2的根結(jié)點(diǎn)是相似的的根結(jié)點(diǎn)是相似的, ,以及以及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兩棵二叉樹相似時(shí)返回兩棵二叉樹相似時(shí)返回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個(gè)結(jié)點(diǎn)的完全二叉樹，已經(jīng)順序存儲(chǔ)在一維數(shù)組A1.n中，下面的算法是將A中順序存儲(chǔ)

11、的二叉樹變?yōu)槎骀湵泶鎯?chǔ)的完全二叉樹 #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、統(tǒng)計(jì)度為1的結(jié)點(diǎn)個(gè)數(shù) 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、統(tǒng)計(jì)度為2的結(jié)點(diǎn)個(gè)數(shù) 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個(gè)結(jié)點(diǎn)的完全二叉樹存放在二叉樹的順序存儲(chǔ)結(jié)構(gòu)中，試編寫非遞歸算法對(duì)該樹進(jìn)行先根遍歷。 按照題目要求，附加一個(gè)工作棧以完成對(duì)該樹的非遞歸遍歷，思路如下：（1）每訪問一個(gè)結(jié)點(diǎn)，將此結(jié)點(diǎn)壓入棧，查看此結(jié)點(diǎn)是否有左子樹，若有，訪問左子樹，轉(zhuǎn)（1）執(zhí)行。（2）從棧彈出一結(jié)點(diǎn)，如果此結(jié)點(diǎn)有右子樹，訪問右子樹并轉(zhuǎn)第（1）步執(zhí)行，否則轉(zhuǎn)第（2）步執(zhí)行。Void preorder(datatype an,int n ) INISTAC

15、K(sd); /*初始工作棧sd*/ I=1; PUSH(sd,0); If (i=n) visite(aI); /*訪問此結(jié)點(diǎn)*/ PUSH(sd,I); J=2*I; /* 取左子樹*/ While(!EMPTY(sd) /*若棧sd 非空*/ while(j=n) /*若2I=n,則該結(jié)點(diǎn)有左子樹*/ PUSH(sd,j); /*進(jìn)棧*/ I=j; j=2*I; /*取左子樹*/ Visite(aI); /*訪問此結(jié)點(diǎn)*/ I=pop(sd); /*出棧*/ J=2*I+1; /*取右子樹*/ 例13、試編寫一個(gè)將百分制轉(zhuǎn)換成五分制的算法，要求其時(shí)間性能盡可能地高（即平均比較次數(shù)盡可能少

16、）。假定學(xué)生成績(jī)的分布情況如下（）分?jǐn)?shù)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、設(shè)棵二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)結(jié)構(gòu)為lchild |data |rchild 。設(shè)計(jì)一個(gè)算法，求在前根序列中處于第k個(gè)位置的結(jié)點(diǎn)。 Bitreptr search(bitreptr t ,int k)if (t!=null)