數(shù)據(jù)結構第4單元課后練習答案.pptx

1、第四單元 樹形結構對于三個結點A，B和C，可分別組成多少不同的無序樹、有序樹和二叉樹？答：（1）無序樹：9棵 （2）有序樹：12棵 （3）二叉樹：30棵高度為h的k叉樹的特點是：第h層的節(jié)點度為0，其余結點的度均為k。如果按從上到下，從左到右的次序從1開始編號，則： 各層的結點是多少？ 編號為i的結點的雙親的編號是多少？ 編號為i的結點的第m個孩子的編號是多少？ 編號為i的結點的有右兄弟的條件是什么？答： 第i層有ki-1個 (i-1)/k k(i-1)+m+1 根據(jù)和的結果有：i k(i-1)/k-1)+k+1即： i k (i-1)/k 設對一棵二叉樹進行中序遍歷和后序遍歷的結果分別為：

2、（1）中序遍歷 B D C E A F H G （2）后序遍歷 D E C B H G F A 畫出該二叉樹。寫出下面得二叉樹的遍歷結果。先序：ADEHFJGBCK中序：HEJFGDABKC后序：HJGFEDKCBA設計算法，交換一棵二叉樹中每個結點的左、右子樹。template void BTree:Exch(BTNode *p) if (p) BTNode *q=Exch(p-lchild); p-lchild=Exch(p-rchild); p-rchild=q; 把下圖中的樹轉換成對應的二叉樹。把下圖中的二叉樹轉換成對應的樹或森林。設S=A,B,C,D,E,F，W=2,3,5,7,9,

3、12，對字符集合進行哈夫曼編碼，W為各字符的頻率。（1)畫出哈夫曼樹（2）計算帶權路徑長度 (3) 求各字符的編碼 A:1010 B:1011 C:100 D:00 E:01 F:11設計一個遞歸算法，實現(xiàn)對一個有序表的順序搜索。 templateint SeqList:Search4(const T& x) const elementslength=1000; return Sch4(x,0);templateint SeqList:Sch4(const T& x,int i) const if (xelementsi) return 0; else if (x=elementsi) ret

4、urn +i; else return Sch4(x,i+1);畫出對長度為12的有序表進行對半查找的二叉判定樹，并求等概率搜索時，成功搜索的平均搜索長度。解：1 二叉判定樹如下：成功搜索的平均搜索長度 由于第i層有2i個結點，故平均搜索長度為：ASL log2(n+1)6394117112108652試證明哈夫曼算法的正確性。引理一 在Huffman樹中不存在度為1的結點。證明： 假設某個二叉樹T中存在度為1的結點a，a的唯一子結點為b，且以a為根的子樹的所有葉結點的WPL為。 現(xiàn)在T中刪除結點a，以結點b取代a形成一棵新的二叉樹T。設以b為根的子樹的所有葉結點的WPL為，則必有： 。 所以

5、，WPL(T) WPL(T)。即T不可能是Huffman樹。試證明哈夫曼算法的正確性。引理二 在字母表C上，一定存在這樣一棵Huffman樹：權值最小的兩個葉結點互為兄弟結點。證明： 假設二叉樹T是字母表C上的一棵Huffman樹，權值最小的兩個葉結點是a和b。 根據(jù)引理一，a必有兄弟結點。假設a的兄弟結點不是b，可設為a。 容易證明a、 a與b有相同的層次，交換a與b形成一棵新的二叉樹T 。 可知WPL(T)=WPL(T)。證畢。試證明哈夫曼算法的正確性。引理三 合并一棵Huffman樹中權值最小的兩個葉結點，將生成一棵新的Huffman樹。證明： 假設二叉樹T是字母表C上的一棵Huffma

6、n樹，權值最小的兩個葉結點是x和y，它們的權值分別是f(x)和f(y)，它們的路徑長度分別是l(x)和l(y) 。 根據(jù)引理二，可假設x與y互為兄弟結點。在二叉樹T中刪除結點x和y，將字母z以及權值f(z)=f(x)+f(y)賦予x和y在T中的父結點，則生成一棵在字母表C=C-x,y+z上的二叉樹T。 易知：l(x)=l(y)， l(z)=l(x)-1。假設T不是字母表C上的最優(yōu)二叉樹?？杉僭OT是。在T中找到葉結點z，在它下面添加兩個子結點x和y，形成一棵字母表C上的二叉樹?？芍?WPL(T)=WPL(T)-f(x)l(x)-f(y)l(y)+f(z)l(z)=WPL(T)-(f(x)+f(

7、y)l(x)+f(z)l(z) =WPL(T)-f(z)l(x)+f(z)(l(x)-1)=WPL(T)-f(x)-f(y)。 同理可知WPL(T)= WPL()-f(x)-f(y)。 由于WPL(T)WPL(T)，可得WPL()WPL(T)。這與“T是字母表C上的一棵Huffman樹”的前提條件相矛盾。所以，T是字母表C上的最優(yōu)二叉樹。證畢。試證明哈夫曼算法的正確性。定理 分裂一棵Huffman樹的某個葉結點，如果產(chǎn)生的兩個葉結點的權值在所有葉結點權值中最小，則將生成一棵新的Huffman樹。證明： 假設二叉樹T是字母表C上的一棵Huffman樹，z是它的一個葉節(jié)點。在z的下面添加兩個子結點

8、x和y，它們的權值分別是f(x)和f(y)，且滿足f(z)=f(x)+f(y)， f(x)和f(y)在字母表C =C-z+x,y上的權值最小，可設新產(chǎn)生的二叉樹為T。 在字母表C上存在一棵最優(yōu)二叉樹T，在T上x和y互為兄弟結點。在T中刪除結點x和y，將字母z以及權值f(z)=f(x)+f(y)賦予x和y在T中的父結點，得到一棵在字母表C上的二叉樹。 根據(jù)引理三，可知是字母表C上的最優(yōu)二叉樹，由于T也是字母表C上的最優(yōu)二叉樹，所以WPL()= WPL(T)。 由于WPL()= WPL(T)-f(x)-f(y)， WPL(T)= WPL(T)-f(x)-f(y)，所以WPL(T)=WPL(T)，即，T是字母表C上的最優(yōu)二叉樹。證畢。補充說明：利用Huffman算法構造一棵二叉樹T后，單獨取出根結點和它的兩個子結點，則該子樹必是一棵最優(yōu)二叉樹。以后，按照與T的形成過程的相反的順序依次分解各葉結點，直到再次構造出T，則依據(jù)上面的定理可知T是一棵Huffman樹。試證明在哈夫曼算法的實施過程中，二叉樹森林中的每一棵子樹都是Huffman樹。證明： 在Huffman算法進行的每一步，都會有一棵新的二叉樹產(chǎn)生，它是合并原來森林中根結點權值最小的兩棵子樹而得來的。假設此二叉樹為T。 取T的根為一棵獨立的子樹，則它是一棵Huffman樹，將此結點向