1、Chap006樹(shù)和二叉樹(shù)習(xí)題講解二叉樹(shù)的二叉鏈表類(lèi)型定義：二叉樹(shù)的二叉鏈表類(lèi)型定義：typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;樹(shù)的二叉鏈表類(lèi)型定義：樹(shù)的二叉鏈表類(lèi)型定義：typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;1.(6.33) 假定用兩個(gè)一維數(shù)組Ln+1和Rn+1作為有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的存儲(chǔ)結(jié)

2、構(gòu)，Li和Ri分別指示結(jié)點(diǎn)i(i=1,2,n)的左孩子和右孩子，0表示空。試寫(xiě)一個(gè)算法判別結(jié)點(diǎn)u是否為結(jié)點(diǎn)v的子孫。o 分析：u是否為v的子孫從結(jié)點(diǎn)v出發(fā)遍歷是否能達(dá)到u， “訪問(wèn)”判斷u是否為v的孩子Status Descendant(int L,int R,int u,int v)/在孩子存儲(chǔ)結(jié)構(gòu)上判斷u是否v的子孫 if(u&v) if(Lv=u|Rv=u) return true; else if(descendent(L,R,u,Lv) return true; else return(descendent(L,R,u,Rv); else return false; 2.（6

3、.41）編寫(xiě)遞歸算法，在二叉樹(shù)中求位于先序序列中第k個(gè)位置的結(jié)點(diǎn)的值。 int c,k; /這里把k和計(jì)數(shù)器c作為全局變量處理 void Get_PreSeq(Bitree T)/求先序序列為k的結(jié)點(diǎn)的值 if(T) c+; /每訪問(wèn)一個(gè)子樹(shù)的根都會(huì)使先序序號(hào)計(jì)數(shù)器加1 if(c=k) printf(Value is %dn,T-data); exit (1); else Get_PreSeq(T-lchild); /在左子樹(shù)中查找 Get_PreSeq(T-rchild); /在右子樹(shù)中查找 /if/Get_PreSeq main() . scanf(%d,&k); c=0; /在主

4、函數(shù)中調(diào)用前,要給計(jì)數(shù)器賦初值0 Get_PreSeq(T,k); ./main 3.（6.45）編寫(xiě)遞歸算法：對(duì)于二叉樹(shù)中每一個(gè)元素值為x的結(jié)點(diǎn)，刪去以它為根的子樹(shù)，并釋放相應(yīng)的空間。分析:1.在先序遍歷二叉樹(shù)的過(guò)程中查找每一個(gè)元素值為x的結(jié)點(diǎn)2.修改其雙親結(jié)點(diǎn)的相應(yīng)指針。3.釋放以它為根的子樹(shù)上的所有結(jié)點(diǎn)，則應(yīng)該后序遍歷以它為根的子樹(shù)。void Del_Sub_x(Bitree &T,ElemType x)/刪除所有以元素x為根的子樹(shù) if T if(T-data=x) Del_Sub(T); T=NULL; /刪除該子樹(shù) else /在左右子樹(shù)中繼續(xù)查找 Del_Sub_x(T-

5、lchild,x); Del_Sub_x(T-rchild,x); /else /Del_Sub_x void Del_Sub(Bitree T)/刪除子樹(shù)T if(T-lchild) Del_Sub(T-lchild); if(T-rchild) Del_Sub(T-rchild); free(T);/Del_Sub 4.（6.47）編寫(xiě)按層次順序（同一層自左至右）遍歷二叉樹(shù)的算法。分析： 按層次遍歷的原則是先被訪問(wèn)的結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)先被訪問(wèn)，因此在遍歷過(guò)程中需利用具有先進(jìn)先出特性的隊(duì)列對(duì)二叉樹(shù)：void LayerOrder(Bitree T)/層序遍歷二叉樹(shù) InitQueue(Q);

6、 /置空的輔助隊(duì)列Q if (T) 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); /LayerOrder對(duì)樹(shù)：即為孩子兄弟鏈表void LayerOrder(CStree T)/層序遍歷二叉樹(shù) InitQueue(Q); /置空的輔助隊(duì)列Q if (T) EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p); visit(p); for(q=p-f

7、irstchild;q;q=q-nextsibling) if(q) EnQueue(Q,q); /LayerOrder 5.（6.59）編寫(xiě)算法完成下列操作：無(wú)重復(fù)地輸出以孩子兄弟鏈表存儲(chǔ)的樹(shù)T中所有的邊。輸出的形式為（k1,k2）,（ki,kj）,，其中，ki和kj為樹(shù)結(jié)點(diǎn)中的結(jié)點(diǎn)標(biāo)識(shí)。o分析：在孩子兄弟鏈表中，哪些結(jié)點(diǎn)是根的孩子？abecgdVoid OutEdge(CSTree T)If (T) P=T-firstchild; While (p) Printf(T-data,p-data);OutEdge(p); p=p-nextsibling; /先根遍歷輸出樹(shù)中各條邊上圖中的輸出次

8、序：(a,b)(b,e)(b,g)(a,c)(a,d)或void Print_CSTree(CSTree T)/輸出孩子兄弟鏈表表示的樹(shù)T的各邊 for(child=T-firstchild;child;child=child-nextsibling) printf(%c,%c),T-data,child-data); Print_CSTree(child); /Print_CSTree 6.編寫(xiě)非遞歸算法實(shí)現(xiàn)：在樹(shù)T中查找結(jié)點(diǎn)X并求出其度數(shù)。 分析：度數(shù)為結(jié)點(diǎn)x的firstchild結(jié)點(diǎn)及孩子結(jié)點(diǎn)的所有nextsibling結(jié)點(diǎn)的個(gè)數(shù)和。xbcdstatus Degree_X_in_T(CS

9、Tree T,int &d) / 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，遍歷樹(shù)T查找結(jié)點(diǎn)X，若未找到，則返回ERROR，否則計(jì)算其度數(shù)并賦值給參數(shù)d，再返回OKinitStack(S); Push(S,T); /根指針進(jìn)棧flag=0;while(!StackEmpty(S) /當(dāng)棧S不空時(shí) while(GetTop(S,p) &p) Push(S,p-firstchild); /孩子入棧，向左走到盡頭 Pop(S,p); /空指針出棧 if (!StackEmpty(S) /訪問(wèn)結(jié)點(diǎn)，向右一步 Pop(S,p); if (p-data= =X) flag=1;break;/找到結(jié)點(diǎn)找到結(jié)點(diǎn)X Push(S,