1、定义：

二叉树是计算机数据结构的一种，是树形结构的一个重要类型，它的每个节点最多有左右两个子树。往往二叉树的存储结构和算法都相对较为简单，一般的树形结构也可以转化为二叉树的形式，因此二叉树十分重要。

二叉树的两个子树，是不相交的，分别称为左子树和右子树，以及根节点root。当为空时，又称为空二叉树。

自然界中二叉树

2、二叉树的特殊形态

满二叉树：二叉树上只有度为0的节点或者度为2的节点，并且度为0的节点，都在同一层上。

满二叉树

完全二叉树：当且仅当二叉树节点与满二叉树编号一一对应的时候，称为完全二叉树。

有如下特点，叶子节点出现在层序最大的两层上，某个节点的左右分支下的子节点最大层序相等或者差1。

完全二叉树

3、二叉树的遍历

遍历是对树形结构的一种基本运算，即按照特定的顺序或者规则把二叉树中所有节点都访问一遍。因为二叉树不是线性结构，遍历的实质也就是把二叉树转化为线性结构来处理。

一棵非空的二叉树，都是由根节点、左节点、右节点三部分组成。执行遍历的时候，也是对这三部分操作，但是根据访问先后顺序的不一样，就分为前序遍历、中序遍历、后序遍历。

前序遍历：也叫先序遍历，先访问根节点，再访问左节点，最后访问右节点。

前序遍历

中序遍历：先访问左节点，再访问根节点，最后访问右节点。

中序遍历

后序遍历：先访问左节点，然后访问右节点，最后访问根节点。

后序遍历

还有一种遍历方式，层序遍历也会经常用到。

层序遍历

4、二叉树的特性

（1）在深度为k的二叉树中，最多有2^k-1个节点。

（2）在第k层中，该层最多有2^（k-1）个节点。

满二叉树还满足：

（1）满二叉树中不存在度为1的节点。

（2）具有n个节点的满二叉树深度为log2（n+1）

完全二叉树满足：

（1）当2*i>n（总结点个数），该节点i没有左孩子，否则其左孩子是节点2*i。

（2）当2*i+1>n，则该节点i没有右孩子，否则右孩子是节点2*i+1。