一、什么是二叉树？
二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。
下图展示了一棵普通二叉树：
image
二、二叉树遍历
1 定义
二叉树的遍历是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。
二叉树的访问次序可以分为三种：
前序遍历
中序遍历
后序遍历
2 前序遍历（根左右）
前序遍历通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。
image
图3.13所示二叉树访问如下：
从根结点出发，则第一次到达结点A，故输出A;
继续向左访问，第一次访问结点B，故输出B；
按照同样规则，输出D，输出H；
当到达叶子结点H，返回到D，此时已经是第二次到达D，故不在输出D，进而向D右子树访问，D右子树不为空，则访问至I，第一次到达I，则输出I；
I为叶子结点，则返回到D，D左右子树已经访问完毕，则返回到B，进而到B右子树，第一次到达E，故输出E；
向E左子树，故输出J；
按照同样的访问规则，继续输出C、F、G；
则3.13所示二叉树的前序遍历输出为：
ABDHIEJCFG
3 中序遍历(左根右)
中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。
image
图3.13所示二叉树中序访问如下：
从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；
到达H，H左子树为空，则返回到H，此时第二次访问H，故输出H；
H右子树为空，则返回至D，此时第二次到达D，故输出D；
由D返回至B，第二次到达B，故输出B；
按照同样规则继续访问，输出J、E、A、F、C、G；
则3.13所示二叉树的中序遍历输出为：
HDIBJEAFCG
4 后序遍历(左右根)
后序遍历就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。
image
图3.13所示二叉树后序访问如下：
从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；
到达H，H左子树为空，则返回到H，此时第二次访问H，不输出H；
H右子树为空，则返回至H，此时第三次到达H，故输出H；
由H返回至D，第二次到达D，不输出D；
继续访问至I，I左右子树均为空，故第三次访问I时，输出I；
返回至D，此时第三次到达D，故输出D；
按照同样规则继续访问，输出J、E、B、F、G、C，A；
则图3.13所示二叉树的后序遍历输出为：
HIDJEBFGCA
三、二叉查找树
1 定义
二叉查找树也叫二叉搜索树，二叉排序树
1.若它的左子树不为空，则左子树上所有结点的值均小于等于根结点的值；
2.若它的右子树不为空，则右子树上所有结点的值均大于等于根结点的值；
3.它的左右子树均为二分查找树。
2 图解实例
选取一个节点为参照根节点，会发现所有的左侧子节点小于等于参照点，右侧大于等于参照点。
比如根节点9， 9所有的左侧子节点（5、2、7、1、3）都小于等于9.
比如根节点13，13所有的左侧子节点（11、10、12）都大于等于13.
image
3 查找
查找节点 10：根节点9开始，10>9 右侧，10<13 左侧，10<11 左侧，找到10.
image
下图是二叉查找树的极端情况
image.png
二叉查找树就是为了提高查询效率，而当前这种和我们写了一堆for循环是一样的。
为了应对这种情况：又出现了平衡二叉树--红黑树。后面会提到。
四、红黑树
1 定义
R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。也就是不能有连在一起的红色节点，但是可以有连在一起的黑色节点
（5）满足所有的二叉查找树的性质
红黑树示意图如下：
image
2 变换规则
image.png
1）颜色变换
2）左旋
image
左旋又分为两种情况，
（1）我们操作的结点E是整棵树的根节点，那么左旋实现为下面步骤
a. 将结点s的左子树变化为E的右子树。也就是将E.rightchild值修改为S.leftchild后将S.leftchild置为NULL,将S.leftchild.parent置为结点E的指针。
b.将结点E的父结点指针parent指向结点S
c.将s结点的父结点指针parent置为NULL。
（2）我们操作的结点E有父结点，那么左旋实现为下面步骤
a. 将结点s的左子树变化为E的右子树，也就是将E.rightchild值修改为S.leftchild后将S.leftchild置为NULL，将S.leftchild.parent置为结点E的指针
b.声明一个辅助指针变量，指向结点E，即存储的是E结点的指针。将结点S的父结点指针parent修改为结点E的父指针parent的值
c.通过辅助指针变量，将结点E的父指针parent修改指向结点S。
3）右旋
image
右旋同样分为两种情况，与左旋情况类似，故实际操作参考左旋。
3 插入
首先使用二叉搜索树的插入算法将一个元素插入到红黑树中，该元素作为新的叶子结点插入到某一外部结点位置，才插入结点过程中需要为新元素染色。
注意：上述描述中一个很重要的点是，在插入元素时，是将元素作为叶子结点插入的，插入到原红黑树的外部结点。
插入结点染色情况
1.如果插入前是空树，那么新插入的元素就会成为根节点，根据特征，需要将根节点染成黑色。
2.如果红黑树非空，那么在红黑树中插入新的结点时，所有的点都默认是红色结点。
插入结点后调整和平衡过程
1.变颜色的情况： 当前结点的父亲是红色，且它的祖父结点的另一个结点（也就是叔叔结点）也是红色：
（1）把父结点设为黑色
（2）把叔叔结点也设为黑色
（3）把祖父结点，也就是父亲的父亲设置为红色（爷爷结点）
（4）把指针定义到祖父结点设为当前要操作的结点（爷爷结点）。分析点的变换规则，进行变换。
2.左旋：当前父结点是红色，叔叔结点是黑色的时候，且当前的结点时右子树，则进行左旋。左旋过程不需要进行颜色变换。
3.右旋：当前父结点时红色，叔叔结点是黑色的时候，且当前的结点是左子树，则进行右旋。右旋过程中需要进行颜色变换，具体右旋过程如下。
（1）把父结点变为黑色
（2）把祖父结点变为红色（爷爷结点）
（3）以祖父结点进行右旋（爷爷结点）
实例讲解
image
参考视频：
https://www.bilibili.com/video/BV1tE411f7tP?p=4&spm_id_from=pageDriver
网友评论