特殊二叉树和二叉树的性质

特殊二叉树

一：斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。
左斜树：

右斜树：

二：满二叉树

在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树的特点有：
1）叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
2）非叶子结点的度一定是2。
3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
满二叉树：

三： 完全二叉树

完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

注意：满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满二叉树。

其次，完全二叉树的所有结点与同样深度的满二叉树，它们按层序编号相同的结点，是一 一对应的。下图中浅色部分表示结点不存在，可以看出，树1的第10个结点编号空档了。同理，树2的6、7，树3的10、11编号空档了，它们编号不连续，都不是完全二叉树。

特点：
1）叶子结点只能出现在最下层和次下层。
2）最下层的叶子结点集中在树的左部。
3）倒数第二层若存在叶子结点，一定在右部连续位置。
4）如果结点度为1，则该结点只有左孩子，即没有右子树。
5）同样结点数目的二叉树，完全二叉树深度最小。

二叉树的性质

性质1：在二叉树的第i层上至多有2^i-1个结点（i>=1)。

性质2：深度为k的二叉树至多有2^k-1个结点（k>=1)。
注意这里是2^k后再减去1。

性质3：对任何一颗二叉树T，如果其终端结点数为n₀，度为2的结点数为n₂，则n₀=n₂+1。
推导过程：对任何一颗二叉树而言，它的分支边数是结点数-1，因为除了根节点没有分支进来，其他结点都有，一个分支连接了一个结点。所以对于二叉树来说，假设度为0的结点数为n₀，度为1的结点数为n₁，度为2的结点数为n₂，
有n₀+n₁+n₂-1=0 * n₀+1 * n₁+2 * n₂，得出n₀=n₂+1。

性质4：具有n个结点的完全二叉树的深度为[log₂n]+1 ([X]表示不大于x的最大整数）。
推导过程：对于k层二叉树，如果是满二叉树的话，则有2^k-1个结点，而完全二叉树一定少于等于同样深度的满二叉树。则有
2^k-1-1<n<2^k-1，由于n是整数，则有2^k-1<=n<2^k，两边取对数，得到k-1<=log₂n<k，因此k=[log₂n]+1。

性质5：如果对一棵有 n 个结点的完全二叉树（其深度为 ⌊log₂n⌋+1）的结点按层序编号（从第 1 层到第 ⌊log₂n⌋+1 层，每层从左到右），对任一结点 i（1≤i≤n） 有：

1. 如果 i=1，则结点 i 是二叉树的根，无双亲；如果 i>1，则其双亲是结点 ⌊i/2⌋。
2. 如果 2i>n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i。
3. 如果 2i+1>n，则结点 i 无右孩子；否则其右孩子是结点 2i+1。