一. 二叉树
二叉树binary tree是指每个节点最多含有两个子树的树结构。
特点：
1.所有节点最多拥有两个子节点，即度不大于2
2.左子树的键值小于根的键值，右子树的键值大于根的键值。
遍历
二叉树的遍历有三种方式 (简记：把根放哪)
（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。
（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。
（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。
image.png
比如上图二叉树遍历结果
前序遍历：ABCDEFGHK
中序遍历：BDCAEHGKF
后序遍历：DCBHKGFEA
二. 平衡二叉树
1.符合二叉树的条件下
2.任何节点的两个子树的高度最大差为1
如果在avl 树，中进行插入和删除节点操作，可能导致avl树失去平衡，那么可以通过旋转重新达到平衡。因此我们说的二叉树也称自平衡二叉树。
三. 红黑树
红黑树和avl树类似，都是在进行插入和删除操作时通过特定的操作保持二叉树的平衡，从而获得较高的查找性能。
特点：
1.节点是红色或黑色
2.根节点是黑色
3.叶子节点（nil,空节点）是黑色
4.每个红色节点的两个子节点都是黑色
