chap006樹和二叉樹習(xí)題講解

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

2、構(gòu)，Li和Ri分別指示結(jié)點(diǎn)i(i=1,2,n)的左孩子和右孩子，0表示空。試寫一個算法判別結(jié)點(diǎn)u是否為結(jié)點(diǎn)v的子孫。o 分析：u是否為v的子孫從結(jié)點(diǎn)v出發(fā)遍歷是否能達(dá)到u， “訪問”判斷u是否為v的孩子Status Descendant(int L,int R,int u,int v)/在孩子存儲結(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）編寫遞歸算法，在二叉樹中求位于先序序列中第k個位置的結(jié)點(diǎn)的值。 int c,k; /這里把k和計數(shù)器c作為全局變量處理 void Get_PreSeq(Bitree T)/求先序序列為k的結(jié)點(diǎn)的值 if(T) c+; /每訪問一個子樹的根都會使先序序號計數(shù)器加1 if(c=k) printf(Value is %dn,T-data); exit (1); else Get_PreSeq(T-lchild); /在左子樹中查找 Get_PreSeq(T-rchild); /在右子樹中查找 /if/Get_PreSeq main() . scanf(%d,&k); c=0; /在主

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

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

6、 /置空的輔助隊列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對樹：即為孩子兄弟鏈表void LayerOrder(CStree T)/層序遍歷二叉樹 InitQueue(Q); /置空的輔助隊列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）編寫算法完成下列操作：無重復(fù)地輸出以孩子兄弟鏈表存儲的樹T中所有的邊。輸出的形式為（k1,k2）,（ki,kj）,，其中，ki和kj為樹結(jié)點(diǎn)中的結(jié)點(diǎn)標(biāo)識。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; /先根遍歷輸出樹中各條邊上圖中的輸出次

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

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