Question

数据结构之二叉树详解

Answer 1

1 定义

2 前序遍历（根左右）

前序遍历 通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。

图3.13所示二叉树访问如下：

则3.13所示二叉树的前序遍历输出为：
ABDHIEJCFG

3 中序遍历(左根右)

中序遍历 就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。

图3.13所示二叉树中序访问如下：

则3.13所示二叉树的中序遍历输出为：
HDIBJEAFCG

4 后序遍历(左右根)

后序遍历 就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。

图3.13所示二叉树后序访问如下：

则图3.13所示二叉树的后序遍历输出为：
HIDJEBFGCA

1 定义

2 图解实例

选取一个节点为参照根节点，会发现所有的左侧子节点小于等于参照点，右侧大于等于参照点。

比如根节点9， 9所有的 左侧子节点（5、2、7、1、3） 都小于等于9.

比如根节点13，13所有的 左侧子节点（11、10、12） 都大于等于13.

3 查找

查找节点 10：根节点9开始，10>9 右侧，10<13 左侧，10<11 左侧，找到10.

下图是二叉查找树的极端情况

二叉查找树就是为了提高查询效率，而当前这种和我们写了一堆for循环是一样的。
为了应对这种情况：又出现了平衡二叉树--红黑树。后面会提到。

1 定义

红黑树的特性 :
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。也就是不能有连在一起的红色节点，但是可以有连在一起的黑色节点
（5）满足所有的二叉查找树的性质

红黑树示意图如下：

2 变换规则

左旋又分为两种情况，

（1）我们操作的结点E是整棵树的根节点，那么左旋实现为下面步骤

（2）我们操作的结点E有父结点，那么左旋实现为下面步骤

3）右旋

右旋同样分为两种情况，与左旋情况类似，故实际操作参考左旋。

3 插入

注意 ：上述描述中一个很重要的点是，在插入元素时，是将元素作为叶子结点插入的，插入到原红黑树的外部结点。

插入结点染色情况

插入结点后调整和平衡过程

1.变颜色的情况： 当前结点的父亲是红色，且它的祖父结点的另一个结点（也就是叔叔结点）也是红色：

2.左旋：当前父结点是红色，叔叔结点是黑色的时候，且当前的结点时右子树，则进行左旋。左旋过程不需要进行颜色变换。

3.右旋：当前父结点时红色，叔叔结点是黑色的时候，且当前的结点是左子树，则进行右旋。右旋过程中需要进行颜色变换，具体右旋过程如下。

实例讲解

参考视频：
https://www.bilibili.com/video/BV1tE411f7tP?p=4&spm_id_from=pageDriver