二叉树是每个结点最多有两个子树的有序树。二叉树的定义也是递归的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：（1）空二叉树；（2）只有一个根结点；（3）只有左子树；（4）只有右子树；（5）左右子树都存在。

完全二叉树的特点是：

（1）所有的叶结点都出现在第k层或k－1层。

（2）对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L＋1。

二叉树的性质

性质1：二叉树的第i层结点数最多为2^i-1个。用数学归纳法可以证明（略）。

性质2： 深度为k的二叉树结点总数最多为2^k-1个。

由性质1可知，二叉树中第i层结点数最多为2^i-1个，那么深度为k的二叉树总结点数为2⁰+2¹+…+2 ^k-1，即2^k-1。

性质3：在任意一棵二叉树中，若叶子结点的个数为n0，度为2的结点个数为n2，则n0=n2+1。

证明：因为二叉树中所有结点的度数均不大于2，所以结点总数n等于度为0结点数n0、度为1的结点数n1和度为2的结点数n2之和：n=n0+n1+n2 (式子1)。

又因为度为1的结点有一个孩子，度为2的结点有两个孩子，所以二叉树中孩子结点总数是： nl+2n2。

另外，只有根结点不是任何结点的孩子，所以二叉树中的结点总数又可表示为：n=n1+2n2+1 (式子2)。

由式子1和式子2得到： n0=n2+1

性质4：具有n个结点的完全二叉树的深度为 K = 。

证明：假设深度为K，则根据性质2 和完全二叉树的定义有：

              2^k-1- 1 ＜ n ≤ 2^k -1    或     2 ^k-1 ≤ n ＜ 2^k

于是K-1 ≤ log₂n<K ，因为 K是整数，所以 K =。

性质5：如果完全二叉树有n个结点，则对任意结点i（1≤i≤n），有：

（1）若i>1，则i的双亲是；若i＝1则i是根结点无双亲；

（2）若2i≤n，则i的左孩子是2i；若2i>n则i无左孩子；

（3）若2i+1≤n，则i的右孩子2i+1；若2i+1>n，则i无右孩子。