【正文】 （參例題）16．編寫算法，對一棵以孩。[提示]：（1）先查看線索，無線索時用下面規(guī)律：（2）結(jié)點*p在先序序列中的后繼為其左子或右子；（3）結(jié)點*p在后序序列中的前驅(qū)也是其左子或右子。}}[方法2]：（1）先序查找；（2）直接查看當(dāng)前根結(jié)點（3）用指針參數(shù)；[方法3]：（1）先序查找；（2）直接查看當(dāng)前根結(jié)點（3）通過函數(shù)值，返回刪除后結(jié)果；（參示例程序）14．分別寫函數(shù)完成：在先序線索二叉樹T中，查找給定結(jié)點*p在先序序列中的后繼。}DelTree(btLChild, x)。 btRChilddata==x){ FreeTree(btRChild)。} if (btRChild amp。 btLChilddata==x){ FreeTree(btLChild)。}else DelTree( *bt, x)void DelTree(BiTree bt, DataType x){ if ( bt ) { if (btLChild amp。 (*bt) data==x ) { FreeTree(*bt)。[提示]：[方法1]：（1）按先序查找；（2）超前查看子結(jié)點（3）按后序釋放；void DelSubTree(BiTree *bt, DataType x){ if ( *bt != NULL amp。10．已知二叉樹采用二叉鏈表存放,要求返回二叉樹T的后序序列中的第一個結(jié)點的指針,是否可不用遞歸且不用棧來完成?請簡述原因.[提示]：無右子的“左下端”11. 畫出和下列樹對應(yīng)的二叉樹：12．已知二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結(jié)點的數(shù)目。（如果去D，則為空樹）7． n個結(jié)點的K叉樹，若用具有k個child域的等長鏈結(jié)點存儲樹的一個結(jié)點，則空的Child域有多少個？[提示]：參考 8．畫出與下列已知序列對應(yīng)的樹Ｔ：樹的先根次序訪問序列為GFKDAIEBCHJ；樹的后根次序訪問序列為DIAEKFCJHBG。b) L D R 與L R D 的相同點：L D，如果無 R，則完全相同。（2）滿二叉樹或完全二叉樹具有最少的一度結(jié)點（3）可能的最大滿二叉樹是幾層？有多少葉結(jié)點？如何增補？255026可能的最大滿二叉樹是6層有 25 = 32個葉結(jié)點假設(shè)將其中x個變?yōu)?度結(jié)點后，總?cè)~結(jié)點數(shù)目為50則：2x + (32 – x) = 50得：x = 18此時總結(jié)點數(shù)目= ( 26 – 1) + 182[方法2]假設(shè)完全二叉樹的最大非葉結(jié)點編號為m，則最大葉結(jié)點編號為2m+1,(2m+1)m=50m=49總結(jié)點數(shù)目=2m+1=99[方法3]由性質(zhì)3：n0=n2+1即：50=n2+1所以：n2=49令n1=0得：n= n0 + n2=997． 給出滿足下列條件的所有二叉樹：a) 前序和中序相同b) 中序和后序相同c) 前序和后序相同[提示]：去異存同。3．已知一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，……，nk個度為k的結(jié)點，則該樹中有多少個葉子結(jié)點？[提示]：參考 性質(zhì)3∵　n=n0 + n1 + …… + nkB=n1 + 2n2 + 3n3 + …… + knkn= B + 1∴ n0 + n1 + …… + nk = n1 + 2n2 + 3n3 + …… + knk + 1∴ n0 = n2 + 2n3 + …… + (k1)nk + 1，中序序列為ABCDEFGHIJK，請畫出該二叉樹。msobidifontfamily: Times N第六章實習(xí)題習(xí)題1．試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。（1）找結(jié)點的中序前驅(qū)結(jié)點BiTNodespan lang=ENUS style=39。在先序線索二叉樹T中，查找給定結(jié)點*p在先序序列中的后繼。【解答】 構(gòu)造哈夫曼樹如下：哈夫曼編碼為：I1：11111 I5：1100 I2：11110 I6： 10I3：1110 I7： 01 I4：1101 I8： 00。【解答】 (1) 前序與中序相同：空樹或缺左子樹的單支樹； (2) 中序與后序相同：空樹或缺右子樹的單支樹； (3) 前序與后序相同：空樹或只有根結(jié)點的二叉樹。(2) 中序序列與后序序列相同。第六章答案6． 1分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。 E D C 后序：CGBFDBA2．已知二叉樹按照二叉鏈表方式存儲，編寫算法，要求實現(xiàn)二叉樹的豎向顯示（豎向顯示就是二叉樹的按層顯示）。中序：CBEGDFA 輸出結(jié)果為： 先序：ABCDEGF要求采用遞歸和非遞歸兩種方法實現(xiàn)。 [問題描述] 建立一棵用二叉鏈表方式存儲的二叉樹，并對其進行遍歷（先序、中序和后序），打印輸出遍歷結(jié)果。實習(xí)題1.24. 二叉樹按照二叉鏈表方式存儲，編寫算法，將二叉樹左右子樹進行交換。21．已知二叉樹按照二叉鏈表方式存儲，利用棧的基本操作寫出先序遍歷非遞歸形式的算法。20．計算二叉樹最大寬度的算法。 19．設(shè)二叉樹按二叉鏈表存放，寫算法判別一棵二叉樹是否是一棵正則二叉樹。17．對以孩子兄弟鏈表表示的樹編寫計算樹的深度的算法。15．分別寫出算法，實現(xiàn)在中序線索二叉樹中查找給定結(jié)點*p在中序序列中的前驅(qū)與后繼。14．分別寫函數(shù)完成：在先序線索二叉樹T中，查找給定結(jié)點*p在先序序列中的后繼。12．已知二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結(jié)點的數(shù)目。10．已知二叉樹采用二叉鏈表存放,要求返回二叉樹T的后序序列中的第一個結(jié)點指針,是否可不用遞歸且不用棧來完成?請簡述原因.11. 畫出和下列樹對應(yīng)的二叉樹： 前序和后序相同7． n個結(jié)點的K叉樹，若用具有k個child域的等長鏈結(jié)點存儲樹的一個結(jié)點，則空的Child域有多少個？8．畫出與下列已知序列對應(yīng)的樹Ｔ：樹的先根次序訪問序列為GFKDAIEBCHJ；樹的后根次序訪問序列為DIAEKFCJHBG。 中序和后序相同③ 前序和后序相同②5．已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少應(yīng)有多少個？6．給出滿足下列條件的所有二叉樹：①3．已知一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，……，nk個度為k的結(jié)點，則該樹中有多少個葉子結(jié)點并證明之。 (d)第六章習(xí)題1．試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。 (b)（4） HEAD[TAIL[HEAD[((a,b),(c,d))]]]。 (a,b)（2） TAIL[((a,b),(c,d))]。 Position[col]++。 Bdata[q].col=[p].row。 q=position[col]。p。 position[col]=t+1。col0。t++) position[[t].col]++。 for(t=1。col=。 Bm=。Blen=。}}}算法(二)FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) {int col,t,p,q。 Bdata[q].e=[p].e。 Bdata[q].row=[p].col。p++){ col=[p].col。 for(p=1。col=。t++) position[[t].col+1]++。 for(t=1。 Bm=。Blen=?！窘獯稹克惴ǎㄒ唬? FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) {/*把矩陣A轉(zhuǎn)置到B所指向的矩陣中去，矩陣用三元組表表示*/int col,t,p,q。第五章答案n,將其三條對角線上的元素逐行的存于數(shù)組B[1..3n2]中，使得B[k]=aij，求：（1）用i,j表示k的下標(biāo)變換公式；（2）用k表示i、j的下標(biāo)變換公式。假設(shè)以二維數(shù)組存儲矩陣，試編寫算法求出矩陣中的所有馬鞍點。 TAIL[HEAD[TAIL[((a,b),(c,d))]]]。（5） TAIL[HEAD[((a,b),(c,d))]]。（3） HEAD[((a,b),(c,d))]。 ((((a), b)), ((( ), d), (e, f)))：（1）：，將計算position[col]的方法稍加改動，使算法只占用一個輔助向量空間。[提示]：（1） 被替換子串定位（相當(dāng)于第9題中i）（2） 被替換子串后面的字符左移或右移（為替換子串準(zhǔn)備房間）（3） 替換子串入?。◤?fù)制）（4） 重復(fù)上述，直到……第五章習(xí)題 假設(shè)有6行8列的二維數(shù)組A，每個元素占用6個字節(jié)，存儲器按字節(jié)編址。11． 寫算法，實現(xiàn)順序串的基本操作StrReplace(amp。9． 寫一個函數(shù)將順序串s1中的第i個字符到第j個字符之間的字符用s2串替換。（4） 從順序串r1中第index 個字符起求出首次與串r2相同的子串的起始位置。（2） 將順序串r中所有字符按照相反的次序仍存放在r中。7． S是用結(jié)點大小為4的單鏈表存儲的串,分別編寫算法在第k個字符后插入串T，及從第k個字符刪除len個字符。5． 已知：S=”(xyz)*”,T=”(x+z)*y”。[說明]：用單鏈表實現(xiàn)。3. 假設(shè)以塊鏈結(jié)構(gòu)表示串，塊的大小為1，且附設(shè)頭結(jié)點。 StrCat(StrCat(sub1,t), StrCat(sub2,q))= ’I AM A GOOD WORKER’。 StrIndex(s,’A’,4)=6。 sub1= ’I AM A_’。 StrCat(StrCat(sub1,t), StrCat(sub2,q))。StrIndex(s,’A’,4)。 SubString(sub1,s,1,7)。 /*失敗*/ }第4章 串習(xí)題1. 設(shè)s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’。} }if(q= =NULL) return(pos+i)。 q=Theadnext。 q=qnext。 q!=NULL) { Ppos=p。 while(p!=NULL amp。 j++。amp。q=Tnext。if(Tnext= =NULL || Snext = =NULL) return(0)。int strIndex(Lstring S, int pos, Lstring T) /*從串S的pos序號起，串T第一次出現(xiàn)的位置 */{ Node *p, *q, *Ppos。 struct Node *next。}/*StrReplace()*/ 附加題：用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)定位函數(shù)。} }/*switch()*/pos=StrIndex(S,pos+,T)。i++) Sch[i+pos]=[i]。} else /*串V的部分字符要舍棄*/ { for(i=0。i++) /*用V替換T*/ Sch[pos+i]=[i]。 i) Sch[i]=sch[+] for(i=0。 } else { /*替換后串長MAXLEN,但串V可以全部替換*/ if(pos+=MAXLEN) { for(i=MAXLEN1。i++) /*用V替換T*/ Sch[pos+i]=[i]。 for(i=0。i=pos+。 Slen=S+。i=。i