【正文】 { if (i+j=St_len) { for (k=i+j。 k=St_len。 k++) /* 將i+j開始往后的所有字符前移j個位置 */ St[kj]=St[k]。 St_len=St_lenj。 /* 修改St的長度 */ St[St_len]= “\0”。 /* 安放新的串結(jié)束符 */}elseprintf (“參數(shù)不合理，無法進(jìn)行刪除！”)。 }6．在算法412的最后，為了釋放被刪結(jié)點(diǎn)使用的存儲空間，先做了操作： ptrNext = NULL。 把由指針ptr指向的最后一個要釋放空間的結(jié)點(diǎn)的Next域設(shè)置為NULL，然后通過while循環(huán)完成釋放。其實，由于知道要釋放空間的結(jié)點(diǎn)共有m個，因此可以取消這一操作，改用for循環(huán)通過m來控制釋放空間的結(jié)點(diǎn)個數(shù)。請試著按照這一思路改寫那一小段算法。 答：改寫一小段算法如下。for (j=1。 j=m。 j++){ ptr=rtr。 rtr=rtrNext。 free(ptr)。} 7．編寫一個算法，功能是復(fù)制一個鏈串。 答：復(fù)制一個完整的鏈串，是一件比較容易的事情。其算法起名為Copy_Lt()，參數(shù)為Lt1。具體編寫如下。Copy_Lt(Lt1){ptr=Lt1_h。rtr=malloc(size)。rtrData=ptrData。Lt2_h=rtr。ptr=ptrNext。while (ptr != NULL){ qtr=malloc(size)。 qtrData=ptrData。 rtrNext=qtr。 ptr=ptrNext。}rtrNext=NULL。return(Lt2_h)。} 算法是通過while循環(huán)，不斷修改指針ptr，以便指向鏈串Lt1的各個結(jié)點(diǎn)；指針rtr總是指向當(dāng)前已形成的新鏈串Lt2的最后一個結(jié)點(diǎn)；用指針qtr指向剛申請到的新存儲結(jié)點(diǎn)，并把它鏈入到rtr所指結(jié)點(diǎn)的后面。 8．已知兩個mⅹn的矩陣A和B。編寫一個算法，求C=A+B。即C也是一個mⅹn的矩陣，其元素滿足條件：cij = aij + bij（1≤i≤m，1≤j≤n） 答：算法名為Add_Mt()，參數(shù)為A，B，C。Add_Mt(A, B, C){ for (i=1。 i=m。 i++) for (j=1。 j=n。 j++) C[i][j] = A[i][j] + B[i][j]。}第5章習(xí)題解答（此處樹的高度不計算根節(jié)點(diǎn)）一、填空1．結(jié)點(diǎn)數(shù)為7的二叉樹的高度最矮是 2 ，最高是 6 。 2．給定二叉樹的結(jié)點(diǎn)數(shù)，要使樹高為最大，那么該樹應(yīng)該是 單枝 形狀。3．給定二叉樹的結(jié)點(diǎn)數(shù)，要使樹高為最矮，那么該樹應(yīng)該是 完全二叉樹 形狀。 4．如果一棵滿二叉樹的深度為6，那么它共有 127 個結(jié)點(diǎn)，有 64 個葉結(jié)點(diǎn)。 5．有15個結(jié)點(diǎn)的二叉樹，最少有 1 個葉結(jié)點(diǎn)，最多有 8 個葉結(jié)點(diǎn)。 6．由n個帶權(quán)值的葉結(jié)點(diǎn)生成的哈夫曼樹，最終共有 2n1個結(jié)點(diǎn)。 7．將一棵完全二叉樹按層次進(jìn)行編號。那么，對編號為i的結(jié)點(diǎn)，如果有左孩子，則左孩子的編號應(yīng)該是 2i ；如果有右孩子，則右孩子的編號應(yīng)該是 2i+1 。 8．若二叉樹共有n個結(jié)點(diǎn)，采用二叉鏈表存儲結(jié)構(gòu)。那么在所有存儲結(jié)點(diǎn)里，一共會有 2n 個指針域，其中有 n+1 個指針域是空的。 9．深度為5的二叉樹，至多有 31 個結(jié)點(diǎn)。 10．在二叉樹中，有一個結(jié)點(diǎn)具有左、右兩個孩子。那么在中序遍歷序列里，它的右孩子一定排在它的 右 邊。二、選擇1．在所給的4棵二叉樹中， C 不是完全二叉樹。 2．把一棵深度為3的左單支二叉樹改造成完全二叉樹時，要增添 D 個空結(jié)點(diǎn)。 A．10 B．8 C．6 D．4 3．設(shè)有一棵5個結(jié)點(diǎn)的二叉樹，其先序遍歷序列為：ABCDE，中序遍歷序列為：BADCE，那么它的后序遍歷序列為 B 。 A．ABDEC B．BDECA C．DECAB D．ABCDE 4．將一棵有50個結(jié)點(diǎn)的完全二叉樹按層編號，那么編號為25的結(jié)點(diǎn)是 B 。 A．無左、右孩子 B．有左孩子，無右孩子 C．有右孩子，無左孩子 D．有左、有孩子 5．深度為6的二叉樹，最多可以有 A 個結(jié)點(diǎn)。 A．63 B．64 C．127 D．128 6．在一棵非空二叉樹的中序遍歷序列里，根結(jié)點(diǎn)的右邊 D 結(jié)點(diǎn)。 A．只有左子樹上的部分 B．只有左子樹上的所有 C．只有右子樹上的部分 D．只有右子樹上的所有 7．在任何一棵二叉樹的各種遍歷序列中，葉結(jié)點(diǎn)的相對次序是 A 。 A．不發(fā)生變化 B．發(fā)生變化 C．不能確定 D．以上都不對 8．權(quán)值為8的四個結(jié)點(diǎn)，所構(gòu)造的哈夫曼樹的帶權(quán)路徑長度是 D 。 A．18 B．28 C．19 D．29 9．一棵二叉樹度2的結(jié)點(diǎn)數(shù)為7，度1的結(jié)點(diǎn)數(shù)為6。那么它的葉結(jié)點(diǎn)數(shù)是 C 。 A．6 B．7 C．8 D．9 10．在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多是 C 個。 A．8 B．15 C．16 D．32 三、問答1．試問滿二叉樹與完全二叉樹之間有何關(guān)系？ 答：由滿二叉樹與完全二叉樹的定義可知，滿二叉樹一定是一棵完全二叉樹，但完全二叉樹卻不一定是一棵滿二叉樹。如果一棵二叉樹不是完全二叉樹，那么它絕對不可能是一棵滿二叉樹。這就是滿二叉樹與完全二叉樹之間的關(guān)系。 2． 請畫出由3個結(jié)點(diǎn)構(gòu)成的所有二叉樹，它們的高度分別是多少？ 答：大小為3的不同的二叉樹共有5種，如下圖所示。其中，4棵樹的高度為2，1棵樹的高度為1。 3．一棵高度為3的滿二叉樹有多少個葉結(jié)點(diǎn)？有多少個度為2的結(jié)點(diǎn)？總共有多少個結(jié)點(diǎn)？ 答：有23=8個葉結(jié)點(diǎn)，有度為2的結(jié)點(diǎn)231=7個，總共有23+11=241=15個結(jié)點(diǎn)。 4．有人說，任何一棵非空滿二叉樹，它的葉結(jié)點(diǎn)數(shù)等于其分支結(jié)點(diǎn)數(shù)加1。這樣的一個結(jié)論正確嗎？請說明理由。（提示：利用性質(zhì)53） 答：在我們介紹的二叉樹性質(zhì)中，只有性質(zhì)53是涉及葉結(jié)點(diǎn)數(shù)與（度為2的）分支結(jié)點(diǎn)數(shù)的關(guān)系的。對于滿二叉樹來說，所有的分支結(jié)點(diǎn)都是度為2的結(jié)點(diǎn)。因此，正好可以直接利用性質(zhì)53得出所需要的結(jié)論。所以，此人說的結(jié)論是完全正確的。 5．有人說，有一棵結(jié)點(diǎn)數(shù)為n1的二叉樹，只包含有一個葉結(jié)點(diǎn)。這可能嗎？如果可能的話，這樣一棵二叉樹應(yīng)該是個什么樣子呢？ 答：這是完全可能的，這種二叉樹是從根結(jié)點(diǎn)開始只有左子樹，或只有右子樹的單支二叉樹，如圖所示。 6．試問，什么樣的二叉樹其先序遍歷序列與中序遍歷序列相同？ 答：先序遍歷序列與中序遍歷序列相同的二叉樹，或是空二叉樹，或是任一結(jié)點(diǎn)都沒有左孩子的非空二叉樹。7．分別寫出如圖532所示二叉樹的先序、中序、后序遍歷序列。圖532 二叉樹示例 答：先序遍歷序列為：ABCDFGHE，中序遍歷序列為：BADGFHCE，后序遍歷序列為：BGHFDECA。四、應(yīng)用 1．對一個二叉樹進(jìn)行順序存儲，各結(jié)點(diǎn)的編號及數(shù)據(jù)如表所示：編號i1234571011數(shù)據(jù)xABCDEFGH 試畫出對應(yīng)的二叉樹，并給出先序、中序、后序遍歷該二叉樹后，所得到的各種結(jié)點(diǎn)序列。 答：對應(yīng)的二叉樹如圖所示。其先序遍歷序列是：ABDEGHCF；中序遍歷序列是：DBGEHACF；后許遍歷序列是：DGHEBFCA。 2．已知中序遍歷序列為：ABCEFGHD，后序遍歷序列為：ABFHGEDC。試畫出這棵二叉樹。 答：這棵二叉樹如應(yīng)用題2答案圖所示。 3．已知前序遍歷序列為：ABCDEF，中序遍歷序列為：CBAEDF。試畫出這棵二叉樹。 答：這棵二叉樹如應(yīng)用題3答案圖所示。 4．若一棵二叉樹的左、右子樹均有3個結(jié)點(diǎn)，其左子樹的先序遍歷序列與中序遍歷序列相同，右子樹的中序遍歷序列與后序遍歷序列相同。請畫出這棵二叉樹。 答：這棵二叉樹如應(yīng)用題4答案圖所示。 5．理解算法510。在圖525(b)的基礎(chǔ)上，進(jìn)行下一次組合。試給出第2次組合后數(shù)組的情形，以及那時二叉樹的樣子。 答：第2次組合后數(shù)組的情形如下圖(a)所示，那時二叉樹的樣子如下圖(b)所示。 6．權(quán)值序列為：124，請用圖示來表達(dá)構(gòu)造一棵哈夫曼樹的全過程。 答：構(gòu)造這棵哈夫曼樹的全過程如下所示。7．一棵有11個結(jié)點(diǎn)的二叉樹的順序存儲情況如表所示，序號3的結(jié)點(diǎn)是根結(jié)點(diǎn)。畫出該二叉樹，并給出它的先序、中序、后序遍歷序列（其中“^”表示空）。序 號1234567891011Lchild6^7^8^5^2^^DataMFAKBLCRDSERchild^^^9^10411^^^ 答：二叉樹如圖所示，先序遍歷序列為：ACBRSEDFMLK，中序遍歷序列為：RBSCEAFDLKM，后序遍歷序列為：RSBECFKLMDA。第6章習(xí)題解答一、填空1．樹中結(jié)點(diǎn)的度，是指結(jié)點(diǎn)擁有 子樹 的個數(shù)。 2．樹中除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)有且只有 一個 前驅(qū)結(jié)點(diǎn)，但可以有 零個或多個 后繼結(jié)點(diǎn)。 3．樹中一個結(jié)點(diǎn)的 直接后繼 ，或一個結(jié)點(diǎn) 子樹的根結(jié)點(diǎn) ，被稱作是該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。 4．樹中一個結(jié)點(diǎn)的子樹中的任何結(jié)點(diǎn)，都被稱作是該結(jié)點(diǎn)的 子孫 結(jié)點(diǎn)。 5．樹中有 同一雙親 的結(jié)點(diǎn)，被互稱為兄弟結(jié)點(diǎn)。 6．所謂結(jié)點(diǎn)的深度，即是指該結(jié)點(diǎn)位于樹的 層次 數(shù)。 7．雙親位于樹中相同層次上的結(jié)點(diǎn)，互稱為 堂兄弟 結(jié)點(diǎn)。 8．在數(shù)據(jù)結(jié)構(gòu)中，把n（n≥0）棵互不相交的樹的集合稱為 森林 。 9．在如圖621所示的樹中，結(jié)點(diǎn)H的祖先是 A、D、G 。 圖621 樹示例 圖622 樹示例 10．在樹中，一個結(jié)點(diǎn)的孩子個數(shù)，稱為該結(jié)點(diǎn)的 度 。 11．一棵樹的形狀如圖622所示。它的根結(jié)點(diǎn)是 A ，葉結(jié)點(diǎn)是 E、G、I、J、K、L、N、O、P、Q、R ，這棵樹的度是 3 ，這棵樹的深度是 4 ，結(jié)點(diǎn)F的孩子結(jié)點(diǎn)是 J、K ，結(jié)點(diǎn)G的父結(jié)點(diǎn)是 C ，結(jié)點(diǎn) M、H、D、A 是結(jié)點(diǎn)R的祖先。二、選擇1．已知一棵單右支的二叉樹，如下左圖所示。把它還原成森林，應(yīng)該是 D 。A． B． C． D． 2．將一棵樹Tr轉(zhuǎn)換成相應(yīng)的二叉樹Bt，那么對Tr的先序遍歷是對Bt的 A 。 A．先序遍歷 B．中序遍歷 C．后序遍歷 D．無法確定 3．將一棵樹Tr轉(zhuǎn)換成相應(yīng)的二叉樹Bt，那么對Tr的后序遍歷是對Bt的 B 。 A．先序遍歷 B．中序遍歷 C．后序遍歷 D．無法確定4．設(shè)森林F中有3棵樹，依次有結(jié)點(diǎn)nnn3個。把該森林轉(zhuǎn)換成對應(yīng)的二叉樹后，該二叉樹的右子樹上的結(jié)點(diǎn)個數(shù)是 D 。A．n1 B．n1+n2 C．n3 D．n2+n3 5．設(shè)有由三棵樹TTT3組成的森林，其結(jié)點(diǎn)個數(shù)分別為nnn3。與該森林相應(yīng)的二叉樹為Bt。則該二叉樹根結(jié)點(diǎn)的左子樹中應(yīng)該有結(jié)點(diǎn) A 個。 A．n11 B．n1 C．n1+1 D．n1+n2 6．現(xiàn)有一棵度為3的樹，它有兩個度為3的結(jié)點(diǎn)，一個度為2的結(jié)點(diǎn)，兩個度為1的結(jié)點(diǎn)。那么其度為0的結(jié)點(diǎn)的個數(shù)應(yīng)該是 C 。 A．5 B．8 C．6 D．9 注意：有n個結(jié)點(diǎn)的樹，樹中所有結(jié)點(diǎn)的度之和為n1。現(xiàn)在這棵樹應(yīng)該滿足條件： n1 = 2*3 + 1*2 + 2*1 = 10這表示該樹共有11個結(jié)點(diǎn)（加上一個根結(jié)點(diǎn)）。在11個結(jié)點(diǎn)里，減去度為1的結(jié)點(diǎn)數(shù)5，剩下的就是度為0的結(jié)點(diǎn)。所以，該樹有葉結(jié)點(diǎn)6個。 7．一棵有n個結(jié)點(diǎn)的樹，在把它轉(zhuǎn)換成對應(yīng)的二叉樹之后，該二叉樹根結(jié)點(diǎn)的左子樹上共有 B 個結(jié)點(diǎn)。 A．n2 B．n1 C．n+1 D．n+2 8．一棵有n個結(jié)點(diǎn)的樹，在把它轉(zhuǎn)換成對應(yīng)的二叉樹之后，該二叉樹根結(jié)點(diǎn)的右子樹上共有 A 個結(jié)點(diǎn)。 A．0 B．n C．n+1 D．n+2 9．下列說法中，正確的是 A 。 A．樹的先序遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同 B．樹的先序遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同 C．樹的后序遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同 D．樹的后序遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同三、問答1． 如圖623所示的兩棵樹是一樣的嗎？為什么？答：從圖623(a)知，該樹的根結(jié)點(diǎn)為A，下面有兩棵子樹，其中的一棵子樹是最小樹，只有根結(jié)點(diǎn)為B；另一棵子樹的根結(jié)點(diǎn)為C，下面又有一棵最小子樹，它的根結(jié)點(diǎn)為D。從圖623(b)知，該樹的根結(jié)點(diǎn)也是A，它的下面也有兩棵子樹，這兩棵子樹的構(gòu)成也與圖623(a)里的相同。因此如果把樹的子樹視為是無序的，那么該圖所展示的兩棵樹是一樣的，否則是不一樣的。圖623 樹示例2．二叉樹與樹有什么不同？ 答：二