数据结构之二叉树详解
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
2024-06-11 广告