【正文】 ol=。col++) position[col]=position[col]+position[col1]。 for(p=1。p。p++){ col=[p].col。 q=position[col]。 Bdata[q].row=[p].col。 Bdata[q].col=[p].row。 Bdata[q].e=[p].e。 Position[col]++。}}}算法(二)FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) {int col,t,p,q。int position[MAXSIZE]。Blen=。 Bn=。 Bm=。if(Blen0){ for(col=1。col=。col++) position[col]=0。 for(t=1。t=。t++) position[[t].col]++。 /*計算每一列的非零元素的個數*//*[]中的位置，存放在position[col]中*/for(col=,t=。col0。col) { t=tposition[col]。 position[col]=t+1。}for(p=1。p。p++){ col=[p].col。 q=position[col]。 Bdata[q].row=[p].col。 Bdata[q].col=[p].row。 Bdata[q].e=[p].e。 Position[col]++。}}}： ((((a), b)), ((( ), d), (e, f)))【解答】第一種存儲結構 第二種存儲結構：（1） HEAD[((a,b),(c,d))]。 (a,b)（2） TAIL[((a,b),(c,d))]。 ((c,d)) （3） TAIL[HEAD[((a,b),(c,d))]]。 (b)（4） HEAD[TAIL[HEAD[((a,b),(c,d))]]]。 b（5） TAIL[HEAD[TAIL[((a,b),(c,d))]]]。 (d)第六章習題1．試分別畫出具有3個結點的樹和3個結點的二叉樹的所有不同形態(tài)。2．對題1所得各種形態(tài)的二叉樹，分別寫出前序、中序和后序遍歷的序列。3．已知一棵度為k的樹中有n1個度為1的結點，n2個度為2的結點，……，nk個度為k的結點，則該樹中有多少個葉子結點并證明之。，中序序列為ABCDEFGHIJK，請畫出該二叉樹。5．已知二叉樹有50個葉子結點，則該二叉樹的總結點數至少應有多少個？6．給出滿足下列條件的所有二叉樹：① 前序和后序相同② 中序和后序相同③ 前序和后序相同7． n個結點的K叉樹，若用具有k個child域的等長鏈結點存儲樹的一個結點，則空的Child域有多少個？8．畫出與下列已知序列對應的樹Ｔ：樹的先根次序訪問序列為GFKDAIEBCHJ；樹的后根次序訪問序列為DIAEKFCJHBG。9．假設用于通訊的電文僅由8個字母組成，字母在電文中出現的頻率分別為：，，，，請為這8個字母設計哈夫曼編碼。10．已知二叉樹采用二叉鏈表存放,要求返回二叉樹T的后序序列中的第一個結點指針,是否可不用遞歸且不用棧來完成?請簡述原因.11. 畫出和下列樹對應的二叉樹：12．已知二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結點的數目。13．編寫遞歸算法：對于二叉樹中每一個元素值為x的結點，刪去以它為根的子樹，并釋放相應的空間。14．分別寫函數完成：在先序線索二叉樹T中，查找給定結點*p在先序序列中的后繼。在后序線索二叉樹T中，查找給定結點*p在后序序列中的前驅。15．分別寫出算法，實現在中序線索二叉樹中查找給定結點*p在中序序列中的前驅與后繼。16．編寫算法，對一棵以孩子兄弟鏈表表示的樹統(tǒng)計其葉子的個數。17．對以孩子兄弟鏈表表示的樹編寫計算樹的深度的算法。18．已知二叉樹按照二叉鏈表方式存儲，利用棧的基本操作寫出后序遍歷非遞歸的算法。 19．設二叉樹按二叉鏈表存放，寫算法判別一棵二叉樹是否是一棵正則二叉樹。正則二叉樹是指：在二叉樹中不存在子樹個數為1的結點。20．計算二叉樹最大寬度的算法。二叉樹的最大寬度是指：二叉樹所有層中結點個數的最大值。21．已知二叉樹按照二叉鏈表方式存儲，利用棧的基本操作寫出先序遍歷非遞歸形式的算法。22. 證明：給定一棵二叉樹的前序序列與中序序列，可唯一確定這棵二叉樹；　　　　　給定一棵二叉樹的后序序列與中序序列，可唯一確定這棵二叉樹；23. 二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結點的數目。24. 二叉樹按照二叉鏈表方式存儲，編寫算法，將二叉樹左右子樹進行交換。實習題1. [問題描述] 建立一棵用二叉鏈表方式存儲的二叉樹，并對其進行遍歷（先序、中序和后序），打印輸出遍歷結果。[基本要求] 從鍵盤接受輸入先序序列，以二叉鏈表作為存儲結構，建立二叉樹（以先序來建立）并對其進行遍歷（先序、中序、后序），然后將遍歷結果打印輸出。要求采用遞歸和非遞歸兩種方法實現。[測試數據] ABCффDEфGффFффф（其中ф表示空格字符） 輸出結果為： 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA2．已知二叉樹按照二叉鏈表方式存儲，編寫算法，要求實現二叉樹的豎向顯示（豎向顯示就是二叉樹的按層顯示）。3．如題1要求建立好二叉樹，按凹入表形式打印二叉樹結構，如下圖所示。A B C D E 2. 按凹入表形式打印樹形結構，如下圖所示。 第六章答案6． 1分別畫出具有3個結點的樹和3個結點的二叉樹的所有不同形態(tài)。【解答】具有3個結點的樹 具有3個結點的二叉樹 ，n2個度為2的結點，……，nk個度為k的結點，則該樹中有多少個葉子結點？【解答】設樹中結點總數為n,則n=n0 + n1 + …… + nk樹中分支數目為B,則B=n1 + 2n2 + 3n3 + …… + knk因為除根結點外，每個結點均對應一個進入它的分支，所以有n= B + 1即n0 + n1 + …… + nk = n1 + 2n2 + 3n3 + …… + knk + 1由上式可得葉子結點數為：n0 = n2 + 2n3 + …… + (k1)nk + 1，則該二叉樹的總結點數至少應有多少個？【解答】n0表示葉子結點數，n2表示度為2的結點數，則n0 = n2+1 所以n2= n0 –1=49，當二叉樹中沒有度為1的結點時，總結點數n=n0+n2=99 試分別找出滿足以下條件的所有二叉樹:(1) 前序序列與中序序列相同。(2) 中序序列與后序序列相同。(3) 前序序列與后序序列相同。【解答】 (1) 前序與中序相同：空樹或缺左子樹的單支樹； (2) 中序與后序相同：空樹或缺右子樹的單支樹； (3) 前序與后序相同：空樹或只有根結點的二叉樹。 假設通訊的電文僅由8個字母組成，字母在電文中出現的頻率分別為：，，，，請為這8個字母設計哈夫曼編碼?！窘獯稹? 構造哈夫曼樹如下：哈夫曼編碼為：I1：11111 I5：1100 I2：11110 I6： 10I3：1110 I7： 01 I4：1101 I8： 00?！窘獯稹?，實現在中序線索二叉樹T中查找給定結點*p在中序序列中的前驅與后繼。在先序線索二叉樹T中，查找給定結點*p在先序序列中的后繼。在后序線索二叉樹T中，查找給定結點*p在后序序列中的前驅。（1）找結點的中序前驅結點BiTNodespan lang=ENUS style=39。fontfamily:Arial。msobidifontfamily: Times N第六章實習題習題1．試分別畫出具有3個結點的樹和3個結點的二叉樹的所有不同形態(tài)。2．對題1所得各種形態(tài)的二叉樹，分別寫出前序、中序和后序遍歷的序列。3．已知一棵度為k的樹中有n1個度為1的結點，n2個度為2的結點，……，nk個度為k的結點，則該樹中有多少個葉子結點？[提示]：參考 性質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，請畫出該二叉樹。[提示]：參考 6． 已知二叉樹有50個葉子結點，則該二叉樹的總結點數至少應有多少個？[提示]：[方法1] （1）一個葉子結點，總結點數至多有多少個？結論：可壓縮一度結點。（2）滿二叉樹或完全二叉樹具有最少的一度結點（3）可能的最大滿二叉樹是幾層？有多少葉結點？如何增補？255026可能的最大滿二叉樹是6層有 25 = 32個葉結點假設將其中x個變?yōu)?度結點后，總葉結點數目為50則：2x + (32 – x) = 50得：x = 18此時總結點數目= ( 26 – 1) + 182[方法2]假設完全二叉樹的最大非葉結點編號為m，則最大葉結點編號為2m+1,(2m+1)m=50m=49總結點數目=2m+1=99[方法3]由性質3：n0=n2+1即：50=n2+1所以：n2=49令n1=0得：n= n0 + n2=997． 給出滿足下列條件的所有二叉樹：a) 前序和中序相同b) 中序和后序相同c) 前序和后序相同[提示]：去異存同。a) D L R 與L D R 的相同點：D R，如果無 L，則完全相同, 如果無 LR，…。b) L D R 與L R D 的相同點：L D，如果無 R，則完全相同。c) D L R 與L R D 的相同點：D，如果無 L R，則完全相同。（如果去D，則為空樹）7． n個結點的K叉樹，若用具有k個child域的等長鏈結點存儲樹的一個結點，則空的Child域有多少個？[提示]：參考 8．畫出與下列已知序列對應的樹Ｔ：樹的先根次序訪問序列為GFKDAIEBCHJ；樹的后根次序訪問序列為DIAEKFCJHBG。[提示]：（1）先畫出對應的二叉樹（2）樹的后根序列與對應二叉樹的中序序列相同9．假設用于通訊的電文僅由8個字母組成，字母在電文中出現的頻率分別為：，，，，（1）請為這8個字母設計哈夫曼編碼，（2）求平均編碼長度。10．已知二叉樹采用二叉鏈表存放,要求返回二叉樹T的后序序列中的第一個結點的指針,是否可不用遞歸且不用棧來完成?請簡述原因.[提示]：無右子的“左下端”11. 畫出和下列樹對應的二叉樹：12．已知二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結點的數目。13．編寫遞歸算法：對于二叉樹中每一個元素值為x的結點，刪去以它為根的子樹，并釋放相應的空間。[提示]：[方法1]：（1）按先序查找；（2）超前查看子結點（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）直接查看當前根結點（3）用指針參數；[方法3]：（1）先序查找；（2）直接查看當前根結點（3）通過函數值，返回刪除后結果；（參示例程序）14．分別寫函數完成：在先序線索二叉樹T中，查找給定結點*p在先序序列中的后繼。在后序線索二叉樹T中，查找給定結點*p在后序序列中的前驅。[提示]：（1）先查看線索，無線索時用下面規(guī)律：（2）結點*p在先序序列中的后繼為其左子或右子；（3）結點*p在后序序列中的前驅也是其左子或右子。15．分別寫出算法，實現在中序線索二叉樹中查找給定結點*p在中序序列中的前驅與后繼。（參例題）16．編寫算法，對一棵