数据结构之树

树

树的遍历：都是依据根节点遍历的顺序来的，分为先序，中序，后序，然后先左节点，后右节点。
1：中序遍历：左根右（从左节点开始遍历，然后是根节点，然后是右节点，下同）
2：先序遍历：根左右
3：后序遍历：左右根

1：普通二叉树：每个节点最多有2颗子树。
a.满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。
b.完全二叉树：只有最下面的两层结点度能够小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

2：二叉查找树：对于树中的每个节点X，它的左子树中所有项的值小于X中的值，而它的右子树中所有项的值大于X中的值。（左值<根值<右值）。
时间复杂度：插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度（原因在于插入和删除元素的时候，树没有保持平衡）。

3：平衡二叉树之AVL树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1（层级差<=1），并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树，反之则不一定。
时间复杂度：插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。
注：平衡二叉树进行插入和删除操作时，为了维持平衡，会进行自平衡操作---旋转(左旋和右旋)。

4：平衡二叉树之红黑树：每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。
特点：
性质1：节点是红色或黑色。 
性质2：根是黑色。 
性质3：所有叶子都是黑色（叶子是NIL节点）。
性质4：每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。) 
性质5：从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
时间复杂度：可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。
注：红黑树存在左旋，右旋和着色问题。

5：B树(B-tree)：是一种用于查找的平衡树，但是它不是二叉树。
B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不止两个），即一个节点下不止有2个字节。
时间复杂度：O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除。
注：数据库索引技术里大量使用者B树和B+树的数据结构，文件系统也多是这个数据结构。

6：B+树和B*树的时间复杂度亦是如此。

详情见：http://blog.jobbole.com/111680/
强子博客：https://blog.51cloud.win/2017/12/16/%E6%A0%91%E4%B8%8E%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/