9.二叉树 
    9.1 二叉树的定义
    9.2 满二叉树与完全二叉树
    9.3 二叉查找树（也叫二叉搜索树，二叉排序树）
        9.3.1 定义
        9.3.2二叉查找树为什么需要平衡 ？
        9.3.3 二叉查找树的各种操作
    9.4 平衡二叉树（AVL树）
        9.4.1 定义
        9.4.2 前中后序遍历
        9.4.3 AVL树的平衡调整（LL,LR,RR,RL）
    9.5  哈夫曼树 （ 最优二叉树 ）
        9.5.1 哈夫曼编码
        9.5.2 介绍
        9.5.3 适用场景
    9.6 红黑树（后面开单章）
        9.6.1 简单介绍
        9.6.2 特点
        9.6.3 有了AVL树为什么还需要红黑树呢?
        9.6.4 红黑树应用场景

9.二叉树

    9.1 二叉树的定义

        在日常的应用中，我们讨论和用的更多的是树的其中一种结构：二叉树。

        ⼀棵树，如果它的每个节点最多只有两个子节点，那么他就是⼆叉树

    9.2 满二叉树与完全二叉树

    9.3 二叉查找树（也叫二叉搜索树，二叉排序树）

        9.3.1 定义

        如果我们给⼆叉树加⼀个额外的条件，就可以得到⼀种被称作二叉查找树的特殊⼆叉树

        ⼆叉查找树要求：
        （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
        （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
        （3）左、右子树也分别为二叉排序树；
        （4）没有键值相等的结点。

这就是二叉查找树

        9.3.2二叉查找树为什么需要平衡 ？

        当按顺序往二分搜索树中添加元素时，其会退化成链表。一棵只有左节点的二叉树，查找的时间复杂度会退化成O(n)(通常情况下为O(logN))，所以二叉树需要平衡。

        9.3.3 二叉查找树的各种操作：

        查询：先取根节点，如果根节点等我们要查找的数据，那么直接返回。如果要查找的数据比根节点的值小，那么就在左子树中递归查找。如果要查找的数据比根节点的值大，那么就在右子树中递归查找。最⼩值位于其最左节点上；最⼤值位于其最右节点上

        插入：类似于查找操作。先从根节点开始，依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

        删除：删除的情况分为很3种：
        1.要删除的节点没有子节点：只需要把父节点中指向要删除节点的指针置为null即可
        2.要删除的节点只有1个子节点：只需要把父节点中指向要删除节点的指针改为指向要删除节点的子节点即可
        3.要删除的节点有2个子节点：找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。最后再删除掉这个最小节点（实际上就是用要删除节点的前驱节点顶替    前驱节点：中序遍历下该节点的上一个节点    后继节点：中序遍历下该节点的下一个节点）

    9.4 平衡二叉树（AVL树）

        9.4.1 定义

        一棵AVL树必须满足如下条件：

            条件一：它必须是二叉查找树。

            条件二：每个节点的左子树和右子树的高度差至多为1（这个高度差就是平衡因子）

        9.4.2 前中后序遍历

        9.4.3 AVL树的平衡调整（LL,LR,RR,RL）

        AVL树为了维持自身平衡性，在插入元素时，计算了每个节点的平衡因子是否大于1，如果大于，那么就将进行相应的旋转操作以维持平衡性。

        失衡结点：插入元素后，以插入的元素为起点，向上追溯找到的第一个平衡因子大于1的节点就是失衡结点

        平衡的调整共有四种情况：分别为LL,LR,RR,RL。

        （1）LR型：插入元素在不平衡节点的左侧的右侧

        简单说明：最开始插⼊数据16，3，7后的结构如上图所示，结点16失去了平衡，3为16的左孩⼦，7为失衡结点的左孩⼦的右孩⼦，所以为LR型，接下来通过两次旋转操作复衡，先通过以3为旋转中⼼，进⾏左旋转，结果如图所示，然后再以7为旋转中⼼进⾏右旋转，旋转后恢复平衡了。

        （2）LL型：插入元素在不平衡节点的左侧的左侧

        简单说明：在上⾯恢复平衡后我们再次插⼊数据11和9,发现⼜失去平衡了，这次失衡结点是16，11是其左孩⼦，9为其失衡结点的左孩⼦的左孩⼦，所以是LL型，以失衡结点的左孩⼦为旋转中⼼进⾏⼀次右旋转即可

右旋转代码

            注意这里的高度是指从该节点到叶子节点（没有子节点的节点）的最长简单路径边的条数

            （3）RR型：插入元素在不平衡节点的右侧的右侧

        简单说明：进⼀步插⼊数据26后⼜再次失衡了，失衡结点为7,很明显这是RR型，以失衡结点的右孩⼦为旋转中⼼左旋转⼀次即可

左旋转代码

        再插⼊18后⼜再次失衡了，失衡结点为16，26为其右孩⼦，18为其右孩⼦的左孩⼦，为RL型，以失衡结点的右孩⼦为旋转中⼼，进⾏⼀次右旋转，然后再次已失衡结点的右孩⼦为旋转中⼼进⾏⼀次左旋转变恢复了平衡。

            （4）RL型

        再插⼊18后⼜再次失衡了，失衡结点为16，26为其右孩⼦，18为其右孩⼦的左孩⼦，为RL型，以失衡结点的右孩⼦为旋转中⼼，进⾏⼀次右旋转，然后再次已失衡结点的右孩⼦为旋转中⼼进⾏⼀次左旋转变恢复了平衡。

    9.5 哈夫曼树 （最优二叉树）

        9.5.1 哈夫曼编码

        比如我们要传输一个长度为10的字符串，使用如下编码需要30个bit位才能表示10个字符       

        但是如果使用 哈夫曼编码 就只需要25位。（经常出现的字母，编码长度小；不经常出现字母，编码长度大）

        9.5.2 介绍

        哈夫曼树是⼀种特殊的⼆叉树又称为最优二叉树。指在具有相同节点的树中，加权路径长度(WPL)最小的二叉树。

        9.5.3 适用场景

        1. 霍夫曼树应⽤于信息编码和数据压缩领域
        2. 霍夫曼树是现代压缩算法的基础

    9.6 红黑树

        9.6.1 简单介绍

        红黑树后面单独开一篇博客讲，这里简单的介绍下：

        首先红黑树也是一个二叉查找树，它也有所谓的平衡性。某种意义上讲红黑树就是一个要求不太严格的平衡二叉树。它具备以下特点：

        9.6.2 特点

            1. 每个节点非红即黑
            2. 根节点是黑的;
            3. 每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的;
            4. 如图所示，如果一个节点是红的，那么它的两儿子都是黑的;
            5. 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点;
            6. 每条路径都包含相同的黑节点;

        9.6.3 有了AVL树为什么还需要红黑树呢?

        平衡树是为了解决二叉查找树退化为链表的情况，而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。（换句话说就是因为平衡二叉树要求太严格了，平衡因子为1，操作时需要频繁的左右旋转重新调整结构。红黑树算是一个折中处理吧）

        9.6.4 红黑树应用场景

        java中的TreeSet,TreeMap，广泛用在C++的STL中。如map和set都是用红黑树实现的