导读
二叉树是一种很常见的数据结构，但要注意的是，二叉树并不是树的特殊情况，二叉树与树是两种不一样的数据结构。
目录
一、 二叉树的定义
二、二叉树为何不是特殊的树
三、二叉树的五种基本形态
四、二叉树相关术语
五、二叉树的主要性质（6个）
六、二叉树的存储结构（2种）
七、二叉树的遍历算法（4种）
八、二叉树的基本应用：二叉排序树、平衡二叉树、赫夫曼树及赫夫曼编码
一、二叉树的定义
如果你知道树的定义（有限个结点组成的具有层次关系的集合），那么就很好理解二叉树了。定义：二叉树是n(n≥0)个结点的有限集，二叉树是每个结点最多有两个子树的树结构，它由一个根结点及左子树和右子树组成。（这里的左子树和右子树也是二叉树）。
值得注意的是，二叉树和“度至多为2的有序树”几乎一样，但，二叉树不是树的特殊情形。具体分析如下
二、二叉树为何不是特殊的树
1、二叉树与无序树不同
二叉树的子树有左右之分，不能颠倒。无序树的子树无左右之分。
2、二叉树与有序树也不同（关键）
当有序树有两个子树时，确实可以看做一颗二叉树，但当只有一个子树时，就没有了左右之分，如图所示：
三、二叉树的五种基本状态
四、二叉树相关术语
满二叉树：所有叶子结点全部集中在最后一层，这样的二叉树称为满二叉树。（注意：国内的定义是每一层的结点都达到最大值时才算是满二叉树；而国际定义为，不存在度为1的结点，即结点的度要么为2要么为0，这样的二叉树就称为满二叉树。这两种概念完全不同，既然在国内，我们就默认第一种定义就好）。
完全二叉树：如果将一颗深度为K的二叉树按从上到下、从左到右的顺序进行编号，如果各结点的编号与深度为K的满二叉树相同位置的编号完全对应，那么这就是一颗完全二叉树。如图所示：
五、二叉树的主要性质
二叉树的性质是基于它的结构而得来的，这些性质不必死记，使用到再查询或者自己根据二叉树结构进行推理即可。
性质1：非空二叉树的叶子结点数等于双分支结点数加1。
证明：设二叉树的叶子结点数为X，单分支结点数为Y，双分支结点数为Z。则总结点数=X+Y+Z，总分支数=Y+2Z。
由于二叉树除了根结点外其他结点都有唯一的分支指向它，所以总分支数=总结点数-1.。
结合三个方程：总分支数=总结点数-1，即Y+2Z = X+Y+Z-1。化简得到X = Z + 1。即叶子结点数等于双分支结点数加1。
性质2：在二叉树的第i层上最多有2 i-1 个结点 （i>=1）。
证明：二叉树结点最多的情况即为满二叉树的情况，由于是满二叉树，每个结点都有两个孩子，所以下一层是上一层的2倍，构成了公比为2的等比数列，而第一层只有根结点，所以首项是1。所以二叉树的第i层上最多有2 i-1 个结点。
性质3：高度（或深度）为K的二叉树最多有2k - 1个结点(K>=1）。
证明：本性质其实就是性质2中描述的等比数列的前项和的问题。
性质4：若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：
(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
(2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；
(3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。
性质5：具有n个结点的完全二叉树的深度为[log2n]+1或者[log2(n+1)]，其中[log2n]+1是向下取整,[log2(n+1)]是向上取整。
性质6：Catalan函数性质：给定n个结点，能构成H(n)种结构不同的树。H(n) = c(2n,n) / (n+1)。
六、二叉树的存储结构
为了方便说明，我们使用下图树1作为案例树。
1、顺序存储
顺序存储是使用一个数组来存储二叉树，我们一般将二叉树按照性质4的做法，即从上到下且从左至右进行 1 至 n 的编号，然后编号与数组下标对应，按照编号依次将对应的结点信息存储数组中即可。
第一步：给二叉树编号：
注意，编号5的位置是没有结点的，但是我们这样编号的目的是为了更好的应用性质4，而性质4描述的是完全二叉树，所以我们编号时要将普通二叉树看做完全二叉树来进行编号，所以即使编号5即使没有结点也需要进行编号。
第二步：按编号存储到数组BTree[]中
第三步：按照性质4的规律取元素
性质4主要是描述结点的编号和双亲编号或孩子编号之间的数学关系，即我们知道了一个结点的编号，那么它的双亲编号和孩子孩子我们都能计算得到并从数组中取出来。
例如，结合性质4我们来计算编号3的双亲和孩子：选取出编号3即BTree[3]，就可以知道编号3的元素为C；双亲结点编号 = 3/2 = 1 ≥ 1，所以C结点的双亲为BTree[1]即A；左孩子编号 = 3*2 = 6 ≤ 7，所以C的右孩子为BTree[6] = E；右孩子编号 = 3*2+1 = 7 ≤ 7，所以C的右孩子为Btree[7] = F。
结论：像编号5这种情况会占用存储空间，所以这种存储方式最适合用于存储完全二叉树，而存储一般的二叉树则会浪费大量空间。
2、链式存储
根据二叉树的结构，我们使用下面的链式结点来存储一个二叉树结点。
所以树1对应的链式存储结构为：
七、二叉树的遍历算法
根据二叉树的结构特点：一般二叉树由左子树、根结点和右子树组成。这三个元素：左子树（L）、根结点（N）、右子树（R）有6种中排列组合，即NLR、LNR、LRN、NRL、RNL、RLN。而从左往右和从右往左这种遍历顺序是对称结构的，采用一种顺序即可，所以二叉树按照三个元素的排列顺序遍历就形成了：NLR（先序遍历）、LNR（中序遍历）和LRN（后序遍历）。
ps:二叉树的这三种遍历要用递归的思想去理解。
先序遍历（NLR）：根左右
1）访问根结点
2）先序遍历左子树
3）先序遍历右子树
中序遍历（LNR）：左根右
1）中序遍历左子树
2）访问根结点
3）中序遍历右子树
后序遍历（LRN）：左右根
1）后序遍历左子树
2）后序遍历右子树
3）访问根结点
java实现（遍历树1）：
1 package test; 2 3 import org.junit.Test; 4 5 /** 6 * 二叉树的遍历 7 * @author Fzz 8 * @date 2018年1月17日 9 * @Description TODO: 10 */ 11 public class BinaryTreeTraversal { 12 private StringBuffer sb = new StringBuffer(); 13 //先序遍历(数组) 14 public String first(Object[] o,int i){ 15 //访问根结点 16 sb.append(o[i]); 17 //遍历左子树 18 int left = i*2; 19 if(left<o.length&&o[left]!=null) 20 first(o,left); 21 //遍历右子树 22 int right = i*2+1; 23 if(right<o.length&&o[right]!=null) 24 first(o,right); 25 return sb.toString(); 26 } 27 28 //中序遍历 29 public String mid(Object[] o,int i){ 30 //遍历左子树 31 int left = i*2; 32 if(left<o.length&&o[left]!=null) 33 mid(o,left); 34 //访问根结点 35 sb.append(o[i]); 36 //遍历右子树 37 int right = i*2+1; 38 if(right<o.length&&o[right]!=null) 39 mid(o,right); 40 return sb.toString(); 41 } 42 43 //后序遍历 44 public String last(Object[] o,int i){ 45 //遍历左子树 46 int left = i*2; 47 if(left<o.length&&o[left]!=null) 48 last(o,left); 49 //遍历右子树 50 int right = i*2+1; 51 if(right<o.length&&o[right]!=null) 52 last(o,right); 53 //访问根结点 54 sb.append(o[i]); 55 return sb.toString(); 56 } 57 58 //将缓存区设为空 59 public void setBufferNull(){ 60 this.sb = this.sb.delete(0, sb.length()); 61 } 62 63 @Test 64 public void test(){ 65 Character[] o = {null,'A','B','C','D',null,'E','F'}; 66 //遍历前先清空缓存区 67 this.setBufferNull(); 68 String s = first(o,1); 69 System.out.println("先序遍历结果："+s); 70 this.setBufferNull(); 71 s = mid(o,1); 72 System.out.println("中序遍历结果："+s); 73 this.setBufferNull(); 74 s = last(o,1); 75 System.out.println("后序遍历结果："+s); 76 } 77 }
测试结果：
层次遍历
层次遍历比较简单，即按照从上往下、从左往右一层一层遍历即可。层次遍历是现实，如果遍历的是顺序存储（数组存储）的二叉树，由于存储的时候就是按照从上往下从左往右的顺序存储的，直接按顺序取出即可；如果是链式存储的二叉树，需要使用一个循环队列进行操作：先将根结点入队，当前结点是队头结点，将其出队并访问，如果当前结点的左结点不为空将左结点入队，如果当前结点的右结点不为空将其入队。所以出队顺序也是从左到右依次出队。
八、二叉树的基本应用
1、二叉排序树（Binary Sort Tree）
二叉排序树，又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
1、定义
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
1 BiTree* InsertBST(BiTree *t,int key) 2 { 3 if (t == NULL) 4 { 5 t = new BiTree(); 6 t->lchild = t->rchild = NULL; 7 t->data = key; 8 return t; 9 } 10 11 if (key < t->data) 12 t->lchild = InsertBST(t->lchild, key); 13 else 14 t->rchild = InsertBST(t->rchild, key); 15 16 return t; 17 }
-
若p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则可以 直接删除此子结点。
-
若p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点f的左子树（当p是左子树）或右子树（当p是右子树）即可，作此修改也不破坏二叉排序树的特性。
-
若p结点的左子树和右子树均不空。这种情况可以转换为情况1或2然后再按照1或2的方法来解决。有两种转换方法：其一是找到p结点的左子树的最右边的结点r（沿着p的左子树的根结点的右指针一直走，其实就是找到左子树的最大值），用r结点替换p结点，然后再删除r结点即可。其二是找到p结点的右子树的最左边的结点r（沿着p的右子树的根结点的左指针一直走，其实就是找到左子树的最小值），用r结点替换p结点，然后再删除r结点即可。
java实现：
private void deleteNode(BinarySortTree p) { //TODOAuto-generatedmethodstub if(p!=null) { //如果结点有左子树 /*1。若p有左子树，找到其左子树的最右边的叶子结点r，用该叶子结点r来替代p，把r的左孩子 作为r的父亲的右孩子。 2。若p没有左子树，直接用p的右孩子取代它。 */ if(p.lChild!=null) { BinarySortTree r=p.lChild; BinarySortTree prev=p.lChild; while(r.rChild!=null) { prev=r; r=r.rChild; } p.data=r.data; //若r不是p的左子树,p的左子树不变，r的左子树作为r的父结点的右孩子结点 if(prev!=r) { prev.rChild=r.lChild; } else { //若r是p的左子树，则p的左子树指向r的左子树 p.lChild=r.lChild; } } else { p=p.rChild; } } }
2、平衡二叉树
平衡二叉树又称为AVL树，是一种特殊的二叉排序树，即左右两个子树高度之差不超过1，并且左右两个子树都是平衡二叉树的二叉排序树称为平衡二叉树。
为什么要构造平衡二叉树呢？对于一般的二叉排序树，其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定。由于AVL树的左右子树高度之差不超过1，其高度一般都良好地维持在O（log（n）），大大降低了操作的时间复杂度。
平衡二叉树的实现算法：关键在于左右子树的平衡。具体的算法有：红黑树、AVL算法、Treap、伸展树、SBT来实现。有兴趣的可以自行搜索，这里就不再描述。
3、赫夫曼树及赫夫曼编码
赫夫曼树又叫做最优二叉树，特点是带权路径长度最短。
1、相关术语
