數(shù)據(jù)結(jié)構(gòu)課后題答案第3章

第三（1）n個(gè)結(jié)點(diǎn)可構(gòu)造出多少種不同形態(tài)的二叉樹？當(dāng)n=111n個(gè)節(jié)點(diǎn)可組成的二叉樹數(shù)量表示為f(n)，則f(1)=1;當(dāng)n=2時(shí)，1個(gè)根節(jié)點(diǎn)固定，還有n-1個(gè)節(jié)點(diǎn)，可以作為左，也可以作為，即：f(2)=f(0)*f(1)+f(1)*f(0)=22f(0)表示空，所以只能算一種形態(tài)，即f(0)=1;當(dāng)n=3時(shí)，1個(gè)根節(jié)點(diǎn)固定，還有n-1=2個(gè)節(jié)點(diǎn)，可以在左或右，即f(3)=f(0)*f(2)+f(1)*f(1)+f(2)*f(0)=5，則能組成5種形態(tài)的二叉樹以此類推， 時(shí)，可組成的二叉樹數(shù)量f(n)=f(0)*f(n-1)+f(1)*f(n-2)+...+f(n-1)*f(0)種即符合Catalan數(shù)的定義，可直接利用通項(xiàng)公式得出結(jié)果。h(n)=h(n-1)*(4*n-h(n)=C(2n,n)/(n+1)（2）31,2,31,2,3的不同 21

2

23 12

(5)326，1710、1、2n0、n1、n2。由題可知：n0=20,n1=30。02n2n0-1=20-1=19，即度為2的結(jié)點(diǎn)個(gè)19個(gè)。因此總結(jié)點(diǎn)數(shù)n=n0+n1+n2=20+30+19=69個(gè)。 3.7在中序線索二叉樹中如何查找給定結(jié)點(diǎn)的前序后繼,前序后繼：如果節(jié)點(diǎn)的ltag==0，那么后繼是節(jié)點(diǎn)的左孩子，否則，如果ltag==1&&rtag==0，后繼是右孩子，如果ltag==1&&rtag==1，那么找到節(jié)點(diǎn)的父節(jié)點(diǎn)p，如果該節(jié)點(diǎn)是p的左孩子，且p->rtag==0，那么p的右孩子是節(jié)點(diǎn)的后>rtag==1>rchildqq的右孩子是后繼，否則 ->rchild,直到找到q->rtag==0的節(jié)點(diǎn)或者q==null為止，q==null說明所求節(jié)點(diǎn)沒有后繼。后序后繼：先根據(jù)中序全線索二叉樹的性質(zhì)找出p的父節(jié)點(diǎn)1）如果r->RightChild！=p則對(duì)r的右進(jìn)行后序遍歷后的第一個(gè)節(jié)點(diǎn)就是p在后序序列中的后繼；如果沒有右，p在后序遍歷中的后繼就是r2）如果r->RightChild==p則rp在后序序列中的后繼。AABFECG JI前前前后前后前前前1J1后0H11D10G00C11E10F10B00A01I1 解答：高度為h的AVL(1+??= ?1當(dāng)節(jié)點(diǎn)數(shù)為n時(shí)，根據(jù)上式可求得，數(shù)的最大高度為???????=?log??(√5+(??+1))?其中φ=2最小高度為???????=?log2(n+當(dāng))=1當(dāng)h=2，N(2)=2當(dāng)h=3，N(3)=4當(dāng)h=4，N(4)=7當(dāng)h=5，N(5)=12歸納可以發(fā)現(xiàn)類 那契數(shù)列的規(guī)律N(h)=N(h?1)+N(h?2)+其中h>23.1220,9,2,11,13,30,22,16,17,15,18,10試從空樹開始順序輸入各關(guān)鍵字建立平衡二叉樹。畫出每次時(shí)二叉樹解 過程及旋轉(zhuǎn)如圖所示2292解：121由上題所得最后的結(jié)果可知：查找長度為0的結(jié)點(diǎn)個(gè)數(shù)為1，查找長度為1的結(jié)點(diǎn)個(gè)數(shù)為2，查找長度為2的結(jié)點(diǎn)個(gè)數(shù)為4，查找長度為3的結(jié)點(diǎn)個(gè)數(shù)為4，查41。因此：查找成功的平均查找長度1×0×

+2×1×

+4×2×

+4×3×14×1×

=26= 刪除刪除 3.158個(gè)字母A，B，C，D，E，F(xiàn)，G，H組成,各字母5,25,3,6,10,11,36,48個(gè)字母設(shè)計(jì)不等長Huffman編碼,并給出該電文的總碼數(shù)。A:0110B:10C:0000D:0111E:001F:010G:112，n-1個(gè)葉結(jié)點(diǎn)，1個(gè)分支結(jié)點(diǎn)。高度最大為n，1個(gè)葉結(jié)點(diǎn)，n-1個(gè)分支結(jié)點(diǎn)先序后序ABE