【二叉树的定义】

二叉树（ binary tree）是 $n(n \geq 0)$ 个结点的有限集合，$n=0$ 时为空二叉树

对于非空二叉树，有：

二叉树具有以下特点：

二叉树存在以下五种基本形态

【特殊二叉树】

所有的结点都只有左子树的二叉树称为左斜树，所有的结点都只有右子树的二叉树称为右斜树

在斜树中，每层只有一个结点，因此斜树的结点个数与其深度相同

在一棵二叉树中，若所有的分支结点都存在左子树和右子树，且所有的叶子都在同一层上，则称为满二叉树

满二叉树具有以下特点：

由于满二叉树的特性可知：满二叉树在同样深度的二叉树中结点个数、叶结点个数最多

从根结点起，对满二叉树自上而下，自左到右进行编号，这称为层序编号，对于编号为 $i$ 的结点，双亲编号为 $\left\lfloor \frac{i}{2} \right\rfloor$，左孩子编号为 $2i$，右孩子编号为 $2i+1$

对一棵具 $n$ 个结点的二叉树按层序编号，若编号为 $i$ 的结点与同样深度的满二叉树中编号 $i$ 的结点在二叉树中的位置完全相同，则称为完全二叉树，那么显然有：满二叉树是完全二叉树

完全二叉树具有以下特点：

叶结点只能出现在最下两层，且最下层的叶结点都集中在二叉树左侧连续的位置
若有度为 $1$ 的结点，只可能有一个，且其只有左孩子
深度为 $k$ 的完全二叉树在 $k -1$ 层上一定是满二叉树
对于具有 $n$ 个结点的完全二叉树，当第 $i$ 个结点满足 $i \leq \left\lfloor \frac{n}{2} \right\rfloor$ 时为分支结点，当 $i > \left\lfloor \frac{n}{2} \right\rfloor$ 时为叶结点

简单来说，在满二叉树中，从最后一个结点开始，连续去掉任意个的结点，即是一棵完全二叉树

除斜树、完全二叉树、满二叉树外，还有具有其他特点的二叉树，常见的有：

二叉树具有以下性质：

1.二叉树的第 $i$ 层上最多有 $2^{i-1},i\geq1$ 个结点

2.在一棵高度为 $h$ 的二叉树中，最多有 $2^h-1$ 个结点，最少有 $h$ 个结点

推论：高度为 $h$ 且具 $2^h-1$ 个结点的二叉树一定是满二叉树，但深度为 $h$ 具有 $h$ 个结点的二叉树不一定是斜树

3.具有 $n$ 个结点的二叉树，其分支数（边）：$B=n-1$，对于任意一个结点，每度贡献一个分支，即：度为 $0$ 的结点贡献 $0$ 个分支，度为 $1$ 的结点贡献 $1$ 个分支，度为 $2$ 的结点贡献 $2$ 个分支

4.在一棵二叉树中，若叶结点个数为 $n_0$，度为 $2$ 结点个数为 $n_2$，那么有：$n_0=n_2+1$

5.具有 $n$ 个结点的完全二叉树的高度为 $\left\lfloor log_2(n+1) \right\rfloor$ 或 $\left\lfloor log_2n \right\rfloor +1 $

6.具有 $n$ 个结点的完全二叉树，可由结点数推出度为 $0,1,2$ 的结点个数 $n_0,n_1,n_2$

7.对一棵具有 $n$ 个结点的完全二叉树，从 $1$ 开始按层序编号，则对于任意编号 $i$ 的结点，有：

若 $i=1$，则结点 $i$ 为根结点；若 $i>1$，则结点 $i$ 的父结点编号为 $\left\lfloor \frac{i}{2} \right\rfloor$
若 $i>\left\lfloor \frac{i}{2} \right\rfloor$ 则结点 $i$ 为叶结点，若 $i \leq \left\lfloor \frac{i}{2} \right\rfloor$ 则结点 $i$ 为分支结点
若 $2i\leq n$，则：结点 $i$ 的左孩子编号为 $2i$；若 $2i>n$，则结点 $i$ 无左孩子
若 $2i+1 \leq n$，则：结点 $i$ 的右孩子编号为 $2i+1$；若 $2i+1>n$，则结点 $i$ 无右孩子
结点 $i$ 的层次为 $\left\lfloor log_2(n+1) \right\rfloor$ 或 $\left\lfloor log_2n \right\rfloor +1 $