以下是应届毕业生网为大家整理好的范文，希望对大家有所帮助！如有疑问请关注本网站！
证明：采用数学归纳法，先证(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û。