常用公式

（1）非空二叉树叶子结点数 = 度为2的结点数 + 1 即，N0=N2+1

（2）非空二叉树上第K层至多有2k−1 个结点（K≥1）

（3）高度为H的二叉树至多有2H−1 个结点（H≥1）

（4）具有N个（N>0）结点的完全二叉树的高度为 ⌈log2(N+1)⌉ 或 ⌊log2N⌋+1

（5）对完全二叉树按从上到下、从左到右的顺序依次编号1,2，...，N，则有以下关系：

① 当 i>1 时，结点 i 的双亲结点编号为 ⌊i/2⌋ ，即当 i 为偶数时，其双亲结点的编号为 i/2 ，它是双亲结点的左孩子；当 i 为奇数时，其双亲结点的编号为 (i−1)/2 ，它是双亲结点的右孩子。

② 当 2i≤N 时，结点i的左孩子编号为 2i ，否则无左孩子。

③ 当 2i+1≤N 时，结点i的右孩子编号为 2i+1 ，否则无右孩子。

④ 结点 i 所在层次（深度）为 ⌊log2i⌋+1 。（设根结点为第1层）

408考研-2011-4  若一棵完全二叉树有768个结点，则二叉树中叶结点的个数是_____。
A.257            B.258            C.384            D.385

解：

根据完全二叉树的性质，最后一个分支结点的序号为 ⌊n/2⌋=⌊768/2⌋=384 ，故叶子结点的个数为 768−384=384