【正文】 ild。 Trchild = temp。 } ChangeLR(Tlchild)。 ChangeLR(Trchild)。}（4）設(shè)計(jì)二叉樹的雙序遍歷算法（雙序遍歷是指對于二叉樹的每一個(gè)結(jié)點(diǎn)來說，先訪問這個(gè)結(jié)點(diǎn)，再按雙序遍歷它的左子樹，然后再一次訪問這個(gè)結(jié)點(diǎn)，接下來按雙序遍歷它的右子樹）。void DoubleTraverse(BiTree T){ if(T == NULL) return。 else if(Tlchild==NULLamp。amp。Trchild==NULL) coutTdata。 else { coutTdata。 DoubleTraverse(Tlchild)。 coutTdata。 DoubleTraverse(Trchild)。 }}（5）計(jì)算二叉樹最大的寬度（二叉樹的最大寬度是指二叉樹所有層中結(jié)點(diǎn)個(gè)數(shù)的最大值）。[題目分析] 求二叉樹高度的算法見上題。求最大寬度可采用層次遍歷的方法，記下各層結(jié)點(diǎn)數(shù)，每層遍歷完畢，若結(jié)點(diǎn)數(shù)大于原先最大寬度，則修改最大寬度。int Width(BiTree bt)//求二叉樹bt的最大寬度{if (bt==null) return (0)。 //空二叉樹寬度為0else {BiTree Q[]。//Q是隊(duì)列，元素為二叉樹結(jié)點(diǎn)指針，容量足夠大 front=1。rear=1。last=1。//front隊(duì)頭指針,rear隊(duì)尾指針,last同層最右結(jié)點(diǎn)在隊(duì)列中的位置 temp=0。 maxw=0。 //temp記局部寬度, maxw記最大寬度 Q[rear]=bt。 //根結(jié)點(diǎn)入隊(duì)列 while(front=last) {p=Q[front++]。 temp++。 //同層元素?cái)?shù)加1 if (plchild!=null) Q[++rear]=plchild。 //左子女入隊(duì)if (prchild!=null) Q[++rear]=prchild。 //右子女入隊(duì) if (frontlast) //一層結(jié)束， {last=rear。if(tempmaxw) maxw=temp。//last指向下層最右元素, 更新當(dāng)前最大寬度 temp=0。 }//if }//while return (maxw)。}//結(jié)束width（6）用按層次順序遍歷二叉樹的方法，統(tǒng)計(jì)樹中具有度為1的結(jié)點(diǎn)數(shù)目。int Level(BiTree bt) //層次遍歷二叉樹，并統(tǒng)計(jì)度為1的結(jié)點(diǎn)的個(gè)數(shù){int num=0。 //num統(tǒng)計(jì)度為1的結(jié)點(diǎn)的個(gè)數(shù) if(bt){QueueInit(Q)。 QueueIn(Q,bt)；//Q是以二叉樹結(jié)點(diǎn)指針為元素的隊(duì)列 while(!QueueEmpty(Q)){p=QueueOut(Q)。 printf(pdata)。 //出隊(duì),訪問結(jié)點(diǎn)if(plchild amp。amp。 !prchild ||!plchild amp。amp。 prchild)num++。//度為1的結(jié)點(diǎn)if(plchild) QueueIn(Q,plchild)。 //非空左子女入隊(duì)if(prchild) QueueIn(Q,prchild)。 //非空右子女入隊(duì)} }//if(bt) return(num)。 }//返回度為1的結(jié)點(diǎn)的個(gè)數(shù) （7）求任意二叉樹中第一條最長的路徑長度，并輸出此路徑上各結(jié)點(diǎn)的值。[題目分析]因?yàn)楹笮虮闅v棧中保留當(dāng)前結(jié)點(diǎn)的祖先的信息，用一變量保存棧的最高棧頂指針，每當(dāng)退棧時(shí)，棧頂指針高于保存最高棧頂指針的值時(shí)，則將該棧倒入輔助棧中，輔助棧始終保存最長路徑長度上的結(jié)點(diǎn)，直至后序遍歷完畢，則輔助棧中內(nèi)容即為所求。void LongestPath(BiTree bt)//求二叉樹中的第一條最長路徑長度{BiTree p=bt,l[],s[]。 //l, s是棧，元素是二叉樹結(jié)點(diǎn)指針，l中保留當(dāng)前最長路徑中的結(jié)點(diǎn) int i，top=0,tag[],longest=0。 while(p || top0) { while(p) {s[++top]=p；tag[top]=0。 p=pLc。} //沿左分枝向下 if(tag[top]==1) //當(dāng)前結(jié)點(diǎn)的右分枝已遍歷 {if(!s[top]Lc amp。amp。 !s[top]Rc) //只有到葉子結(jié)點(diǎn)時(shí)，才查看路徑長度if(toplongest) {for(i=1。i=top。i++) l[i]=s[i]。 longest=top。 top。}//保留當(dāng)前最長路徑到l棧，記住最高棧頂指針，退棧} else if(top0) {tag[top]=1。 p=s[top].Rc。} //沿右子分枝向下 }//while(p!=null||top0)}//結(jié)束LongestPath（8）輸出二叉樹中從每個(gè)葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。[題目分析]采用先序遍歷的遞歸方法，當(dāng)找到葉子結(jié)點(diǎn)*b時(shí)，由于*b葉子結(jié)點(diǎn)尚未添加到path中，因此在輸出路徑時(shí)還需輸出bdata值。對應(yīng)的遞歸算法如下：void AllPath(BTNode *b,ElemType path[],int pathlen){ int i。 if (b!=NULL) { if (blchild==NULL amp。amp。 brchild==NULL) //*b為葉子結(jié)點(diǎn) { cout bdata 到根結(jié)點(diǎn)路徑: bdata。 for (i=pathlen1。i=0。i) cout endl。 } else { path[pathlen]=bdata。 //將當(dāng)前結(jié)點(diǎn)放入路徑中 pathlen++。 //路徑長度增1 AllPath(blchild,path,pathlen)。 //遞歸掃描左子樹 AllPath(brchild,path,pathlen)。 //遞歸掃描右子樹 pathlen。 //恢復(fù)環(huán)境 } }}第6章 圖2．應(yīng)用題（1），請給出：① 每個(gè)頂點(diǎn)的入度和出度； ② 鄰接矩陣；③ 鄰接表；④ 逆鄰接表。 有向圖 （2），請給出：① 鄰接矩陣； ② 鄰接表；③ 最小生成樹 無向網(wǎng) a→b4→c3b→a4→c5→d5→e9^c→a3→b5→d5→h5^d→b5→c5→e7→f6→g5→h4^e→b9→d7→f3^f→d6→e3→g2^g→d5→f2→h6^h→c5→d4→g6^（3）。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。 鄰接矩陣（4），試用迪杰斯特拉算法求出從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑。 有向網(wǎng)D終點(diǎn)i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)c2(a,c)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)e∞10(a,c,e)10(a,c,e)f∞6(a,c,f)g∞∞16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S終點(diǎn)集{a,c}{a,c,f}{a,c,f,e}{a,c,f,e,d}{a,c,f,e,d,g}{a,c,f,e,d,g,b} （5）：① 求這個(gè)工程最早可能在什么時(shí)間結(jié)束； ② 求每個(gè)活動的最早開始時(shí)間和最遲開始時(shí)間； AOE網(wǎng)③ 確定哪些活動是關(guān)鍵活動 【解答】按拓?fù)溆行虻捻樞蛴?jì)算各個(gè)頂點(diǎn)的最早可能開始時(shí)間Ve和最遲允許開始時(shí)間Vl。然后再計(jì)算各個(gè)活動的最早可能開始時(shí)間e和最遲允許開始時(shí)間l，根據(jù)l e = 0? 來確定關(guān)鍵活動，從而確定關(guān)鍵路徑。 1 182。 2 184。 3 4 185。 5 186。 6 187。 Ve 0 19 15 29 38 43 Vl 0 19 15 37 38 431, 21, 33, 22, 42, 53, 54, 65, 6 e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38le 17 0 0 8 0 12 8 0 此工程最早完成時(shí)間為43。關(guān)鍵路徑為1, 33, 22, 55, 6 3．算法設(shè)計(jì)題（1）分別以鄰接矩陣和鄰接表作為存儲結(jié)構(gòu)，實(shí)現(xiàn)以下圖的基本操作：① 增添一個(gè)新頂點(diǎn)v，InsertVex(G, v)；② 刪除頂點(diǎn)v及其相關(guān)的邊，DeleteVex(G, v)。③ 增加一條邊v，w，InsertArc(G, v, w)。④ 刪除一條邊v，w，DeleteArc(G, v, w)。//本題中的圖G均為有向無權(quán)圖,其余情況容易由此寫出Status Insert_Vex(MGraph amp。G, char v)//在鄰接矩陣表示的圖G上插入頂點(diǎn)v{if(+1)MAX_VERTEX_NUM return INFEASIBLE。[++]=v。return OK。}//Insert_VexStatus Insert_Arc(MGraph amp。G,char v,char w)//在鄰接矩陣表示的圖G上插入邊(v,w){if((i=LocateVex(G,v))0) return ERROR。if((j=LocateVex(G,w))0) return ERROR。if(i==j) return ERROR。if(![j].adj){[j].adj=1。++。}return OK。}//Insert_ArcStatus Delete_Vex(MGraph amp。G,char v)//在鄰接矩陣表示的圖G上刪除頂點(diǎn)v{n=。if((m=LocateVex(G,v))0) return ERROR。[m][n]。 //將待刪除頂點(diǎn)交換到最后一個(gè)頂點(diǎn)for(i=0。in。i++){[m]=[n]。[m]=[n]。 //將邊的關(guān)系隨之交換}[m][m].adj=0。return OK。}//Delete_Vex分析:如果不把待刪除頂點(diǎn)交換到最后一個(gè)頂點(diǎn)的話,算法將會比較復(fù)雜,而伴隨著大量元素的移動,時(shí)間復(fù)雜度也會大大增加.Status Delete_Arc(MGraph amp。G,char v,char w)//在鄰接矩陣表示的圖G上刪除邊(v,w){if((i=LocateVex(G,v))0) return ERROR。if((j=LocateVex(G,w))0) return ERROR。if([j].adj){[j].adj=0。}return OK。}//Delete_Arc//為節(jié)省篇幅,.Status Insert_Arc(ALGraph amp。G,char v,char w)//在鄰接表表示的圖G上插入邊(v,w){if((i=LocateVex(G,v))0) return ERROR。if((j=LocateVex(G,w))0) return ERROR。p=(ArcNode*)malloc(sizeof(ArcNode))。padjvex=j。pnextarc=NULL。if(!) =p。else{for(q=。qq