數(shù)據(jù)結(jié)構(gòu)第4單元課后練習(xí)答案.pptx

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

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

3、12，對字符集合進(jìn)行哈夫曼編碼，W為各字符的頻率。（1)畫出哈夫曼樹（2）計(jì)算帶權(quán)路徑長度 (3) 求各字符的編碼 A:1010 B:1011 C:100 D:00 E:01 F:11設(shè)計(jì)一個(gè)遞歸算法，實(shí)現(xiàn)對一個(gè)有序表的順序搜索。 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的有序表進(jìn)行對半查找的二叉判定樹，并求等概率搜索時(shí)，成功搜索的平均搜索長度。解：1 二叉判定樹如下：成功搜索的平均搜索長度 由于第i層有2i個(gè)結(jié)點(diǎn)，故平均搜索長度為：ASL log2(n+1)6394117112108652試證明哈夫曼算法的正確性。引理一 在Huffman樹中不存在度為1的結(jié)點(diǎn)。證明： 假設(shè)某個(gè)二叉樹T中存在度為1的結(jié)點(diǎn)a，a的唯一子結(jié)點(diǎn)為b，且以a為根的子樹的所有葉結(jié)點(diǎn)的WPL為。 現(xiàn)在T中刪除結(jié)點(diǎn)a，以結(jié)點(diǎn)b取代a形成一棵新的二叉樹T。設(shè)以b為根的子樹的所有葉結(jié)點(diǎn)的WPL為，則必有： 。 所以

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

6、n樹，權(quán)值最小的兩個(gè)葉結(jié)點(diǎn)是x和y，它們的權(quán)值分別是f(x)和f(y)，它們的路徑長度分別是l(x)和l(y) 。 根據(jù)引理二，可假設(shè)x與y互為兄弟結(jié)點(diǎn)。在二叉樹T中刪除結(jié)點(diǎn)x和y，將字母z以及權(quán)值f(z)=f(x)+f(y)賦予x和y在T中的父結(jié)點(diǎn)，則生成一棵在字母表C=C-x,y+z上的二叉樹T。 易知：l(x)=l(y)， l(z)=l(x)-1。假設(shè)T不是字母表C上的最優(yōu)二叉樹?？杉僭O(shè)T是。在T中找到葉結(jié)點(diǎn)z，在它下面添加兩個(gè)子結(jié)點(diǎn)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樹的某個(gè)葉結(jié)點(diǎn)，如果產(chǎn)生的兩個(gè)葉結(jié)點(diǎn)的權(quán)值在所有葉結(jié)點(diǎn)權(quán)值中最小，則將生成一棵新的Huffman樹。證明： 假設(shè)二叉樹T是字母表C上的一棵Huffman樹，z是它的一個(gè)葉節(jié)點(diǎn)。在z的下面添加兩個(gè)子結(jié)點(diǎn)

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