Pre-order/In-order/Post-order
1. 前序(Pre-order)：根-左-右
2. 中序(In-order)：左-根-右 （如果一棵树是二叉搜索树，它的中序是有序的）
3. 后序(Post-order)：左-右-根
3. 二叉搜索树 Binary Search Tree树和链表没有本质的区别，当一个链表分出两个next时就把它称为树，从一维空间扩展为二维空间了。
这种扩展的好处：引入了二叉搜索树，当它本身是有序的话可以根据它和当前结点的大小关系分出来它只走左分支还是右分支（它的查询、插入和搜索的效率就是从O(n)变成Log(2n)的时间复杂度 ）。
二叉搜索树，也称二叉搜索树、有序二叉树（Ordered Binary Tree）、 排序二叉树（Sorted Binary Tree），
是指一棵空树或者具有下列性质的二叉树：
1. 左子树上所有结点的值均小于它的根结点的值；
2. 右子树上所有结点的值均大于它的根结点的值；
3. 以此类推：左、右子树也分别为二叉查找树。 （这就是 重复性！）
二叉搜索树的中序遍历是：升序排列
二叉搜索树的查找、插入、删除等操作二叉搜索树即二叉查找树是最常用的一种二叉树，它支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度是 O(logn) 。
不过，二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于 log2n 的情况，从而导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间复杂度会退化到 O(n)。
要解决这个复杂度退化的问题，需要设计一种平衡二叉查找树。
它的时间复杂度为Log(2n)，n为它的结点个数。
极端情况下，一直插入到左边，二叉搜索树就退化成了链表，就类似于链表的查询时间复杂度了。
保证性能的关键
1. 保证二维维度！ —> 左右子树结点平衡（recursively）
2. Balanced
二叉查找树是常用的一种二叉树，它支持快 速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度 是 O(logn)。
不过，二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于 log n 的情况，从而 导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间复杂度会退化到 O(n)。要解决这个复杂度退化
的问题，我们需要设计一种平衡二叉查找树。
但凡讲到平衡二叉查找树，就会拿红黑树作为例子。在工程中，很多用到平衡二叉查找树的地方都会用红黑树。 为什么工程中都喜欢用红黑树，而不是其他平衡二叉查找树呢？
平衡二叉树定义：二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看，完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。
平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。
最先被发明的平衡二叉查找树是AVL 树，它严格符合平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过 1，是一种高度平衡的二叉查找树。
但很多平衡二叉查找树其实并没有严格符合上面的定义（树中任意一个节点的左右子树的高度相差不能大于 1），比如红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。
对于平衡二叉查找树这个概念，从他的由来，去理解“平衡”的意思。发明平衡二叉查找树这类数据结构的初衷是解决普通二叉查找树在频繁的插入、删除等动态更 新的情况下，出现时间复杂度退化的问题。