【正文】 R，如果無(wú) L，則完全相同, 如果無(wú) LR，…。b) L D R 與L R D 的相同點(diǎn)：L D，如果無(wú) R，則完全相同。c) D L R 與L R D 的相同點(diǎn)：D，如果無(wú) L R，則完全相同。（如果去D，則為空樹(shù)）7． n個(gè)結(jié)點(diǎn)的K叉樹(shù)，若用具有k個(gè)child域的等長(zhǎng)鏈結(jié)點(diǎn)存儲(chǔ)樹(shù)的一個(gè)結(jié)點(diǎn)，則空的Child域有多少個(gè)？[提示]：參考 8．畫(huà)出與下列已知序列對(duì)應(yīng)的樹(shù)Ｔ：樹(shù)的先根次序訪問(wèn)序列為GFKDAIEBCHJ；樹(shù)的后根次序訪問(wèn)序列為DIAEKFCJHBG。[提示]：（1）先畫(huà)出對(duì)應(yīng)的二叉樹(shù)（2）樹(shù)的后根序列與對(duì)應(yīng)二叉樹(shù)的中序序列相同9．假設(shè)用于通訊的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為：，，，，（1）請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼，（2）求平均編碼長(zhǎng)度。10．已知二叉樹(shù)采用二叉鏈表存放,要求返回二叉樹(shù)T的后序序列中的第一個(gè)結(jié)點(diǎn)的指針,是否可不用遞歸且不用棧來(lái)完成?請(qǐng)簡(jiǎn)述原因.[提示]：無(wú)右子的“左下端”11. 畫(huà)出和下列樹(shù)對(duì)應(yīng)的二叉樹(shù)：12．已知二叉樹(shù)按照二叉鏈表方式存儲(chǔ)，編寫算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。13．編寫遞歸算法：對(duì)于二叉樹(shù)中每一個(gè)元素值為x的結(jié)點(diǎn)，刪去以它為根的子樹(shù)，并釋放相應(yīng)的空間。[提示]：[方法1]：（1）按先序查找；（2）超前查看子結(jié)點(diǎn)（3）按后序釋放；void DelSubTree(BiTree *bt, DataType x){ if ( *bt != NULL amp。amp。 (*bt) data==x ) { FreeTree(*bt)。*bt =NULL。}else DelTree( *bt, x)void DelTree(BiTree bt, DataType x){ if ( bt ) { if (btLChild amp。amp。 btLChilddata==x){ FreeTree(btLChild)。 btLChild=NULL。} if (btRChild amp。amp。 btRChilddata==x){ FreeTree(btRChild)。 btRChild=NULL。}DelTree(btLChild, x)。DelTree(btRChild, x)。}}[方法2]：（1）先序查找；（2）直接查看當(dāng)前根結(jié)點(diǎn)（3）用指針參數(shù)；[方法3]：（1）先序查找；（2）直接查看當(dāng)前根結(jié)點(diǎn)（3）通過(guò)函數(shù)值，返回刪除后結(jié)果；（參示例程序）14．分別寫函數(shù)完成：在先序線索二叉樹(shù)T中，查找給定結(jié)點(diǎn)*p在先序序列中的后繼。在后序線索二叉樹(shù)T中，查找給定結(jié)點(diǎn)*p在后序序列中的前驅(qū)。[提示]：（1）先查看線索，無(wú)線索時(shí)用下面規(guī)律：（2）結(jié)點(diǎn)*p在先序序列中的后繼為其左子或右子；（3）結(jié)點(diǎn)*p在后序序列中的前驅(qū)也是其左子或右子。15．分別寫出算法，實(shí)現(xiàn)在中序線索二叉樹(shù)中查找給定結(jié)點(diǎn)*p在中序序列中的前驅(qū)與后繼。（參例題）16．編寫算法，對(duì)一棵以孩子兄弟鏈表表示的樹(shù)統(tǒng)計(jì)其葉子的個(gè)數(shù)。[提示]：（1）可將孩子兄弟鏈表劃分為根、首子樹(shù)、兄弟樹(shù)，遞歸處理。（2）可利用返回值，或全局變量。17．對(duì)以孩子兄弟鏈表表示的樹(shù)編寫計(jì)算樹(shù)的深度的算法。18．已知二叉樹(shù)按照二叉鏈表方式存儲(chǔ)，利用棧的基本操作寫出后序遍歷非遞歸的算法。 （參課本）19．設(shè)二叉樹(shù)按二叉鏈表存放，寫算法判別一棵二叉樹(shù)是否是一棵正則二叉樹(shù)。正則二叉樹(shù)是指：在二叉樹(shù)中不存在子樹(shù)個(gè)數(shù)為1的結(jié)點(diǎn)。[提示]：可利用任何遞歸、非遞歸遍歷算法。20．計(jì)算二叉樹(shù)最大寬度的算法。二叉樹(shù)的最大寬度是指：二叉樹(shù)所有層中結(jié)點(diǎn)個(gè)數(shù)的最大值。21．已知二叉樹(shù)按照二叉鏈表方式存儲(chǔ)，利用棧的基本操作寫出先序遍歷非遞歸形式的算法。22. 證明：給定一棵二叉樹(shù)的前序序列與中序序列，可唯一確定這棵二叉樹(shù)；　　給定一棵二叉樹(shù)的后序序列與中序序列，可唯一確定這棵二叉樹(shù)；23. 二叉樹(shù)按照二叉鏈表方式存儲(chǔ)，編寫算法將二叉樹(shù)左右子樹(shù)進(jìn)行交換。實(shí)習(xí)題1. [問(wèn)題描述] 建立一棵用二叉鏈表方式存儲(chǔ)的二叉樹(shù)，并對(duì)其進(jìn)行遍歷（先序、中序和后序），打印輸出遍歷結(jié)果。[基本要求] 從鍵盤接受輸入先序序列，以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹(shù)（以先序來(lái)建立）并對(duì)其進(jìn)行遍歷（先序、中序、后序），然后將遍歷結(jié)果打印輸出。要求采用遞歸和非遞歸兩種方法實(shí)現(xiàn)。[測(cè)試數(shù)據(jù)] ABCффDEфGффFффф（其中ф表示空格字符） 輸出結(jié)果為： 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA2．已知二叉樹(shù)按照二叉鏈表方式存儲(chǔ)，編寫算法，要求實(shí)現(xiàn)二叉樹(shù)的豎向顯示（豎向顯示就是二叉樹(shù)的按層顯示）。[提示]：（1），實(shí)現(xiàn)逐層遍歷（2）隊(duì)中保存每個(gè)結(jié)點(diǎn)的打印位置，其左、右子的距離3．如題1要求建立好二叉樹(shù)，按凹入表形式打印二叉樹(shù)結(jié)構(gòu)。CF EAD BFA B C D E 4．按凹入表形式打印樹(shù)形結(jié)構(gòu)。[提示]：，用先根遍歷。ABDCGFEAB E FC GD A B C D E F G 第六章答案6． 1分別畫(huà)出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)?！窘獯稹烤哂?個(gè)結(jié)點(diǎn)的樹(shù) 具有3個(gè)結(jié)點(diǎn)的二叉樹(shù) ，n2個(gè)度為2的結(jié)點(diǎn)，……，nk個(gè)度為k的結(jié)點(diǎn)，則該樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)？【解答】設(shè)樹(shù)中結(jié)點(diǎn)總數(shù)為n,則n=n0 + n1 + …… + nk樹(shù)中分支數(shù)目為B,則B=n1 + 2n2 + 3n3 + …… + knk因?yàn)槌Y(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均對(duì)應(yīng)一個(gè)進(jìn)入它的分支，所以有n= B + 1即n0 + n1 + …… + nk = n1 + 2n2 + 3n3 + …… + knk + 1由上式可得葉子結(jié)點(diǎn)數(shù)為：n0 = n2 + 2n3 + …… + (k1)nk + 1，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)至少應(yīng)有多少個(gè)？【解答】n0表示葉子結(jié)點(diǎn)數(shù)，n2表示度為2的結(jié)點(diǎn)數(shù)，則n0 = n2+1 所以n2= n0 –1=49，當(dāng)二叉樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)時(shí)，總結(jié)點(diǎn)數(shù)n=n0+n2=99 試分別找出滿足以下條件的所有二叉樹(shù):(1) 前序序列與中序序列相同。(2) 中序序列與后序序列相同。(3) 前序序列與后序序列相同。【解答】 (1) 前序與中序相同：空樹(shù)或缺左子樹(shù)的單支樹(shù)； (2) 中序與后序相同：空樹(shù)或缺右子樹(shù)的單支樹(shù)； (3) 前序與后序相同：空樹(shù)或只有根結(jié)點(diǎn)的二叉樹(shù)。 假設(shè)通訊的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為：，，，，請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼?！窘獯稹? 構(gòu)造哈夫曼樹(shù)如下：哈夫曼編碼為：I1：11111 I5：1100 I2：11110 I6： 10I3：1110 I7： 01 I4：1101 I8： 00?！窘獯稹浚瑢?shí)現(xiàn)在中序線索二叉樹(shù)T中查找給定結(jié)點(diǎn)*p在中序序列中的前驅(qū)與后繼。在先序線索二叉樹(shù)T中，查找給定結(jié)點(diǎn)*p在先序序列中的后繼。在后序線索二叉樹(shù)T中，查找給定結(jié)點(diǎn)*p在后序序列中的前驅(qū)。（1）找結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)BiTNode *InPre (BiTNode *p)/*在中序線索二叉樹(shù)中查找p的中序前驅(qū)結(jié)點(diǎn)，并用pre指針?lè)祷亟Y(jié)果*/{ if (pLtag= =1) pre = pLChild。 /*直接利用線索*/ else {/*在p的左子樹(shù)中查找“最右下端”結(jié)點(diǎn)*/ for ( q=pLChild。 qRtag= =0。 q=qRChild)。 pre = q。 } return (pre)。 }（2）找結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)BiTNode *InSucc (BiTNode *p)/*在中序線索二叉樹(shù)中查找p的中序后繼結(jié)點(diǎn)，并用succ指針?lè)祷亟Y(jié)果*/{ if (pRtag= =1) succ = pRChild。 /*直接利用線索*/ else {/*在p的右子樹(shù)中查找“最左下端”結(jié)點(diǎn)*/ for ( q=pRChild。 qLtag= =0。 q=qLChild)。 succ= q。 } return (succ)。 }(3) 找結(jié)點(diǎn)的先序后繼結(jié)點(diǎn)BiTNode *PreSucc (BiTNode *p)/*在先序線索二叉樹(shù)中查找p的先序后繼結(jié)點(diǎn)，并用succ指針?lè)祷亟Y(jié)果*/{ if (pLtag= =0) succ = pLChild。 else succ= pRChild。 return (succ)。 }(4) 找結(jié)點(diǎn)的后序前驅(qū)結(jié)點(diǎn)BiTNode *SuccPre (BiTNode *p)/*在后序線索二叉樹(shù)中查找p的后序前驅(qū)結(jié)點(diǎn)，并用pre指針?lè)祷亟Y(jié)果*/{ if (pLtag= =1) pre = pLChild。 else pre= pRChild。 return (pre)。 }，利用棧的基本操作寫出先序遍歷非遞歸形式的算法?！窘獯稹縑oid PreOrder(BiTree root) /*先序遍歷二叉樹(shù)的非遞歸算法*/{ InitStack(amp。S)。 p=root。 while(p!=NULL || !IsEmpty(S) ) { if(p!=NULL) {Visit(pdata)。push(amp。S,p)。p=pLchild。 }else { Pop(amp。S,amp。p)。 p=pRChild。}}}，編寫算法，將二叉樹(shù)左右子樹(shù)進(jìn)行交換?！窘獯稹? 算法(一) Void exchange ( BiTree root ){ p=root。 if ( pLChild != NULL || pRChild != NULL ) { temp = pLChild。pLChild = pRChild。 pRChild = temp。 exchange ( pLChild )。 exchange ( pRChild )。 } } 算法(二) Void exchange ( BiTree root ){ p=root。 if ( pLChild != NULL || pRChild != NULL ) { exchange ( pLChild )。 exchange ( pRChild )。 temp = pLChild。pLChild = pRChild。 pRChild = temp。 } } 第七章補(bǔ)充題參考題實(shí)習(xí)題習(xí)題 已知如圖所示的有向圖，請(qǐng)給出該圖的：156243題1圖（1） 每個(gè)頂點(diǎn)的入度、出度；（2） 鄰接矩陣；（3） 鄰接表；（4） 逆鄰接表；（5） 十字鏈表；（6） 強(qiáng)連通分量。 已知如圖所示的無(wú)向圖，請(qǐng)給出該圖的：（1） 鄰接多重表；（要求每個(gè)邊結(jié)點(diǎn)中第一個(gè)頂點(diǎn)號(hào)小于第二個(gè)頂點(diǎn)號(hào)，且每個(gè)頂點(diǎn)的各鄰接邊的鏈接順序，為它所鄰接到的頂點(diǎn)序號(hào)由小到大的順序。）（2） 從頂點(diǎn)1開(kāi)始，深度優(yōu)先遍歷該圖所得頂點(diǎn)序列和邊的序列；（給出深度優(yōu)先搜索樹(shù)）（3） 從頂點(diǎn)1開(kāi)始，廣度優(yōu)先遍歷該圖所得頂點(diǎn)序列和邊的序列。（給出廣度優(yōu)先搜索樹(shù)）142536題2圖 ，試求：（1） 每個(gè)事件的最早發(fā)生時(shí)間和最晚發(fā)生時(shí)間；（2） 每個(gè)活動(dòng)的最早開(kāi)始時(shí)間和最晚開(kāi)始時(shí)間；（3） 給出關(guān)鍵路徑。021435768944354336614522 用圖 ，試?yán)肈ijkstra算法求頂點(diǎn)1到其余頂點(diǎn)的最短路徑，并給出算法執(zhí)行過(guò)程中各步的狀態(tài)。 用圖654321101521043020152010 編寫算法，由依次輸入的頂點(diǎn)數(shù)目、弧的數(shù)目、各頂點(diǎn)的信息和各條弧的信息建立有向圖的鄰接表。[參例題] 試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：InsertVertex(G,v)。 InsertArc(G, v, w)。 DeleteVertex(G,v)和DeleteArc(G, v, w)。 試對(duì)鄰接表存儲(chǔ)結(jié)構(gòu)重做題6。 試基于圖的深度優(yōu)先搜索策略寫一算法，判別以鄰接表方式存儲(chǔ)的有向圖中，是否存在由頂點(diǎn)vi到頂點(diǎn)vj的路徑（i≠j）。注意：算法中涉及的圖的基