一.什么是树
     是一种数据结构，可以用来表示层次关系，因表示的样子很像一颗倒立的树而得名。在数据结构中的特点，是一对多（链表是一对一，图是多对多）

    对树而言，先了解以下基本概念：

                                        1

                                     /      \

                                  2         3

                                /    \      /   

                              4     5   6     

        1、每棵树都有一个“根”，这是树的“根基”，称为root，通过root我们可以很容易的找到树上的各个支点，上图中“1”为树的root；

        2、一棵树上的每个节点，它们有可能有分支，有可能没有分支，分支的数目称为分支因子。如上图中，最大的分支结因子为2，"3"结点的分支因子为1

        3、每棵树都有一个高度，数据的层次数就是树的高度，上图中树的高度为3。

        4、通用概念：

             1与2,3之间的关系为：1是父，2是其左孩子，3是其右孩子。2与3相互之间称为兄弟。 没有孩子的结点称为叶子结点，如4\5\6结点。

二.什么是二叉树

    二叉树是一种特殊的顺序树，它规定有左右两个孩子，即左右孩子顺序不能替换，所以二叉树是一种有序树。二叉树的结点数为大于0小于等于2。三.二叉树的遍历

   简单二叉树遍历，可分为：先序，中序，后序。在此分别总结先序，中序，后序的结点输出顺序。

  先序： 1.访问根结点

　　　　2.访问左子树

　　　　3.访问右子树

  先序较简单，不予以即系解释。

  中序：1.访问左子树

　　　  2.访问根结点

　　     3.访问右子树

　　　　原则：访问左子树。【先访问左子树中的左子树，再访问左子树中的右子树。】直到访问到叶子结点后输出。输出根。访问右子树。【先访问右子树中的左子树，再访问右子树中的右子树。】直到访问到叶子结点后输出。

    具体步骤如下：A作为根。从A开始，先访问A的左子树。即

    在看B的左子树，D。则输出D。B无左子树。访问完B的左子树。然后访问B。输出B。再看B的右子树。F有左子树E，则输出E。返回输出F。A的左子树全部输出完，再返回A，输出A。

    同理，看A的右子树。 输出顺序为G,H,C,I。

    所以，中序遍历输出的结果为：（D B E F）A（G H C I）.

  后序：1.访问左子树

　　　  2.访问右子树

          3.访问根

　　　 原则：访问左子树。【先访问左子树中的左子树，再访问左子树中的右子树】。直到访问到叶子结点后输出。访问右子树。【先访问右子树中的左子树，再访问右子树中的右子树】。直到访问到叶子结点后输出。再返回访问根，并输出。

具体步骤：

  先访问A的左子树。再访问左子树中的左子树。【即：A的左子树为B，再访问B的左子树D。D没有左右子树，输出D。】，然后访问左子树中的右子树。【即：访问B的右子树F，F还有左子树，再访问F的左子树E，E没有左右子树。输出E。再输出F，再输出B。】。

  然后访问A的右子树。再访问右子树中的左子树。【即：A的右子树为C，再访问C的左子树G。G还有右子树H，输出H。再输出G，再输出G】，然后访问右子树中的右子树。【即：访问C的右子树I，I没有左右子树，输出I。在输出C。再输出A。】。

  所以，后序遍历输出结果为：（D E F B）（H G I C）A

四.常见的几种二叉树
1.二叉搜索树:
    如果我们给二叉树加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。二叉搜索树要求：每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大。如

    BST(二叉搜索树)树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；

    如果BST树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变BST树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；如:

    但BST树在经过多次插入与删除后，有可能导致不同的结构：

    右边也是一个BST树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的树结构索引；所以，使用BST树还要考虑尽可能让BST树保持左图的结构，和避免右图的结构，也就是所谓的“平衡”问题；

2.AVL平衡二叉搜索树
    定义：平衡二叉树或为空树,或为如下性质的二叉排序树:
      （1）左右子树深度之差的绝对值不超过1;
      （2）左右子树仍然为平衡二叉树.
    平衡因子BF=左子树深度－右子树深度.
    平衡二叉树每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则该二叉排序树就是不平衡的。

3.RBT 红黑树

    红黑树主要有两个特征：1.节点都有颜色；2.在插入和删除的过程中，要遵循保持这些颜色的不同排列的规则。首先第一个特征很好解决，在节点类中店家一个数据字段，例如boolean型变量，以此来表示节点的颜色信息。第二个特征比较复杂，红-黑树有它的几个规则，如果遵循这些规则，那么树就是平衡的。红-黑树的主要规则如下：

        1.每个节点不是红色就是黑色的；

        2.根节点总是黑色的；

        3.如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；

        4.从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。   

    下图所示，即是一颗红黑树：

4.B-树

       是一种平衡多路搜索树（并不是二叉的）：

       1.定义任意非叶子结点最多只有M个儿子；且M>2；

       2.根结点的儿子数为[2, M]；

       3.除根结点以外的非叶子结点的儿子数为[M/2, M]；

       4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

       5.非叶子结点的关键字个数=指向儿子的指针个数-1；

       6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K < K[i+1]；

7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P指向关键字属于(K[i-1], K)的子树；

       8.所有叶子结点位于同一层；

       如：（M=3）

B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

    B-树的特性：

       1.关键字集合分布在整颗树中；

       2.任何一个关键字出现且只出现在一个结点中；

       3.搜索有可能在非叶子结点结束；

       4.其搜索性能等价于在关键字全集内做一次二分查找；

       5.自动层次控制；

       由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为：

  其中，M为设定的非叶子结点最多子树个数，N为关键字总数；所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并.

5.B+树

       B+树是B-树的变体，也是一种多路搜索树：

       1.其定义基本与B-树同，除了：

       2.非叶子结点的子树指针与关键字个数相同；

       3.非叶子结点的子树指针P，指向关键字值属于[K, K[i+1])的子树（B-树是开区间）；

       5.为所有叶子结点增加一个链指针；

       6.所有关键字都在叶子结点出现；

       如：（M=3）

    B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

    B+的特性：

       1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

       2.不可能在非叶子结点命中；

       3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

       4.更适合文件索引系统；比如对已经建立索引的数据库记录，查找10<=id<=20，那么只要通过根节点搜索到id=10的叶节点，之后只要根据叶节点的链表找到第一个大于20的就行了，比B-树在查找10到20内的每一个时每次都从根节点出发查找提高了不少效率。

我来占层楼啊