以下是應(yīng)屆畢業(yè)生網(wǎng)為大家整理好的范文，希望對(duì)大家有所幫助！如有疑問請(qǐng)關(guān)注本網(wǎng)站！

　　證明：采用數(shù)學(xué)歸納法，先證(2)和(3)。

　　設(shè)n個(gè)結(jié)點(diǎn)的完全二叉樹如圖所示。

　　i=1時(shí),顯然 i 結(jié)點(diǎn)的左子編號(hào)為2，i的右子編號(hào)為2+1=3，除非2>n , 3>n 。

　　設(shè)對(duì)i結(jié)點(diǎn)，命題(2)、(3)成立，即Lchild(i)=2i，Rchild(i)=2i+1。根據(jù)按層編號(hào)規(guī)則，i+1時(shí)有：

　　Lchild(i+1)=(2i+1)+1=2(i+1)，除非2(i+1)>n,

　　Rchild(i+1)=(2i+1)+1+1=2(i+1)+1，除非2(i+1)+1>n，

　　故(2)、(3)得證。

　　再證(1)，它可看作是(2)、(3)的推廣。

　　因Lchild(j)=2j，所以Parent(2j)=j,令2j=i，有 Parent(i)=i/2= (i/2為正整數(shù));

　　又：Rchild(j)=2j+1，所以Parent(2j+1)=j，令2j+1=i (i=3,5,7…)，有:

　　Parent(i)=(i-1)/2= ，證畢。

　　n

　　2i

　　2i+1

　　1

　　2

　　3

　　2i+1+1

　　2i+1+2

　　i

　　i+1

　　例題：一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是( )【西安交通大學(xué) 1996 三、2 (3分)】

　　A. 250 B. 500 C.254 D.505 E.以上答案都不對(duì) 501

　　例題1：由二叉樹結(jié)點(diǎn)的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1， 因?yàn)閚=1001,所以1002=2n0+n1,在完全二叉樹樹中，n1只能取0或1,在本題中只能取0，故n=501，因此選E。

　　例題2：高度為K的完全二叉樹至少有_ __個(gè)葉子結(jié)點(diǎn)。(剛好第K上只有一個(gè)葉子時(shí)，高度為K，N= -1+1= 例題3：在順序存儲(chǔ)的二叉樹中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是

　　用順序存儲(chǔ)二叉樹時(shí)，要按完全二叉樹的形式存儲(chǔ)，非完全二叉樹存儲(chǔ)時(shí)，要加“虛結(jié)點(diǎn)”。設(shè)編號(hào)為i和j的結(jié)點(diǎn)在順序存儲(chǔ)中的下標(biāo)為s 和t ,則結(jié)點(diǎn)i和j在同一層上的條件是ëlog2sû=ëlog2tû。