【零基础学java】（二叉树）

二叉查找树：

1.每一个节点上最多有两个子节点

2.  任意节点左子树上的值都小于当前节点

3.任意节点右子节树上的值都大于当前节点

4.添加节点：小的存左边，大的存右边，一样的不存

二叉树遍历

前序遍历：从根节点开始，然后按照当前节点，左子节点，右子节点的顺序遍历

中序遍历：从最左边的子节点开始，然后按照左子节点**，当前节点**，右子节点的顺序遍历（按照这种方式，遍历出的数据是从小到大的顺序。左中右）

后续遍历：从最左边的子节点开始，然后按照左子节点，右子节点，当前节点的顺序遍历

层序遍历：一层一层的去遍历

平衡二叉树：任意节点左右子树高度差不超过1

平衡二叉树的旋转机制

左旋：

1.确定支点：从添加的节点开始，不断的往父节点找不平衡的节点

2.旋转过程：以不平衡的点作为支点，把支点左旋降级，变成左子节点，晋升原来的右子节点。

  3.当原来的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点的当右子节点

右旋：反之

触发时机：当添加一个节点之后，该树不再是一颗平衡二叉树。

左左：当根节点左子树的左子树有节点插入，导致而二叉树不平衡，只要进行一次右旋就可以平衡

左右：当根节点左子树的右子树有节点插入，导致二叉树不平衡，先进行局部的左旋，变成左左。再进行整体的右旋