習(xí)題課(樹與二叉樹)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)第六章 樹和二叉樹6.33 int ex633(int u,int v)/判斷u是否v的子孫,是返回1,否則返回0if(u=v) return 1; else if(Lv) if (ex633(u,Lv) return 1; if(Rv) if (ex633(u,Rv) return 1; return 0; 6.34 假定用兩個(gè)一維數(shù)組LN和RN作為有N個(gè)結(jié)點(diǎn)1，2,， N的二叉樹的存儲(chǔ)結(jié)構(gòu)。Li和Ri分別指示結(jié)點(diǎn) i的左兒子和右兒子；Li=0（Ri=0）表示i的左（

2、右）兒子為空。試寫一個(gè)算法，由L和R建立一個(gè)一維數(shù)組TN，使Ti存放結(jié)點(diǎn)i的父親；然后再寫一個(gè)判別結(jié)點(diǎn)U是否為結(jié)點(diǎn)V的后代的算法?！竟枮I工業(yè)大學(xué) 1999 七 (14分)】【華南師范大學(xué)2000 六(17分)】解：題目分析由指示結(jié)點(diǎn)i 左兒子和右兒子的兩個(gè)一維數(shù)組Li和Ri，很容易建立指示結(jié)點(diǎn)i 的雙親的一維數(shù)組Ti，根據(jù)T數(shù)組，判斷結(jié)點(diǎn)U是否是結(jié)點(diǎn)V后代的算法，轉(zhuǎn)為判斷結(jié)點(diǎn)V是否是結(jié)點(diǎn)U的祖先的問題。int Generate(int U,int V,int N,int L,int R,int T)/*L和R是含有N個(gè)元素且指示二叉樹結(jié)點(diǎn)i左兒子和右兒子的一維數(shù)組，本算法據(jù)此建立結(jié)點(diǎn)i的雙親

3、數(shù)組T，并判斷結(jié)點(diǎn)U是否是結(jié)點(diǎn)V的后代。*/for(i=1;i=N;i+) Ti=0; /T數(shù)組初始化 for (i=1;i=N;i+) /根據(jù)L和R填寫T if(Li!=0) TLi=i; /若i的左子女是L，則L的雙親是i for(i=1;ilchild,T2-lchild);b2=ex636(T1-rchild,T2-rchild); return b1&b2; 6.37 void ex637(BiTree T)/先序遍歷二叉樹的非遞歸算法InitStack(S); Push(S,T); while(!StackEmpty(S) while(GetTop(S,p)&p) coutdata

4、; push(S,p-lchild); pop(S,p); if(!StackEmpty(S) pop(S,p); push(S,p-rchild); 6.37利用棧的基本操作寫出先序遍歷二叉樹的非遞歸算法，要求進(jìn)棧的元素最少。 【山東科技大學(xué) 2002 四、 (10分)】解：題目分析 先序遍歷二叉樹的非遞歸算法，要求進(jìn)棧元素少，意味著空指針不進(jìn)棧。void PreOrder(Bitree bt) /對(duì)二叉樹bt進(jìn)行非遞歸先序遍歷int top=0; Bitree s; /top是棧s的棧頂指針，棧中元素是樹結(jié)點(diǎn)指針，棧容量足夠大 while(bt!=null | top0) while(bt

5、!=null) coutdata; /訪問根結(jié)點(diǎn)if(bt-rchlid) s+top=bt-rchild; /若有右子女，則右子女進(jìn)棧bt=bt-lchild; if (top0) bt=stop-; 6.38 void ex638(BiTree T)/后序遍歷二叉樹的非遞歸算法,用棧 BiTree s100; char tag100; p=T;top=0; do while(p)tagtop=L;stop=p;top+;p=p-lchild; while(top0&tagtop-1=R)top-;p=stop;coutdata0)tagtop-1=R;p=stop-1-rchild;whi

6、le(top0);6.43設(shè)一棵二叉樹以二叉鏈表為存貯結(jié)構(gòu)，結(jié)點(diǎn)結(jié)構(gòu)為(lchild, data,rchild)，設(shè)計(jì)一個(gè)算法將二叉樹中所有結(jié)點(diǎn)的左，右子樹相互交換。【福州大學(xué) 1998 四、2 (10分)】解： void exchange(BiTree &bt)/將二叉樹bt所有結(jié)點(diǎn)的左右子樹交換 if(bt) BiTree s； s=bt-lchild; bt-lchild=bt-rchild; bt-rchild=s; /左右子女交換 exchange(bt-lchild);/交換左子樹上所有結(jié)點(diǎn)左右子樹 exchange(bt-rchild);/交換右子樹上所有結(jié)點(diǎn)左右子樹 算法討論將

7、上述算法中兩個(gè)遞歸調(diào)用語句放在前面，將交換語句放在最后，則是以后序遍歷方式交換所有結(jié)點(diǎn)的左右子樹。中序遍歷不適合本題。下面是本題的非遞歸算法void exchange(BiTree &bt) /交換二叉樹中各結(jié)點(diǎn)的左右孩子的非遞歸算法int top=0; BiTree s,t,p; /s是二叉樹的結(jié)點(diǎn)指針的棧，容量足夠大 if(bt) s+top=bt;while(top0) t=stop-;if(t-lchild|t-rchild)p=t-lchild;t-lchild=t-rchild; t-rchild=p;/交換左右子樹 if(t-lchild) s+top=t-lchild; /左子

8、女入棧 if(t-rchild) s+top=t-rchild; /右子女入棧 /while(top0)/if(bt) / 結(jié)束exchange6.47 void ex647(BiTree T)/層序遍歷二叉樹InitQueue(Q);EnQueue(Q,T);while(!QueueEmpty(Q)DeQueue(Q,p);coutdata;if(p-lchild) EnQueue(Q,p-lchild);if(p-rchild) EnQueue(Q,p-rchild); 6.56 BiThrTree ex656(BiThrTree p)/在先序后繼線索二叉樹中查找結(jié)點(diǎn)p的先序后繼if(p-

9、ltag=Link) return p-lchild; else return p-rchild;6.57 BiThrTree ex657(BiThrTree p)/在后序后繼線索二叉樹中查找結(jié)點(diǎn)p的后序后繼,并返回指針if(!p-parent) return NULL; else if(p=p-parent-lchild&p-parent-rchild) q=p-parent-rchild; while(q-lchild|q-rchild) if(q-lchild) q=q-lchild; else q=q-rchild; return q; else return p-parent;例1二

10、叉樹采用二叉鏈表存儲(chǔ)：（1）編寫計(jì)算整個(gè)二叉樹高度的算法（二叉樹的高度也叫二叉樹的深度）。（2）編寫計(jì)算二叉樹最大寬度的算法（二叉樹的最大寬度是二叉樹所有層中結(jié)點(diǎn)個(gè)數(shù)的最大值）?！疚鞅贝髮W(xué) 2001 四】解：題目分析 求二叉樹高度的算法略。求最大寬度可采用層次遍歷的方法，記下各層結(jié)點(diǎn)數(shù)，每層遍歷完畢，若結(jié)點(diǎn)數(shù)大于原先最大寬度，則修改最大寬度。int Width(BiTree bt)/求二叉樹bt的最大寬度if (bt=null) return (0); /空二叉樹寬度為0 else BiTree Q;/Q是隊(duì)列,元素為二叉樹結(jié)點(diǎn)指針,容量足夠大front=1;rear=1;last=1;/fr

11、ont頭指針,rear尾指針,last同層最右結(jié)點(diǎn)在隊(duì)列中的位置temp=0; maxw=0; /temp記局部寬度, maxw記最大寬度 Qrear=bt; /根結(jié)點(diǎn)入隊(duì)列 while(frontlchild!=null) Q+rear=p-lchild; /左子女入隊(duì) if(p-rchild!=null) Q+rear=p-rchild; /右子女入隊(duì) if (frontlast) /一層結(jié)束 last=rear; if(tempmaxw) maxw=temp; /last指向下層最右元素, 更新當(dāng)前最大寬度 temp=0;/if /while return (maxw);/結(jié)束width

12、例2要求二叉樹按二叉鏈表形式存儲(chǔ)，（1）寫一個(gè)建立二叉樹的算法。（2）寫一個(gè)判別給定的二叉樹是否是完全二叉樹的算法。完全二叉樹定義為：深度為K，具有N個(gè)結(jié)點(diǎn)的二叉樹的每個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至N的結(jié)點(diǎn)一一對(duì)應(yīng)。此題以此定義為準(zhǔn)?！疚鞅贝髮W(xué) 2000 六 (12分)】【青島海洋大學(xué) 1999 六(15分)】【南京航空航天大學(xué)2001十(10分)】【北方交通大學(xué) 1997 八 (20分)】【哈爾濱工業(yè)大學(xué) 2000 十一 (14分)】【南開大學(xué) 1997 四 (16分)】【北京郵電大學(xué) 1994 九 (20分)】解：題目分析二叉樹是遞歸定義的，以遞歸方式建立最簡(jiǎn)單。判定是否是完全二

13、叉樹，可以使用隊(duì)列，在遍歷中利用完全二叉樹“若某結(jié)點(diǎn)無左子女就不應(yīng)有右子女”的原則進(jìn)行判斷。BiTree Creat() /建立二叉樹的二叉鏈表形式的存儲(chǔ)結(jié)構(gòu)int x；BiTree bt; scanf(“%d”,&x); /本題假定結(jié)點(diǎn)數(shù)據(jù)域?yàn)檎?if(x=0) bt=null; else if(x0) bt=(BiNode *)malloc(sizeof(BiNode);bt-data=x; bt-lchild=creat();bt-rchild=creat(); else error(“輸入錯(cuò)誤”)； return(bt);/結(jié)束 BiTreeint JudgeComplete(BiT

14、ree bt) /判斷二叉樹是否是完全二叉樹,如是，返回1，否則，返回0int tag=0; BiTree p=bt, Q; / Q是隊(duì)列，元素是二叉樹結(jié)點(diǎn)指針，容量足夠大 if(p=null) return (1); InitQueue(Q); EnQueue(Q,p); /初始化隊(duì)列，根結(jié)點(diǎn)指針入隊(duì) while (!QueueEmpty(Q) p=DeQueue(Q); /出隊(duì) if (p-lchild & !tag) EnQueue(Q,p-lchild); /左子女入隊(duì) else if (p-lchild) return 0; /前邊已有結(jié)點(diǎn)為空，本結(jié)點(diǎn)不空else tag=1; /首

15、次出現(xiàn)結(jié)點(diǎn)為空 if (p-rchild & !tag) EnQueue(Q,p-rchild); /右子女入隊(duì) else if (p-rchild) return 0; else tag=1; /while return 1; /JudgeComplete算法討論完全二叉樹證明還有其它方法。判斷時(shí)易犯錯(cuò)誤是證明其左子樹和右子數(shù)都是完全二叉樹，由此推出整棵二叉樹必是完全二叉樹的錯(cuò)誤結(jié)論。例3已知一棵二叉樹的中序序列和后序序列，寫一個(gè)建立該二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)的算法。【東北大學(xué) 1999 六、3 （12分）】解：BiTree IntoPost(ElemType in,ElemType pos

16、t,int l1,int h1,int l2,int h2)/*in和post是二叉樹的中序序列和后序序列,l1,h1,l2,h2分別是兩序列第一和最后結(jié)點(diǎn)的下標(biāo)*/BiTree bt=(BiTree)malloc(sizeof(BiNode); bt-data=posth2;/后序遍歷序列最后的元素是根結(jié)點(diǎn) for(i=l1;ilchild=null; /處理左子樹 elsebt-lchild=IntoPost(in,post,l1,i-1,l2,l2+i-l1-1)； if(i=h1) bt-rchild=null; /處理右子樹 elsebt-rchild=IntoPost(in,pos

17、t,i+1,h1,l2+i-l1,h2-1); return(bt);例4已知具有n個(gè)結(jié)點(diǎn)二叉樹的中序遍歷序列與后序遍歷序列分別存放于數(shù)組IN1：n和POST1：n中，（設(shè)二叉樹各結(jié)點(diǎn)的數(shù)據(jù)值均不相同）。請(qǐng)寫一建立該二叉樹的二叉鏈表結(jié)構(gòu)的非遞歸算法。該二叉鏈表的鏈結(jié)點(diǎn)結(jié)構(gòu)為(lchild,data,rchild)，其中data為數(shù)據(jù)域，lchild與rhild分別為指向結(jié)點(diǎn)左、右孩子的指針（當(dāng)孩子結(jié)點(diǎn)不存在時(shí)，相應(yīng)指針域?yàn)榭?，用NULL表示）?！颈本┖娇蘸教齑髮W(xué) 1998 六 (15分)】解：題目分析已知二叉樹中序序列與后序序列，上題以遞歸算法建立了二叉樹，本題是非遞歸算法。void InPo

18、stCreat(BiTree &bt,ElemType IN,ElemType POST,int l1,int h1,int l2,int h2)/*由二叉樹的中序序列IN和后序序列POST建立二叉樹，l1,h1和l2,h2分別是中序序列和后序序列第一和最后元素的下標(biāo)，初始調(diào)用時(shí)，l1=l2=1,h1=h2=n。*/typedef struct int l1,h1,l2,h2; BiTree t; node; node s,p;/s為棧，容量足夠大 BiTree bt=(BiTree)malloc(sizeof(BiNode); int top=0,i; p.l1=l1; p.h1=h1; p

19、.l2=l2; p.h2=h2; p.t=bt; s+top=p;/初始化 while(top0) p=stop-; bt=p.t; l1=p.l1; h1=p.h1;l2=p.l2; h2=p.h2;/取出棧頂數(shù)據(jù) for(i=l1;idata=POSTh2; /根結(jié)點(diǎn)的值 if(i=l1) bt-lchild=null; /bt無左子樹 else /將建立左子樹的數(shù)據(jù)入棧bt-lchild=(BiTree)malloc(sizeof(BiNode); p.t=bt-lchild;p.l1=l1; p.h1=i-1; p.l2=l2; p.h2=l2+i-l1-1; s+top=p; if(

20、i=h1) bt-rchild=null; /bt無右子樹else/右子樹數(shù)據(jù)入棧bt-rchild=(BiTree)malloc(sizeof(BiNode); p.t=bt-rchild;p.l1=i+1; p.h1=h1; p.l2=l2+i-l1; p.h2=h2-1; s+top=p; / while(top0)/結(jié)束InPostCreat例5編程求以孩子兄弟表示法存儲(chǔ)的森林的葉子結(jié)點(diǎn)數(shù)。要求描述結(jié)構(gòu)?！颈本┕I(yè)大學(xué)2000五(10分)】【北京輕工業(yè)學(xué)院2000四(15分)】解：題目分析當(dāng)森林（樹）以孩子兄弟表示法存儲(chǔ)時(shí)，若結(jié)點(diǎn)沒有孩子（firstchild=null）,則它必是葉子

21、，總的葉子結(jié)點(diǎn)個(gè)數(shù)是孩子子樹（firstchild）上的葉子數(shù)和兄弟（nextsibling）子樹上葉結(jié)點(diǎn)個(gè)數(shù)之和。typedef struct CSNodeElemType data;/數(shù)據(jù)域struct CSNode *firstchild, *nextsibling;/孩子與兄弟域 CSNode,*CSTree;int Leaves (CSTree t)/計(jì)算以孩子-兄弟表示法存儲(chǔ)的森林的葉子數(shù)if(t=NULL)return(0); else if(t-firstchild=NULL) /若結(jié)點(diǎn)無孩子，則該結(jié)點(diǎn)必是葉子 return(1+Leaves(t-nextsibling); /

22、返回葉子結(jié)點(diǎn)和其兄弟子樹中的葉子結(jié)點(diǎn)數(shù)else /孩子子樹和兄弟子樹中葉子數(shù)之和return(Leaves(t-firstchild)+Leaves(t-nextsibling); /結(jié)束Leaves例6以孩子兄弟鏈表為存儲(chǔ)結(jié)構(gòu)，請(qǐng)?jiān)O(shè)計(jì)遞歸和非遞歸算法求樹的深度?！颈狈浇煌ù髮W(xué)1999五(18分)】【南京航空航天大學(xué) 2000 九】解：題目分析由孩子兄弟鏈表表示的樹，求高度的遞歸模型是：若樹為空，高度為零；若第一子女為空，高度為1和兄弟子樹的高度的大者；否則，高度為第一子女樹高度加1和兄弟子樹高度的大者。其非遞歸算法使用隊(duì)列，逐層遍歷樹，取得樹的高度。int Height(CSTree bt)

23、 /遞歸求以孩子兄弟鏈表表示的樹的深度int hc,hs; if (bt=null) return (0);else if (!bt-firstchild) hs= Height(bt-nextsibling); if(hs1)return(hs); else return (1);/子女空，查兄弟的深度 else / 結(jié)點(diǎn)既有第一子女又有兄弟，高度取子女高度+1和兄弟子樹高度的大者h(yuǎn)c=Height(bt-firstchild)；/第一子女樹高h(yuǎn)s=Height(bt-nextsibling)；/兄弟樹高if(hc+1hs)return(hc+1);else return (hs); /結(jié)束

24、Heightint Height(CSTree t) /非遞歸遍歷求以孩子兄弟鏈表表示的樹的深度if(t=null) return(0);elseint front=1,rear=1; /front,rear是隊(duì)頭隊(duì)尾元素的指針int last=1,h=0; /last指向樹中同層結(jié)點(diǎn)中最后一個(gè)結(jié)點(diǎn)，h是樹的高度 Qrear=t; /Q是以樹中結(jié)點(diǎn)為元素的隊(duì)列while(frontfirstchild) /第一子女入隊(duì)Q+rear=t-firstchild; t=t-nextsibling; /同層兄弟指針后移 if(frontlast)/本層結(jié)束，深度加1（初始深度為0） h+;last=r

25、ear; /last再移到指向當(dāng)前層最右一個(gè)結(jié)點(diǎn)/while(front=last) /else/Height例7假設(shè)以雙親表示法作樹的存儲(chǔ)結(jié)構(gòu)，寫出雙親表示的類型說明，并編寫求給定的樹的深度的算法。（注:已知樹中結(jié)點(diǎn)數(shù)）【清華大學(xué) 1994 七、 (15分)】解：題目分析 由于以雙親表示法作樹的存儲(chǔ)結(jié)構(gòu)，找結(jié)點(diǎn)的雙親容易。因此我們可求出每一結(jié)點(diǎn)的層次，取其最大層次即樹有深度。對(duì)每一結(jié)點(diǎn)，找其雙親，雙親的雙親，直至（根）結(jié)點(diǎn)雙親為0為止。int Depth(Ptree t) /求以雙親表示法為存儲(chǔ)結(jié)構(gòu)的樹的深度，Ptree的定義參看教材int maxdepth=0;for(i=1;i0) te

26、mp+; f=t.nodesf.parent; / 深度加1,并取新的雙親if(tempmaxdepth) maxdepth=temp; /最大深度更新return(maxdepth);/返回樹的深度 /結(jié)束Depth例25請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，要求該算法把二叉樹的葉子結(jié)點(diǎn)按從左到右的順序連成一個(gè)單鏈表，表頭指針為head。 二叉樹按二叉鏈表方式存儲(chǔ)，鏈接時(shí)用葉子結(jié)點(diǎn)的右指針域來存放單鏈表指針。分析你的算法的時(shí)、空復(fù)雜度。【華南師范大學(xué) 1999 六、2 （13分）】【清華大學(xué) 1997 三、 (10分)】解:題目分析葉子結(jié)點(diǎn)只有在遍歷中才能知道，這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點(diǎn)指針pre，初始為

27、空。第一個(gè)葉子結(jié)點(diǎn)由指針head指向，遍歷到葉子結(jié)點(diǎn)時(shí)，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點(diǎn)的rchild為空。LinkList head,pre=null; /全局變量LinkList InOrder(BiTree bt)/*中序遍歷二叉樹bt，將葉子結(jié)點(diǎn)從左到右鏈成一個(gè)單鏈表，表頭指針為head*/if(bt) InOrder(bt-lchild); /中序遍歷左子樹if(bt-lchild=null & bt-rchild=null) /葉子結(jié)點(diǎn)if(pre=null) head=bt; pre=bt; /處理第一個(gè)葉子結(jié)點(diǎn) elsepre-rchild=bt; pre=bt

28、; /將葉子結(jié)點(diǎn)鏈入鏈表InOrder(bt-rchild); /中序遍歷左子樹pre-rchild=null; /設(shè)置鏈表尾 return(head); /InOrder時(shí)間復(fù)雜度為O(n),輔助變量使用head和pre,棧空間復(fù)雜度O(n)例26編寫一算法，利用葉子結(jié)點(diǎn)中的空指針域?qū)⑺腥~子結(jié)點(diǎn)鏈接為一帶有頭結(jié)點(diǎn)的雙鏈表，算法返回頭結(jié)點(diǎn)的地址?！緰|北大學(xué) 1999 四(13分)】解:題目分析 “雙鏈”就利用二叉樹結(jié)點(diǎn)的左右指針，重新定義左指針為指向前驅(qū)的指針，右指針是指向后繼的指針，鏈表在遍歷中建立，下面采用中序遍歷二叉樹。BiTree head=null,pre; /全局變量鏈表頭指針h

29、ead,prevoid CreatLeafList(BiTree bt) /將BiTree 樹中所有葉子結(jié)點(diǎn)鏈成帶頭結(jié)點(diǎn)的雙鏈表if（bt） /若bt不空 CreatLeafList（bt-lchild）; /中序遍歷左子樹 if(bt-lchild=null & bt-rchild=null) /葉子結(jié)點(diǎn) if(head=null)/第一個(gè)葉子結(jié)點(diǎn)head=(BiTree)malloc(sizeof(BiNode); head-lchild=null; head-rchild=bt; /頭結(jié)點(diǎn)的左鏈為空,右鏈指向第一個(gè)葉子結(jié)點(diǎn) bt-lchild=head; pre=bt; /第一個(gè)葉子結(jié)點(diǎn)左鏈指向頭結(jié)點(diǎn)，pre指向當(dāng)前葉子結(jié)點(diǎn) else /已不是第一個(gè)葉子結(jié)點(diǎn) pre-rchild=bt; bt-lchild=pre; pre=bt; /當(dāng)前葉子結(jié)點(diǎn)鏈入雙鏈表 CreatLeafList(bt-rchild); /中序遍歷右子樹pre-rchild=null; /最后一個(gè)葉子結(jié)點(diǎn)的右鏈置空（鏈表結(jié)束標(biāo)記） /if(bt) /結(jié)束CreatLeafList例33寫出在中序線索二叉樹里；找指定結(jié)點(diǎn)在后序下的前驅(qū)結(jié)點(diǎn)的算法?！竞雍４髮W(xué)1998