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

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

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

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

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

　　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個結(jié)點，其中葉子結(jié)點的個數(shù)是( )【西安交通大學(xué) 1996 三、2 (3分)】

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

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

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

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