上傳人：紅***

認(rèn)證信息

認(rèn)證類型：個人認(rèn)證

認(rèn)證主體：楊**（實名認(rèn)證）

IP屬地：江西

IP屬地：江西 上傳時間：2022-07-21 格式：PPT 頁數(shù)：35 大小：664KB 積分：8.4 舉報 版權(quán)申訴

1、第四章習(xí)題作業(yè)4-2由三個結(jié)點A、B、C可以構(gòu)成多少棵不同的樹？不同的二叉樹？二叉樹區(qū)分左右子樹 9種， 30種21作業(yè)4-3判斷：一棵二叉樹的所有葉結(jié)點在先根、中根和后根次序下的排列都按相同的相對位置出現(xiàn)。正確，按照先左后右的順序。作業(yè)4-5判別給定二叉樹是否為完全二叉樹。完全二叉樹：按層次順序編號其中的結(jié)點，對應(yīng)于滿二叉樹中的那些結(jié)點。高為k的完全二叉樹第k-1層是滿的，第k層如有空缺，則結(jié)點集中在最左邊。123456按層次順序遍歷樹的結(jié)點，判斷：無左、有右孩子，則不是完全二叉樹 (結(jié)點1)無左、無右孩子，則記錄狀態(tài)，判斷后續(xù)結(jié)點是否有孩子。對于完全二叉樹，后續(xù)結(jié)點不能有孩子。(結(jié)點2)有

2、左、右孩子，則繼續(xù)下一結(jié)點。(結(jié)點5)有左、無右孩子，則記錄狀態(tài)，判斷后續(xù)結(jié)點是否有孩子。對于完全二叉樹，后續(xù)結(jié)點不能有孩子。(結(jié)點6)變量M變量Sint complete(BinTreeNode *t) AQueue q; /隊列 bool S=1; bool M=1; if( t!=null) /根結(jié)點非空 q.QInsert(t); while(! q.IsEmpty() ) /隊列非空 q.QDelete(p); /取出元素p if(p-left=null) if(p-right!=null) then M=0; return M; else S=0; /記錄狀態(tài) else q.QIn

3、sert(p-left); if(p-right=null) then S=0; /記錄狀態(tài) else q.QInsert(p-right); 作業(yè)4-6編寫算法求任意二叉樹中一條最長的路徑，并輸出此路徑上各結(jié)點的值。（最左的一條路徑）（從根結(jié)點到任意點的路徑）非遞歸的后根遍歷算法 設(shè)置一個工作棧： 結(jié)點所處狀態(tài)i = 0, 1或2： 0：結(jié)點及左右子樹均未被訪問； 1：遍歷左子樹； 2：遍歷右子樹。樹中任一結(jié)點q都需進棧三次，出棧三次。第一次出棧是為遍歷結(jié)點q的左子樹，第二次出棧是為遍歷結(jié)點q的右子樹，第三次出棧是為訪問結(jié)點q . 結(jié)點 結(jié)點狀態(tài) i 當(dāng)結(jié)點狀態(tài)為2，且結(jié)點為棧頂元素時，棧中

4、存放了根結(jié)點到該結(jié)點的路徑。這樣可以得到所有結(jié)點到根節(jié)點的路徑。(綠色圓圈)當(dāng)結(jié)點狀態(tài)為2，且當(dāng)前結(jié)點為葉子結(jié)點時，棧中存放一條從根到葉子結(jié)點的路徑。(紅色圓圈)變量m記錄最長路徑的長度，數(shù)組long存放最長路徑中的結(jié)點；每次當(dāng)前結(jié)點的狀態(tài)為2，且是葉子結(jié)點時，看棧中元素個數(shù)，若大于m，則將此時棧中元素存入long中。算法NPOS(t. path)N1建立堆棧 CREATS(S). CREATS(tmp). N2特殊情況 IF t=NULL RETURN.N3初始化 S (t,0). m0. N4利用棧實現(xiàn)遞歸 WHILE NOT(StackEmpty(S) DO ( (P,i) S. /彈出

5、元素 IF i=0 THEN ( S (P,1). IF left(P) null THEN S (left(P),0) . ) IF i=1 THEN ( S (P,2). IF right (P) null THEN S(right(P),0). ) IF i=2 THEN IF(left(P) =null AND right(P)=null AND S.topm) THEN ( j 0. long 0Data(P). m S.top. WHILE( !S.IsEmpty() DO (q pop(S). longj Data(q). tmp.push(q). j+.） WHILE( !tm

6、p.IsEmpty() DO （q pop(tmp). S.push(q).） ) . ). ) 總結(jié)1所有路徑 總結(jié)2最左路徑存儲路徑棧S遍歷的結(jié)點； 棧I-對應(yīng)結(jié)點的遍歷情況，左子結(jié)點遍歷 則為0，右子結(jié)點遍歷則為1。盡量向深層搜索開始一直找左子結(jié)點，將結(jié)點入棧S，且結(jié)點狀態(tài)為0，入棧I；（結(jié)點A）無左子結(jié)點時，將棧S頂部結(jié)點狀態(tài)變?yōu)?，找該結(jié)點的右子節(jié)點，再繼續(xù)上步操作；當(dāng)前結(jié)點為空時，看棧頂元素，若狀態(tài)為1，則查看棧S中元素個數(shù)，若大于當(dāng)前最大長度，則更新最大長度值，更新數(shù)組path。ABCVoid Longpath(BinTreeNode *t, int size) BinTreeN

7、ode * Ssize; int Isize; BinTreeNode *now;/當(dāng)前結(jié)點的指針 int m, top; /最長路徑長度，棧頂指針 char pathsize;/保存最長路徑的數(shù)組 now=t; top=0; m=0; if(t=null) return. if(t-left=null)&(t-right=null) return. while(now!=null | top 0) while(now!=null) top+, Stop=now; Itop=0; now=now-left; /沿左分支向下 /當(dāng)前結(jié)點無左子節(jié)點If( top0) if(Itop=1) If(S

8、top-left=null)&(Stop right=null) &(topm) /葉子結(jié)點且 for(int i=1;idata; m=top; top-; else /棧頂元素狀態(tài)為0 now=Spop; if(top0) now=now-right; Itop=1; For(int i=1;i=m;i+) coutpathi; cout“l(fā)ength=”maxd) maxd=d; p=NextBrother(p); Return maxd+1;作業(yè)4-12構(gòu)造權(quán)值為5，13，21，7，18，31，41的哈夫曼樹。5713拓?fù)渑判?若圖中存在邊，則在拓?fù)湫蛄兄衯i在vj之前?；静襟E： 從

9、圖中選擇一個入度為0的頂點且輸出之。 從圖中刪除該頂點及其所有出邊。執(zhí)行 ，直至所有頂點已輸出，或圖中剩余頂點入度均不為0 (說明圖中存在回路，無法繼續(xù)拓?fù)渑判?思想：數(shù)組count存放各個結(jié)點的入度， 找到count中所有入度為0的頂點并入棧； 棧頂取出一個頂點，輸出，刪除該頂點及所有出邊，更改其余頂點的入度信息。ABCDE011120A0021BCDE121CBED0111 BED寬度優(yōu)先遍歷00343 E D不為棧另外分配存儲空間，而是直接利用入度為0的頂點對應(yīng)的count數(shù)組元素值來模擬堆棧的壓入和彈出。 方法：設(shè)置一個指針top，指示棧頂位置；初始時，top=-1，表示棧空；當(dāng)頂點i

10、的入度為0，需要入棧時，將指針?biāo)傅捻旤c序號放在counti中，即counti=top; 更新top，令其指向頂點i，即top=i；當(dāng)彈出頂點時，記錄棧頂位置，j=top; top退到次棧頂位置，即top=counttop;入棧操作：counti=top； top=i。頂點1，即i=1；則count1=-1，top=1；假設(shè)頂點3的入度變?yōu)?，將其入棧，即i=3；則count3=1； top=3； 棧元素為頂點3和頂點1。出棧操作： j=top；top=counttop。j=3，top=count3=1; 新棧頂為頂點1。30152 0 1 2 3 4 52Count數(shù)組：頂點的入度3-115

11、223-115023-11512算法TopoOrder(n) TOrder1初始化 /* 計算count數(shù)組 */ FOR i = 0 TO n-1 DO counti 0. FOR i = 0 TO n-1 DO ( p adjacent( Headi ) . WHILE p DO (countVerAdj(p) countVerAdj(p)+1. p link (p). ) )Head-頂點表；adjacent-邊鏈表頭指針VerAdj(p)-p所指的頂點序號325140002123013425count02431524235355拓?fù)渑判蛩惴ǎ?top -1. /棧頂指針top FOR

12、i = 0 TO n-1 DO/入度為0的頂點入棧IF counti = 0 THEN ( counti top. top i. )top102123013425count325140102123013425counttop1拓?fù)渑判蛩惴ǎ?top -1. /棧頂指針top FOR i = 0 TO n-1 DO/入度為0的頂點入棧IF counti = 0 THEN ( counti top. top i. )325140TOrder2拓?fù)渑判?FOR i = 1 TO n DO IF top = - 1 THEN / 若循環(huán)體尚未被執(zhí)行n次，棧頂指針已為-1 (PRINT “有回路! ”.

13、 RETURN. ) /說明有回路，終止程序 ELSE ( j top. top counttop . /* 彈出棧頂j */ PRINT ( j ) . p adjacent( Headj ) . / 掃描j的邊鏈表 WHILE p DO ( k VerAdj(p) . countk countk-1. / 頂點k的入度減1 IF countk = 0 THEN /若入度為0，則k入棧 (countk top. top k.) p link (p). ) ) 刪除邊，更改相關(guān)頂點的入度；若度為0，則壓入棧中 024315242353551 1013013425counttop32540ppp

14、 j top. top counttop . PRINT ( j ) . p adjacent( Headj ) . WHILE p DO /* 掃描j的邊鏈表 */ (k VerAdj(p) . /*k的入度減1，若入度為0，則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) p link (p). )原數(shù)組：-1,0,2,2,1,3top=1；彈棧之后，top=0； 32501 1 12013425counttopj top. top counttop . /* 彈出堆棧頂點j */PRINT ( j ) .p

15、adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1，若入度為0，則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). ) 1 1 2013425counttop325j top. top counttop . /* 彈出堆棧頂點j */PRINT ( j ) .p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1，若入度為0，則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). )1 1013425counttop35j top. top counttop . /* 彈出堆棧頂點j */PRINT ( j ) .p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1，若入度為0，則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top.