1、習題八: 根樹及其應用1從簡單有向圖的鄰接矩陣怎樣去決定它是否為根樹。如果是根樹，怎樣定出它的樹根和樹葉。2求出對應于圖7-8.9所給出的樹的二叉樹。1413983124567101112圖7-8.93證明在完全二叉樹中，邊的總數等于，式中是樹葉數。4在一棵叉樹中，其外部通路長度與內部通路長度之間有什么關系。5給定權1，4，9，16，25，36，49，64，81，100a）構造一棵最優二叉樹。b）構造一棵最優三叉樹。c）說明如何構造一棵最優叉樹。6構造一個與英文字母對應的前綴碼，并畫出該前綴碼對應的二叉樹，再用此六個字母構成一個英文短語，寫出此短語的編碼信息。7設是二進制序列的集合。我們將劃分

2、為兩個子集和，這里是中第一個數字是0的序列的集合，是中第一個數字是1的序列的集合，然后我們根據序列中的第二個數字將劃分成兩個子集，對也用同樣方法加以劃分。運用不斷的將序列的集合劃分成子集的方法來證明：如果是前綴碼，則存在一棵二叉樹，其中從每個分枝點射出的兩條邊分別標號0和1，使得賦于樹葉的0和1的序列是中的序列。8給出公式（的根樹表示。9（1）求帶權為1，1，2，3，3，4，5，6，7的最優三元樹。 （2）求帶權為1，1，2，3，3，4，5，6，7，8的最優三元樹。10在通信中要傳輸八進制數字0，1，2，7。這些數字出現的頻率為0：30%；1：20%；2：15%；3：10%；4：10%；5：6

3、%；6：5%；7：4%。 編一個最佳前綴碼，使通信中出現的二進制數字盡可能地少。具體要求如下：（1） 畫出相應的二元樹。（2） 寫出每個數字對應的前綴碼。（3） 傳輸按上述比例出現的數字10000個時，至少要用多少個二進制數字？11如何由有向圖G的鄰接矩陣判定G是否為根樹，若為根樹，如何定出它的樹根和樹葉。12非平凡的無向連通圖G是樹當且僅當G的每條邊都是割邊。13根數中最長路徑的端點都是樹葉嗎？為什么？14證明：若T是有n個結點的完全二元樹，則T有片樹葉。15設T為高為h的r元正則樹，證明T的樹葉數t滿足： 。16（1）求帶權為2，3，5，7，8的最優二元樹T。 （2）求T對應的二元前綴碼。

4、17將圖7-9所示的有序樹表示成二叉樹并求出相應的前綴碼。 52678910413圖7-918根據圖7-10中所示的兩棵二元樹，產生兩個前綴碼。圖7-10（1）（2）19. 在下面給出的3個符號串集合中，哪些是前綴碼？哪些不是前綴碼？若是前綴碼，構造二叉樹，其樹葉代表二進制編碼。若不是前綴碼，則說明理由。（1）B1=0，10，110，1111；（2）B2=1，01，001，000；（3）B3=1，11，101，001，0011。20連通圖G的樹圖是一個圖，它的結點為G的生成樹，與相鄰的充要條件是它們恰好有v-2條公共邊（其中v為G的結點數）。證明：連通圖的樹圖是連通圖。21在圖7-11中，（1

5、），（2）所示的連通圖G1，G2中各有幾棵非同構的生成樹？（1）（2）圖7-1122畫出具有7個結點的所有非同構的樹。23結點已標定的，和各有多少棵生成樹？24（1）證明完全二元樹的樹葉數比內部結點數大1。 （2）找出完全n元樹的樹葉數的表達式，該表達式用樹的內部結點數的項表示。25證明一棵完全二元樹必有奇數個結點。26在圖7-12（1）、（2）所示的兩圖中各求一棵最小生成樹，將生成樹用粗邊給出并計算它們的權。7-12 4ae54143d63c2babc9d125e8516798f56（1）（2）7-12 4ae54143d63c2babc9d125e8516798f567-12 4ae54143d63c2babc9d125e8516798f5627在圖7-13所示的帶權圖G中共有多少棵生成樹，它們的權各為多少？其中哪些是圖中的最小生成樹？adbcv3v6v8v9v7v5v4v1v0v2圖7-13圖7-144122328分別用先根、中根、和后根的次序通過如圖7-14所示的二叉樹。29設G是一無向加權圖且各邊的權不相等，V，E分