二叉树
一、什么是二叉树？
二、二叉查找树
1. 添加节点
规则：小的存左边、大的存右边、一样的不存。
2. 遍历节点
前序遍历： 从根节点开始，然后按照当前节点，左子节点，右子节点的顺序遍历
中序遍历： 从最左边的子节点开始，然后按照左子节点，当前节点，右子节点的顺序遍历
后序遍历： 从最左边的子节点开始，然后按照左子节点，右子节点，当前节点的顺序遍历
层序遍历： 从根节点开始一层一层的遍历
三、平衡二叉树
规则：任意节点左右子树高度差不超过1
1. 左旋
确定支点：从添加的节点开始，不断的往父节点找不平衡的节点
步骤
以不平衡的点作为支点
把支点左旋降级，变成左子节点 / 将根节点的右侧往左拉
晋升原来的右子节点 / 原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点
2. 右旋
确定支点：从添加的节点开始，不断的往父节点找不平衡的节点
步骤
以不平衡的点作为支点
把支点左旋降级，变成右子节点 / 将根节点的左侧往右拉
晋升原来的左子节点 / 原先的左子节点变成新的父节点，并把多余的右子节点出让，给已经降级的根节点当左子节点