習題課(樹與二叉樹)

1、精選優(yōu)質文檔-傾情為你奉上精選優(yōu)質文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質文檔-傾情為你奉上專心-專注-專業(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 假定用兩個一維數(shù)組LN和RN作為有N個結點1，2,， N的二叉樹的存儲結構。Li和Ri分別指示結點 i的左兒子和右兒子；Li=0（Ri=0）表示i的左（

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

3、數(shù)組T，并判斷結點U是否是結點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利用棧的基本操作寫出先序遍歷二叉樹的非遞歸算法，要求進棧的元素最少。 【山東科技大學 2002 四、 (10分)】解：題目分析 先序遍歷二叉樹的非遞歸算法，要求進棧元素少，意味著空指針不進棧。void PreOrder(Bitree bt) /對二叉樹bt進行非遞歸先序遍歷int top=0; Bitree s; /top是棧s的棧頂指針，棧中元素是樹結點指針，棧容量足夠大 while(bt!=null | top0) while(bt

5、!=null) coutdata; /訪問根結點if(bt-rchlid) s+top=bt-rchild; /若有右子女，則右子女進棧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設一棵二叉樹以二叉鏈表為存貯結構，結點結構為(lchild, data,rchild)，設計一個算法將二叉樹中所有結點的左，右子樹相互交換?！靖Ｖ荽髮W 1998 四、2 (10分)】解： void exchange(BiTree &bt)/將二叉樹bt所有結點的左右子樹交換 if(bt) BiTree s； s=bt-lchild; bt-lchild=bt-rchild; bt-rchild=s; /左右子女交換 exchange(bt-lchild);/交換左子樹上所有結點左右子樹 exchange(bt-rchild);/交換右子樹上所有結點左右子樹 算法討論將

7、上述算法中兩個遞歸調(diào)用語句放在前面，將交換語句放在最后，則是以后序遍歷方式交換所有結點的左右子樹。中序遍歷不適合本題。下面是本題的非遞歸算法void exchange(BiTree &bt) /交換二叉樹中各結點的左右孩子的非遞歸算法int top=0; BiTree s,t,p; /s是二叉樹的結點指針的棧，容量足夠大 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) / 結束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)/在先序后繼線索二叉樹中查找結點p的先序后繼if(p-

9、ltag=Link) return p-lchild; else return p-rchild;6.57 BiThrTree ex657(BiThrTree p)/在后序后繼線索二叉樹中查找結點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、叉樹采用二叉鏈表存儲：（1）編寫計算整個二叉樹高度的算法（二叉樹的高度也叫二叉樹的深度）。（2）編寫計算二叉樹最大寬度的算法（二叉樹的最大寬度是二叉樹所有層中結點個數(shù)的最大值）?！疚鞅贝髮W 2001 四】解：題目分析 求二叉樹高度的算法略。求最大寬度可采用層次遍歷的方法，記下各層結點數(shù)，每層遍歷完畢，若結點數(shù)大于原先最大寬度，則修改最大寬度。int Width(BiTree bt)/求二叉樹bt的最大寬度if (bt=null) return (0); /空二叉樹寬度為0 else BiTree Q;/Q是隊列,元素為二叉樹結點指針,容量足夠大front=1;rear=1;last=1;/fr

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

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

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

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

15、次出現(xiàn)結點為空 if (p-rchild & !tag) EnQueue(Q,p-rchild); /右子女入隊 else if (p-rchild) return 0; else tag=1; /while return 1; /JudgeComplete算法討論完全二叉樹證明還有其它方法。判斷時易犯錯誤是證明其左子樹和右子數(shù)都是完全二叉樹，由此推出整棵二叉樹必是完全二叉樹的錯誤結論。例3已知一棵二叉樹的中序序列和后序序列，寫一個建立該二叉樹的二叉鏈表存儲結構的算法?！緰|北大學 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分別是兩序列第一和最后結點的下標*/BiTree bt=(BiTree)malloc(sizeof(BiNode); bt-data=posth2;/后序遍歷序列最后的元素是根結點 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個結點二叉樹的中序遍歷序列與后序遍歷序列分別存放于數(shù)組IN1：n和POST1：n中，（設二叉樹各結點的數(shù)據(jù)值均不相同）。請寫一建立該二叉樹的二叉鏈表結構的非遞歸算法。該二叉鏈表的鏈結點結構為(lchild,data,rchild)，其中data為數(shù)據(jù)域，lchild與rhild分別為指向結點左、右孩子的指針（當孩子結點不存在時，相應指針域為空，用NULL表示）?！颈本┖娇蘸教齑髮W 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分別是中序序列和后序序列第一和最后元素的下標，初始調(diào)用時，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; /根結點的值 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)/結束InPostCreat例5編程求以孩子兄弟表示法存儲的森林的葉子結點數(shù)。要求描述結構。【北京工業(yè)大學2000五(10分)】【北京輕工業(yè)學院2000四(15分)】解：題目分析當森林（樹）以孩子兄弟表示法存儲時，若結點沒有孩子（firstchild=null）,則它必是葉子

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

22、返回葉子結點和其兄弟子樹中的葉子結點數(shù)else /孩子子樹和兄弟子樹中葉子數(shù)之和return(Leaves(t-firstchild)+Leaves(t-nextsibling); /結束Leaves例6以孩子兄弟鏈表為存儲結構，請設計遞歸和非遞歸算法求樹的深度?！颈狈浇煌ù髮W1999五(18分)】【南京航空航天大學 2000 九】解：題目分析由孩子兄弟鏈表表示的樹，求高度的遞歸模型是：若樹為空，高度為零；若第一子女為空，高度為1和兄弟子樹的高度的大者；否則，高度為第一子女樹高度加1和兄弟子樹高度的大者。其非遞歸算法使用隊列，逐層遍歷樹，取得樹的高度。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 / 結點既有第一子女又有兄弟，高度取子女高度+1和兄弟子樹高度的大者hc=Height(bt-firstchild)；/第一子女樹高hs=Height(bt-nextsibling)；/兄弟樹高if(hc+1hs)return(hc+1);else return (hs); /結束

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

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

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

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

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

29、ead,prevoid CreatLeafList(BiTree bt) /將BiTree 樹中所有葉子結點鏈成帶頭結點的雙鏈表if（bt） /若bt不空 CreatLeafList（bt-lchild）; /中序遍歷左子樹 if(bt-lchild=null & bt-rchild=null) /葉子結點 if(head=null)/第一個葉子結點head=(BiTree)malloc(sizeof(BiNode); head-lchild=null; head-rchild=bt; /頭結點的左鏈為空,右鏈指向第一個葉子結點 bt-lchild=head; pre=bt; /第一個葉子結點左鏈指向頭結點，pre指向當前葉子結點 else /已不是第一個葉子結點 pre-rchild=bt; bt-lchild=pre; pre=bt; /當前葉子結點鏈入雙鏈表 CreatLeafList(bt-rchild); /中序遍歷右子樹pre-rchild=null; /最后一個葉子結點的右鏈置空（鏈表結束標記） /if(bt) /結束CreatLeafList例33寫出在中序線索二叉樹里；找指定結點在后序下的前驅結點的算法。【河海大學1998