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

第三（1）n個結(jié)點可構(gòu)造出多少種不同形態(tài)的二叉樹？當n=111n個節(jié)點可組成的二叉樹數(shù)量表示為f(n)，則f(1)=1;當n=2時，1個根節(jié)點固定，還有n-1個節(jié)點，可以作為左，也可以作為，即：f(2)=f(0)*f(1)+f(1)*f(0)=22f(0)表示空，所以只能算一種形態(tài)，即f(0)=1;當n=3時，1個根節(jié)點固定，還有n-1=2個節(jié)點，可以在左或右，即f(3)=f(0)*f(2)+f(1)*f(1)+f(2)*f(0)=5，則能組成5種形態(tài)的二叉樹以此類推， 時，可組成的二叉樹數(shù)量f(n)=f(0)*f(n-1)+f(1)*f(n-2)+...+f(n-1)*f(0)種即符合Catalan數(shù)的定義，可直接利用通項公式得出結(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é)點個19個。因此總結(jié)點數(shù)n=n0+n1+n2=20+30+19=69個。 3.7在中序線索二叉樹中如何查找給定結(jié)點的前序后繼,前序后繼：如果節(jié)點的ltag==0，那么后繼是節(jié)點的左孩子，否則，如果ltag==1&&rtag==0，后繼是右孩子，如果ltag==1&&rtag==1，那么找到節(jié)點的父節(jié)點p，如果該節(jié)點是p的左孩子，且p->rtag==0，那么p的右孩子是節(jié)點的后>rtag==1>rchildqq的右孩子是后繼，否則 ->rchild,直到找到q->rtag==0的節(jié)點或者q==null為止，q==null說明所求節(jié)點沒有后繼。后序后繼：先根據(jù)中序全線索二叉樹的性質(zhì)找出p的父節(jié)點1）如果r->RightChild！=p則對r的右進行后序遍歷后的第一個節(jié)點就是p在后序序列中的后繼；如果沒有右，p在后序遍歷中的后繼就是r2）如果r->RightChild==p則rp在后序序列中的后繼。AABFECG JI前前前后前后前前前1J1后0H11D10G00C11E10F10B00A01I1 解答：高度為h的AVL(1+??= ?1當節(jié)點數(shù)為n時，根據(jù)上式可求得，數(shù)的最大高度為???????=?log??(√5+(??+1))?其中φ=2最小高度為???????=?log2(n+當)=1當h=2，N(2)=2當h=3，N(3)=4當h=4，N(4)=7當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)鍵字建立平衡二叉樹。畫出每次時二叉樹解 過程及旋轉(zhuǎn)如圖所示2292解：121由上題所得最后的結(jié)果可知：查找長度為0的結(jié)點個數(shù)為1，查找長度為1的結(jié)點個數(shù)為2，查找長度為2的結(jié)點個數(shù)為4，查找長度為3的結(jié)點個數(shù)為4，查41。因此：查找成功的平均查找長度1×0×

+2×1×

+4×2×

+4×3×14×1×

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