第六章習題
1．試分別畫出具有3個結點的樹和3個結點的二叉樹的所有不同形態。
2．對題1所得各種形態的二叉樹，分別寫出前序、中序和後序遍歷的序列。
3．已知一棵度為k的樹中有n1個度為1的結點，n2個度為2的結點，……，nk個度為k的結點，則該樹中有多少個葉子結點並證明之。
4.假設一棵二叉樹的先序序列為ebadcfhgikj，中序序列為abcdefghijk，請畫出該二叉樹。
5．已知二叉樹有50個葉子結點，則該二叉樹的總結點數至少應有多少個？
6．給出滿足下列條件的所有二叉樹：
① 前序和後序相同
② 中序和後序相同
③ 前序和後序相同
7． n個結點的k叉樹，若用具有k個child域的等長鏈結點儲存樹的乙個結點，則空的child域有多少個？
8．畫出與下列已知序列對應的樹ｔ：
樹的先根次序訪問序列為gfkdaiebchj；
樹的後根次序訪問序列為diaekfcjhbg。
9．假設用於通訊的電文僅由8個字母組成，字母在電文中出現的頻率分別為：
0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10
請為這8個字母設計哈夫曼編碼。
10．已知二叉樹採用二叉鍊錶存放,要求返回二叉樹t的後序序列中的第乙個結點指標,是否可不用遞迴且不用棧來完成?請簡述原因.
11. 畫出和下列樹對應的二叉樹：
12．已知二叉樹按照二叉鍊錶方式儲存，編寫演算法，計算二叉樹中葉子結點的數目。
13．編寫遞迴演算法：對於二叉樹中每乙個元素值為x的結點，刪去以它為根的子樹，並釋放相應的空間。
14．分別寫函式完成：在先序線索二叉樹t中，查詢給定結點*p在先序序列中的後繼。在後序線索二叉樹t中，查詢給定結點*p在後序序列中的前驅。
15．分別寫出演算法，實現在中序線索二叉樹中查詢給定結點*p在中序序列中的前驅與後繼。
16．編寫演算法，對一棵以孩子-兄弟鍊錶表示的樹統計其葉子的個數。
17．對以孩子-兄弟鍊錶表示的樹編寫計算樹的深度的演算法。
18．已知二叉樹按照二叉鍊錶方式儲存，利用棧的基本操作寫出後序遍歷非遞迴的演算法。
19．設二叉樹按二叉鍊錶存放，寫演算法判別一棵二叉樹是否是一棵正則二叉樹。正則二叉樹是指：在二叉樹中不存在子樹個數為1的結點。
20．計算二叉樹最大寬度的演算法。二叉樹的最大寬度是指：二叉樹所有層中結點個數的最大值。
21．已知二叉樹按照二叉鍊錶方式儲存，利用棧的基本操作寫出先序遍歷非遞迴形式的演算法。
22. 證明：給定一棵二叉樹的前序序列與中序序列，可唯一確定這棵二叉樹；
給定一棵二叉樹的後序序列與中序序列，可唯一確定這棵二叉樹；
23. 二叉樹按照二叉鍊錶方式儲存，編寫演算法，計算二叉樹中葉子結點的數目。
24. 二叉樹按照二叉鍊錶方式儲存，編寫演算法，將二叉樹左右子樹進行交換。
實習題1. [問題描述] 建立一棵用二叉鍊錶方式儲存的二叉樹，並對其進行遍歷（先序、中序和後序），列印輸出遍歷結果。
[基本要求] 從鍵盤接受輸入先序序列，以二叉鍊錶作為儲存結構，建立二叉樹（以先序來建立）並對其進行遍歷（先序、中序、後序），然後將遍歷結果列印輸出。要求採用遞迴和非遞迴兩種方法實現。
[測試資料] abcффdeфgффfффф（其中ф表示空格字元）
輸出結果為： 先序：abcdegf
中序：cbegdfa
後序：cgbfdba
2．已知二叉樹按照二叉鍊錶方式儲存，編寫演算法，要求實現二叉樹的豎向顯示（豎向顯示就是二叉樹的按層顯示）。
3．如題1要求建立好二叉樹，按凹入錶形式列印二叉樹結構，如下圖所示。
2. 按凹入錶形式列印樹形結構，如下圖所示。
第六章答案
6． 1分別畫出具有3個結點的樹和3個結點的二叉樹的所有不同形態。
【解答】
具有3個結點的樹具有3個結點的二叉樹
6.3已知一棵度為k的樹中有n1個度為1的結點，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 + …… + (k-1)nk + 1
6.5已知二叉樹有50個葉子結點，則該二叉樹的總結點數至少應有多少個？
【解答】n0表示葉子結點數，n2表示度為2的結點數，則n0 = n2+1
所以n2= n0 –1=49，當二叉樹中沒有度為1的結點時，總結點數n=n0+n2=99
6.6 試分別找出滿足以下條件的所有二叉樹:
(1) 前序序列與中序序列相同;
(2) 中序序列與後序序列相同;
(3) 前序序列與後序序列相同。
【解答】
(1) 前序與中序相同：空樹或缺左子樹的單支樹；
(2) 中序與後序相同：空樹或缺右子樹的單支樹；
(3) 前序與後序相同：空樹或只有根結點的二叉樹。
6.9 假設通訊的電文僅由8個字母組成，字母在電文中出現的頻率分別為：
0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10
請為這8個字母設計哈夫曼編碼。
【解答】
構造哈夫曼樹如下：
哈夫曼編碼為：
i1：11111 i5：1100
i2：11110 i6： 10
i3：1110 i7： 01
i4：1101 i8： 00
6.11畫出如下圖所示樹對應的二叉樹。
【解答】
6.15分別寫出演算法，實現在中序線索二叉樹t中查詢給定結點*p在中序序列中的前驅與後繼。在先序線索二叉樹t中，查詢給定結點*p在先序序列中的後繼。
在後序線索二叉樹t中，查詢給定結點*p在後序序列中的前驅。
（1）找結點的中序前驅結點
bitnode *inpre (bitnode *p)
/*在中序線索二叉樹中查詢p的中序前驅結點，並用pre指標返回結果*/
return (pre);
}（2）找結點的中序後繼結點
bitnode *insucc (bitnode *p)
/*在中序線索二叉樹中查詢p的中序後繼結點，並用succ指標返回結果*/
return (succ);
}(3) 找結點的先序後繼結點
bitnode *presucc (bitnode *p)
/*在先序線索二叉樹中查詢p的先序後繼結點，並用succ指標返回結果*/
(4) 找結點的後序前驅結點
bitnode *succpre (bitnode *p)
/*在後序線索二叉樹中查詢p的後序前驅結點，並用pre指標返回結果*/
6.21已知二叉樹按照二叉鍊錶方式儲存，利用棧的基本操作寫出先序遍歷非遞迴形式的演算法。
【解答】
void preorder(bitree root) /*先序遍歷二叉樹的非遞迴演算法*/
else}}
6.24已知二叉樹按照二叉鍊錶方式儲存，編寫演算法，將二叉樹左右子樹進行交換。
【解答】
演算法(一)
void exchange ( bitree root )
} 演算法(二)
void exchange ( bitree root )
{ p=root;
資料結構課後習題第六章
一 選擇題 1.設高度為h的二叉樹只有為0和2的結點，則此類二叉樹的結點數至少有 個，至多有幾個 a.2h b.2h 1 c.2h 1 d.2h 1 e.2h 1 f.2h 1 2.高度為h的完全二叉樹有 個結點，至多有 個結點。a.2h b.2h 1 c.2h 1 d.2h 1 3.具有n個結點的...
資料結構習題答案耿國華主編第六章
6.27 問題 假設一棵二叉樹的先序序列為ebadcfhgikj和中序序列為abcdefghijk。請畫出該樹。解答 6.29 問題 假設一棵二叉樹的層序序列為abcdefghij和中序序列為dbgehjacif。請畫出該樹。6.37 問題 試利用棧的基本操作寫出先序遍歷二叉樹的非遞迴演算法。解答提...
資料結構試題和答案第六章
a a 2n b n l c n l d n 11.由3 個結點可以構造出多少種不同的二叉樹？a a 2 b 3 c 4 d 5 12.深度為k的完全二叉樹至少有 個結點，至多有 個結點。13.具有n個結點的二叉樹，採用二叉鍊錶儲存，共有 個空鏈域。14.n個結點的線索二叉樹上含有的線索數為 15....