1、基本概念
二叉树（Binary Tree）是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。
二叉树的特点：
二叉树不存在度大于2的结点。
二叉树的子树有左右之分，次序不能颠倒。
如下图中，树1和树2是同一棵树，但它们是不同的二叉树。
二叉树
1）、斜树
所有的结点都只有左子树的二叉树叫左斜树。所有的结点都只有右子树的二叉树叫右斜树。这两者统称为斜树。
斜树每一层只有一个结点，结点的个数与二叉树的深度相同。其实斜树就是线性表结构。
2）、满二叉树
在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
满二叉树具有如下特点：
叶子只能出现在最下一层
非叶子结点的度一定是2
同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
3）、完全二叉树
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
完全二叉树的特点：
叶子结点只能出现在最下两层
最下层叶子在左部并且连续
同样结点数的二叉树，完全二叉树的深度最小
4）、平衡二叉树
平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
2、二叉树的性质
在二叉树的第i层上至多有2^i-1^个结点（i>=1）。
深度为k的二叉树至多有2^k^-1个结点（k>=1）。
对任何一棵二叉树T，如果其终端结点个数为n~0~，度为2的结点数为n~2~，则n~0~ = n~2~ + 1。
具有n个结点的完全二叉树的深度为「log~2~n」+ 1（「x」表示不大于x的最大整数）。
如果对一棵有n个结点的完全二叉树的结点按层序编号（从第一层到第「log~2~n」+ 1层，每层从左到右），对任一结点i（1≤i≤n）有：
若i=1，则结点i是二叉树的根，无双亲；如i>1，则其双亲是结点「i/2」。
如2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
若2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。
3、二叉树的存储结构和遍历
二叉树是一种特殊的树，它的存储结构相对于前面谈到的一般树的存储结构要简单一些。
①顺序存储结构
②链式存储结构
