数据结构和算法（1）-- 二叉树
1、二叉树
1）满二叉树：
所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，这样就是满二叉树。
2）完全二叉树：
一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。
不是完全二叉树的情况：
在上图中，树1，按层次编号5结点没有左子树，有右子树，10结点缺失。树2由于3结点没有字数，是的6,7位置空挡了。树3中结点5没有子树。
3）平衡二叉树：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
4）二叉搜索树，也就是二叉查找树：
它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
二叉查找树的搜索过程（查找一下值为9的节点）：
（1）查看根节点9：
（2）由于10 > 9，因此查看右孩子13：
（3）由于10 < 13，因此查看左孩子11：
（4）由于10 < 11，因此查看左孩子10，发现10正是要查找的节点：
这种方式正是二分查找的思想，查找所需的最大次数等同于二叉查找树的高度。在插入接点的时候也是利用类似的方法，通过一层一层的比较大小，找到新节点适合插入的位置。
5）AVL树：第一个自平衡二叉搜索树
二叉查找树仍然存在它的缺陷，主要体现在插入新节点的时候：
假设初始的二叉查找树只有三个节点，根节点值为9，左孩子值为8，右孩子值为12：
接下来我们依次插入如下五个节点：7,6,5,4,3。依照二叉查找树的特性，结果会变成什么样呢？
这样的形态虽然也符合二叉查找树的特性，但是查找的性能大打折扣，几乎变成了线性。
这时候就需要自平衡二叉查找树。
AVL树本质上还是一棵二叉搜索树，它的特点是：
（1）本身首先是一棵二叉搜索树。
（2）带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
6）红黑树：也是自平衡二叉搜索树
为何有了AVL树还需要红黑树呢？红黑树没有AVL树那么的稳定，这换来的是红黑树比AVL数有更好的插入和删除效率，但是查找效率并没有比AVL差很多。
为什么插入和删除效率更高呢？因为红黑树的平衡条件没有AVL那么苛刻，插入和删除节点后平衡的调整相对简单。
平衡条件：能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍，如左子树为2，则右子树最多为4
（1）节点是红色或黑色。
（2）根节点是黑色。
（3）每个叶节点（NIL节点，空节点）是黑色的。
（4） 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
正是因为这些规则限制，才保证了红黑树的自平衡。红黑树从根到叶子的最长路径不会超过最短路径的2倍。
当插入或删除节点的时候，红黑树的规则有可能被打破，这时候就需要做出一些调整，来继续维持我们的规则。
红黑树详细内容：
7）B-树：
B-树是为实现高效的磁盘存取而设计的多叉平衡搜索树。这个概念在文件系统，数据库系统中非常重要。
下面来具体介绍一下B-树（Balance Tree），一个m阶的B树具有如下几个特征：
1.根结点至少有两个子女。
2.每个中间节点都包含k-1个元素和k个孩子，其中m/2 <= k <= m
3.每一个叶子节点都包含k-1个元素，其中m/2 <= k <= m
4.所有的叶子结点都位于同一层。
5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
B-树详细内容：
8）B+树：
B+树是B树的一种变形，由B-树和索引顺序访问方法演化而来，它更适合实际应用中操作系统的文件索引和数据库索引。
一个m阶的B+树具有如下几个特征：
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
B+树详细内容：
树的前序、中序、后序遍历过程。
