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

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

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

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

5、，WPL(T) WPL(T)。即T不可能是Huffman樹(shù)。試證明哈夫曼算法的正確性。引理二 在字母表C上，一定存在這樣一棵Huffman樹(shù)：權(quán)值最小的兩個(gè)葉結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)。證明： 假設(shè)二叉樹(shù)T是字母表C上的一棵Huffman樹(shù)，權(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形成一棵新的二叉樹(shù)T 。 可知WPL(T)=WPL(T)。證畢。試證明哈夫曼算法的正確性。引理三 合并一棵Huffman樹(shù)中權(quán)值最小的兩個(gè)葉結(jié)點(diǎn)，將生成一棵新的Huffman樹(shù)。證明： 假設(shè)二叉樹(shù)T是字母表C上的一棵Huffma

6、n樹(shù)，權(quán)值最小的兩個(gè)葉結(jié)點(diǎn)是x和y，它們的權(quán)值分別是f(x)和f(y)，它們的路徑長(zhǎng)度分別是l(x)和l(y) 。 根據(jù)引理二，可假設(shè)x與y互為兄弟結(jié)點(diǎn)。在二叉樹(shù)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上的二叉樹(shù)T。 易知：l(x)=l(y)， l(z)=l(x)-1。假設(shè)T不是字母表C上的最優(yōu)二叉樹(shù)。可假設(shè)T是。在T中找到葉結(jié)點(diǎn)z，在它下面添加兩個(gè)子結(jié)點(diǎn)x和y，形成一棵字母表C上的二叉樹(shù)?？芍?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樹(shù)”的前提條件相矛盾。所以，T是字母表C上的最優(yōu)二叉樹(shù)。證畢。試證明哈夫曼算法的正確性。定理 分裂一棵Huffman樹(shù)的某個(gè)葉結(jié)點(diǎn)，如果產(chǎn)生的兩個(gè)葉結(jié)點(diǎn)的權(quán)值在所有葉結(jié)點(diǎn)權(quán)值中最小，則將生成一棵新的Huffman樹(shù)。證明： 假設(shè)二叉樹(shù)T是字母表C上的一棵Huffman樹(shù)，z是它的一個(gè)葉節(jié)點(diǎn)。在z的下面添加兩個(gè)子結(jié)點(diǎn)

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