导读

　　二叉树是一种很常见的数据结构，但要注意的是，二叉树并不是树的特殊情况，二叉树与树是两种不一样的数据结构。

目录

　 　一、 二叉树的定义

　　二、二叉树为何不是特殊的树

　　三、二叉树的五种基本形态

　　四、二叉树相关术语

　　五、二叉树的主要性质（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的二叉树最多有2^k – 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个节点的完全二叉树的深度为[log₂n]+1或者[log_2(n+1)]，其中[log₂n]+1是向下取整,[log_2(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 }

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、相关术语