每一个节点包含：父节点地址 值 左子节点地址 右子节点地址

如果一个节点不含有：父节点地址或左子节点地址 右子节点地址就记为null

二叉树

度：每一个节点的子节点数量

二叉树中，任意节点的度<=2

树的结构：

二叉查找树：

二叉查找树，又称二叉排序树或者二叉搜素树

特点：

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

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

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

规则：小的存左边，大的存右边，一样的不存。

如果不是按照以上的规则就是普通的二叉树

二叉树的前序遍历

先从跟节点遍历，在向左遍历18在向左子节点遍历16，在向右子节点遍历19，在从20的右子节点遍历23在左子节点22在右子节点24.

二叉树中序遍历

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

按照左中右的方法进行遍历的。

这种遍历方式是按照从小到大的顺序排列的

二叉树后序遍历

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

二叉树层序遍历

从根节点开始一层一层的遍历

小结

二叉查找树的弊端：

存入数据时数据有可能都比父节点大，就使树右子节点过长，左子节点过短。所以我们就要学习平衡二叉树

平衡二叉树

规则：任意节点左右子树高度差不超过1

上图是平衡二叉树吗：答案：不是

看10节点，他的左子树为0右子树为3左右相差超过1所以不是。

平衡二叉树旋转机制

规则1：左旋

规则2：右旋

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

左旋

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

右旋

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

怎么旋转：

左左：当根节点左子树的左子树有节点插入，导致二叉树不平衡

一次右旋

左右：当根节点左子树的右子树有节点插入，导致二叉树不平衡

先局部左旋，再整体右

右右：当根节点右子树的右子树有节点插入，导致二叉树不平衡

一次左旋

右左：当根节点右子树的左子树有节点插入，导致二叉树不平衡

先局部右旋，再整体左旋

红黑树：

红黑树：是一个二叉查找树：但是，不是高度平衡的

条件： 特有的红黑规则

数据结构（红黑树）红黑规则：

1.每一个节点或是红色的，或者是黑色的

2.根节点必须是黑色

3.如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点(Nil)是黑色的

4.如果某一个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）

5.对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点；

添加节点默认是红色的（效率高）

添加节点的处理方案：