一、树 Tree

二、二叉树 Binary Tree

二叉树遍历原理

二叉树的遍历是指从根节点出发，按照某种次序依次访问二叉树中所有节点，使得每个节点被访问一次且仅被访问一次。

二叉树的遍历方式可以很多，如果我们限制了从左到右的习惯方式，那么主要就分为4中：

1、前序遍历

先访问根节点，然后前序遍历左子树，再前序遍历右子树。

2、中序遍历

从根节点开始(注意不是先访问根节点)，中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树。

三、二叉查找树

二叉查找树，英文binary search tree，简称BST，查找一个节点所需的最大次数等于二叉查找树的高度。

二叉查找树有一个根节点(root)，比根节点小的放到根节点的左侧，变成根节点的左子节点(left)，大于等于根节点的放到根节点的右侧，变成根节点的右子节点(right)。如此，新元素通过与已有节点不断比较，从而找到自己的位置。

二叉查找树有一个很大的缺陷就是，假如新添加的元素是越来越大的或者越来越小的，则二叉查找树就会侧重一边，这时查找性能严重下降(侧重一边相对于左右平衡，查找元素时会多一倍的性能消耗)。

红黑树，英文red black tree，是一种自平衡的二叉查找树。

红黑树除了符合二叉查找树的基本特性外，还有自己的5个特性：

1、每个节点颜色，要么是黑色，要么是红色

2、根节点是黑色

3、叶子节点是黑色的空节点(nil节点)

4、红色节点的子节点都是黑色

5、对每一个节点来说，从这个节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。

红黑树会通过三种方式对平衡进行修正，变色、左旋、右旋。

如果一个红黑树向右倾斜，就左旋，反之，就右旋。

左旋动图：

右旋动图：

用语言真是不可描述。

多路查找树

多路查找树，其每一个节点的孩子数可以多于两个，且每一个节点处可以存储多个元素。

有4中特殊形式：2-3树、2-3-4树、B树和B+树。

2-3树