以下是應屆畢業生網為大家整理好的范文，希望對大家有所幫助！如有疑問請關注本網站！
證明：采用數學歸納法，先證(2)和(3)。
設n個結點的完全二叉樹如圖所示。
i=1時,顯然 i 結點的左子編號為2，i的右子編號為2+1=3，除非2>n , 3>n 。
設對i結點，命題(2)、(3)成立，即Lchild(i)=2i，Rchild(i)=2i+1。根據按層編號規則，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為正整數);
又：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個結點，其中葉子結點的個數是( )【西安交通大學 1996 三、2 (3分)】
A. 250 B. 500 C.254 D.505 E.以上答案都不對 501
例題1：由二叉樹結點的公式：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的完全二叉樹至少有_ __個葉子結點。(剛好第K上只有一個葉子時，高度為K，N= -1+1= 例題3：在順序存儲的二叉樹中，編號為i和j的兩個結點處在同一層的條件是
用順序存儲二叉樹時，要按完全二叉樹的形式存儲，非完全二叉樹存儲時，要加“虛結點”。設編號為i和j的結點在順序存儲中的下標為s 和t ,則結點i和j在同一層上的條件是ëlog2sû=ëlog2tû。