二叉树
特点
二叉树特点是，根节点有俩孩子，左小右大（左<根/中<右）
查找比线性链表或数组快
极端情况变链表
但是有一种极端情况，会退化成一个链表：数据从小到大或从大到小，比如：
1 2 3 4 5 6 7 放入二叉树
二叉树的遍历
组装一棵二叉树如下：
- 前序遍历（中->左子->右子，根节点M在前面）
结果：
M，G，D，B，A，C，F，E，J，H，I，K，L，S，P，O，N，Q，R，W，U，T，V，X，Z，Y - 后续遍历（左子->右子->中，根节点M在最后）
结果：
A，C，B，E，F，D，I，H，L，K，J，G，N，O，R，Q，P，T，V，U，Y，Z，X，W，S，M - 中序遍历（左子->中->右子，根节点M在中间）
结果：
A，B，C，D，E，F，G，H，I，J，K，L，M，N，O，P，Q，R，S，T，U，V，W，X，Y，Z
平衡二叉树
为了避免出现链表或者子节点数据量不一致问题，又出现了平衡（AVL）二叉树。
平衡二叉树，当左右子节点树高差大于1时，通过左旋或右旋来保持整颗树的平衡
比如 1 2 3 4 5 6 7 放入平衡二叉树
特点：
- 非叶子节点最多拥有两个子节点
- 非叶子节点值大于左边子节点、小于右边子节点
- 树的左右两边的层级数相差不会大于1
- 没有值相等重复的节点
红黑树
因为平衡二叉树每次加入数据，为了保持整棵树的平衡，要做大量的节点旋转移动，所以又出现了红黑树
红黑树特点
- 每个节点或者是黑色，或者是红色
- 根节点是黑色
- 每个叶子节点(NIL)是黑色
- 如果一个节点是红色的，则它的子节点必须是黑色的
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点
B树
WIP