前言

下图是一个很经典的算法叫做折半查找法：

对于在每个阶段都是两种结果的情况时，比如开和关，0和1，真和假，对和错，正面和反面等等，都适合用树状结构来建模，而这种树其实是一种很特殊的树，叫做二叉树。

定义

二叉树时n个结点的有限集合，该集合或者为空集（空集成为空二叉树），或者由一个根节点和两棵互不相交的，分别称为根节点的左子树和右子树的二叉树组成。

特点

二叉树的特点：
一.每个结点最多有两棵子树
二.左子树和右子树是有顺序的，次序不能任意颠倒
三.即使树中只有一棵子树，也要区分它是左子树还是右子树。例如下图中，树1和树2是同一棵树，但它们却是不同的二叉树

分类

斜树

顾名思义，就是树是斜的。
定义：
“所有结点都只有左子树的二叉树叫做左斜树
所有结点都只有右子树的二叉树叫做右斜树，这两者统称为斜树。
特点：每一层都只有一个结点，结点的个数和二叉树的深度相同。
线性表的结构可以理解为树的一种极其特殊的表现形式（斜树）

满二叉树

满二叉树其实就是完美的二叉树
定义：
在一棵二叉树中，所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树
特点：
一.叶子结点只能存在于最下层且所有叶子结点处在同一层
二.非叶子结点的度一定为2
三.在同样深度的二叉树中，满二叉树的结点个数最多，叶子结点也是最多

完全二叉树

完全二叉树是重点也是理解难点
定义：
对一棵具有n个结点的二叉树按层序编号（层数由上至下，每一层从左至右编号每个结点），如果序号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，所有结点都满足这个要求的二叉树则称为完全二叉树。
注意：一定要区别满二叉树和完全二叉树，满二叉树一定是一棵完全二叉树，完全二叉树不一定是满二叉树。

案例：

图一是满二叉树
图二和图四不是完全二叉树，因为存在个别对应结点的序号不一样
图三是完全二叉树，因为图三中所有结点的序号和图一中所有序号一一对应

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