【正文】 preright=ptriht。 Pbt=pb。//B表移至下一結(jié)點(diǎn) //以下是將pbt插入A表的相應(yīng)列鏈表中 j=pbtcol。pre=pt。amp。pt=ptdown} predown=pbt。 //以下是將pbt插入A表相應(yīng)行鏈表中 i=pbtright。pre=pt。amp。pt=ptright。 ptbright=pt。 if(v !=0) {padata+=pbdata。 將pb從行鏈表中刪除；pb=pbright。然后 pa=paright。 } (1) head((p,h,w))=p(2) tail((b,k,p,h))=(k,p,h)(3) head(((a,b),(c,d)))=(a,b)(4) tail(((a,b),(c,d)))=((c,d))(5) head(tail(((a,b),(c,d)))=(c,d)(6) tail(head(((a,b),(c,d))))=(b) (1) (2) (1) 第6章 樹(shù)和二叉樹(shù)（參考答案）(1)根結(jié)點(diǎn)a 三個(gè)結(jié)點(diǎn)的樹(shù)的形態(tài)： 三個(gè)結(jié)點(diǎn)的二叉樹(shù)的形態(tài)： （2） （3） （1） （1） （2） （4） （5）6．3 設(shè)樹(shù)的結(jié)點(diǎn)數(shù)是n，則n=n0+n1+n2+……+nm+ (1)設(shè)樹(shù)的分支數(shù)為B，有n=B+1n=1n1+2n2+……+mnm+1 (2)由（1）和（2）有：n0=n2+2n3+……+(m1)nm+1(1) ki1 (i為層數(shù))(2) (n2)/k+1(3) (n1)*k+i+1(4) (n1)%k !=0。 // 局部變量，分別表示二叉樹(shù)左、右子樹(shù)的高度 if (bt==null) return(0)。 br=height(btrchild)。 // 左右子樹(shù)高度的大者加1（根） } }// 算法結(jié)束 void preorder(cbt[],int n,int i)。本算法以非遞歸形式前序遍歷該二叉樹(shù) { int i=1,s[],top=0。exit（0）；}while (i=n ||top0) { while(i=n) {visit(cbt[i])。 //若右子樹(shù)非空，其編號(hào)進(jìn)棧 i=2*i。 // 退棧，先序訪問(wèn)右子樹(shù) } // END OF while (i=n ||top0) }// 算法結(jié)束 //以下是非完全二叉樹(shù)順序存儲(chǔ)時(shí)的遞歸遍歷算法，“虛結(jié)點(diǎn)”用‘*’表示 void preorder(bt[],int n,int i)。i是數(shù) // 組下標(biāo)，初始調(diào)用時(shí)為1。amp。 preorder(bt,n,2*i)。 }// 算法結(jié)束 int equal(bitree T1,bitree T2)。amp。 // 同為空二叉樹(shù) else if (T1==null || T2==null) return(0)。// 根結(jié)點(diǎn)值不等 else return(equal(T1lchild,T2lchild)amp。equal(T1rchild,T2rchild)) //判左右子樹(shù)等價(jià)}// 算法結(jié)束 6．11void levelorder (bitree ht)。 {處始化隊(duì)列，隊(duì)列元素為二叉樹(shù)結(jié)點(diǎn)的指針} enqueue(q,ht)。 visit(p)。 //若左子女非空，則左子女入隊(duì)列 if (prchild!=null) enqueue (q,prchild)； //若右子女非空，則右子女入隊(duì)列 }}} // 算法結(jié)束 6．12void preorder (bitree *t)。 // s是指針數(shù)組，數(shù)組中元素為二叉樹(shù)節(jié)點(diǎn)的指針top=0。 s[++top]=t。 t=trchild。 (中序非遞歸遍歷){bitree *s[n+1]。while ((t!=null || top!=0){ while (t!=null) { s[++top]=t。 visit(*t)。 }} // 算法結(jié)束 void postorder (bitree *t)。 tag:0..1 } stack。top=0。 s[top].tag=0。 } while (top amp。 s[top].tag==1) { printf(s[top].tdata:3)。 t=s[top].trchild 。 if (*t!=null) { if ((*t)data==x) // 根結(jié)點(diǎn)數(shù)據(jù)域?yàn)閤 {p=*t。 return(p)。(*t)lchild),x)。(*t)rchild),x)。 } } else return(null)。 int tag。 snode s[]。 while (t amp。 tdata !=x || top){ while (t amp。 tdata !=x) // 沿左分支向下 { s[++top].p=t。 t=tlchild。i=top。// 輸出，設(shè)元素為字符 return(1)。amp。//退出右子樹(shù)已訪問(wèn)的結(jié)點(diǎn) if (top0) // 置訪問(wèn)標(biāo)志1，訪問(wèn)右子樹(shù) {s[top].tag=1。 t=trchild。 // 沒(méi)有值為x的結(jié)點(diǎn) } // 算法結(jié)束 中序序列BDCEAFHGA后序序列DECBHGFAFBGCDHE前序序列 ABCDEFGHA 后序線索樹(shù)： BCDEFHE null只有空指針處才能加線索。 // 左標(biāo)記為0時(shí)，p的左子女plchild為p的后繼 .} // 算法結(jié)束 bitree *search（b：tree *p） //在后序線索二叉樹(shù)中查找給定結(jié)點(diǎn)的后序前驅(qū)的算法{ if(prtag==0) return(prchild)。 //p的左標(biāo)記為0，左子女plchild是后序前驅(qū), 否則，線索plchild指向p的后序前驅(qū) }AGBLHCMIDNPJEOQKFR前序序列：ABCDEFGHIJKLMPQRNO后序序列：BDEFCAIJKHGQRPMNOL 7,19,2,6,32,3,21,10其對(duì)應(yīng)字母分別為a,b,c,e,f,g,h。7．2（1）任一頂點(diǎn)間均有通路，故是強(qiáng)連通；（2）簡(jiǎn)單路徑 V4 V3 V1 V2。 vtxptr i,j。在遍歷中若發(fā)現(xiàn)頂點(diǎn)j，則說(shuō)明頂點(diǎn)i和j間有路徑。 //置訪問(wèn)標(biāo)記 if (y= =j){ found=1。}//有通路，退出else { p=g[x].firstarc。 if （!visited[k]）dfs(k)。//下一鄰接點(diǎn) }}③ void connect_DFS (adjlisttp g) //基于圖的深度優(yōu)先遍歷策略，本算法判斷一鄰接表為存儲(chǔ)結(jié)構(gòu)的圖g種，是否存在頂點(diǎn)i//到頂點(diǎn)j的路徑。found=0。i,amp。 dfs (i)。void bfs(vtxptr x)//{ initqueue(q)。 while (!empty(q))。 if (y= =j) 　{ found=1。}//有通路，退出 else {p=g[x].firstarc。 if (! Visted[k]) enqueue(q,k)。假定該有向圖以鄰接表存儲(chǔ)，各頂點(diǎn)的鄰接點(diǎn)按增序排列DFS序列：V1,V3,V6,V7,V4,V2,V5,V8BFS序列：V1,V3,V4,V6,V7,V2,V5,V8DFS森林 BFS森林V1 V2 V1 V2 V3 V4 V3 V4 V5 V5 V6 V7V6 V8 V8V77．6簡(jiǎn)單回路指起點(diǎn)和終點(diǎn)相同的簡(jiǎn)單路徑。Adjlisttp g 。Int found =0。 p=g[x].firstarc。 if(w= =k) { found=1。}//有簡(jiǎn)單回路，退出 if (!visited[k] ) dfs(w )。}//while(p!=null)}// dfs7．7 （1）PRIM算法的最小生成樹(shù) bbbeb 2 2 2 2 2 2addadaa 1ccbebgeeb 2 2 2 2 2 2dada 2 2 2da 1 1 1 1 1 1 1hacfc 1hfc 1 1 1 1（2）KRUSKAL算法的最小生成樹(shù)dbggee 1 2 2cda 2 1 1 1 1 1hac hf 1 1 1（權(quán)值相同的邊選取無(wú)順序）7．8所選頂點(diǎn)已選定點(diǎn)的集合尚未被選頂點(diǎn)的集合DIST[2] [3] [4] [5] [6]初態(tài){1}{2，3，4，5，6}20 15 ∞ ∞ ∞3{1，3}{2，4，5，6}19 ∞ ∞ 252{1，3，2}{4，5，6} ∞ 29 256{1，3，2，6}{4，5} 29 294{1，3，2，6，4}{5} 295{1，3，2，6，4，5}{}注：選定點(diǎn)4和5時(shí)無(wú)優(yōu)先順序，二者最短路徑均為297．9 0 8 ∞ 1 2 0 0:11A0= 3 0 ∞ path0 = 1 2 0 1:12 5 2 0 1 2 3 ∞:1到3沒(méi)有直接通路 0 8 ∞ path1同path0,加入頂點(diǎn)1后無(wú)變化A1= 3 0 ∞ 5 2 0 0 8 ∞A2= 3 0 ∞ path2同path1 5 2 ∞ 0 8 ∞A3= 3 0 ∞ 本題不好，終態(tài)和初態(tài)無(wú)變化V4V6V3 5 2 0V27．10V1V5V6V6V3V4V2V3V4V6V4V6V5V3V1V6V1V2V6V4V2V3V3V2V4V4V3共七種用TOPOSORT算法求得第七種，即V5,V6,V1,V2,V3,V4.用鄰接表存儲(chǔ)結(jié)構(gòu)，鄰接點(diǎn)逆序即編號(hào)大的排在前面。7．11 void toposort_dfs （graph g；vtptr v） //從頂點(diǎn)v開(kāi)始，利用深度優(yōu)先遍歷對(duì)圖g進(jìn)行拓?fù)渑判?。若出棧元素個(gè)數(shù)等于頂點(diǎn)數(shù)，則拓?fù)渑判虺晒?，輸出的是逆拓?fù)渑判蛐蛄?。top=0。//初始化；top為棧頂指針，num記出棧元素?cái)?shù) s[++top]=v。//求頂點(diǎn)v的第一鄰接點(diǎn) while (w！=0) // w!=0的含義是w存在 { if ( !visited[w]) s[++top]=w。//求下一個(gè)鄰接點(diǎn) } if (top!=0) {v=s[top]。 printf(v)。if (numn) printf(“ 從”,”v”,”頂點(diǎn)開(kāi)始拓?fù)渑判虿荒茼樌瓿?”)； else printf(“拓?fù)渑判虺晒Γ敵龅氖且粋€(gè)逆拓?fù)湫蛄?