看的就懂d二叉树-搜索二叉树-平衡二叉树AVL-红黑树RBT

vlambda
2021-01-09

看的就懂d二叉树-搜索二叉树-平衡二叉树AVL-红黑树RBT

（一）二叉树的先序-中序-后序遍历

核心：

先序遍历从顶部开始，中序遍历从最左部开始(建议补充未完全二叉树后，有节
点的最左边)，后序遍历从最下部开始（如果并列，则从最左下开始遍历）
且先序遍历第一个绝对是根节点，后续遍历最后一个绝对是根节点
不论是先，中，后，序遍历，只是根节点遍历的顺序不同，左节点始终是在右节
点之前遍历（可用于检查）

步骤：

根据遍历类型确定起点，先序（根节点），中序（最左节点），后序（最左下节
点）
以起点作为基元的根节点（不存在的节点可理解为空节点），开始按照遍历类型规
律进行遍历：先序（根-左-右），中序（左-根-右），后序（左-右-根）
分情况判断是否为叶子节点
若为先序：写出该基元的根-左，判断左节点是否为叶子节点，如果不是，
则以该节点为下一层基元的根节点，按照遍历类型规律书写（递归下去去找）。如果
是，则把该基元的右节点写出。
若为中序：写出该基元的左-根，判断右节点是否为叶子节点，如果不是，
则以该节点为下一层基元的根节点，按照遍历类型规律书写（递归下去去找）。如果
是，则把该基元的右节点写出。
若为后序：写出该基元的左，判断基元中的右节点是否为叶子节点，如果不
是，则以该节点为下一层基元的根节点，按照左-右-根的规律书写（递归下去找），
如果是，则写出该节点和其根节点
对于已经是叶子节点后，向上回溯，按照遍历类型的规则进行遍历，遍历过的元素
不可重复遍历

使用递归方式遍历

/*** 树节点*/public class TreeNode {
/*** 节点名称*/private String name; /** * 权值 */ private int weight; /** * 左子节点 */ private TreeNode leftChildNode; /** * 右子节点 */ private TreeNode rightChildNode; //省略getter，setter构造

排序类

package com.zuikaku.utils;
import com.zuikaku.pojo.TreeNode;
import java.util.ArrayList;import java.util.List;

/** * 排序工具 */public class TreeSortUtils { public static List<TreeNode> treeNodeList = new ArrayList<TreeNode>();
 /** * 递归调用，先序排序 * @param node * @return */ public static void root_left_right_sort(TreeNode node) { //根‐左‐右 if (node != null) { treeNodeList.add(node); root_left_right_sort(node.getLeftChildNode()); root_left_right_sort(node.getRightChildNode()); } }
 /** * 递归调用，中序排序 * @param node */ public static void left_root_right_sort(TreeNode node) { //左‐根‐右 if (node != null) { left_root_right_sort(node.getLeftChildNode()); treeNodeList.add(node); left_root_right_sort(node.getRightChildNode()); } }
 public static void left_right_root_sort(TreeNode node) { //左‐右‐根 if (node != null) { left_right_root_sort(node.getLeftChildNode()); left_right_root_sort(node.getRightChildNode()); treeNodeList.add(node); } }}

测试类

package com.zuikaku.utils;
import com.zuikaku.pojo.TreeNode;import java.util.ArrayList;import java.util.List;/** * 排序工具 */public class TreeSortUtils { public static List<TreeNode> treeNodeList = new ArrayList<TreeNode>();
 /** * 递归调用，先序排序 * @param node * @return */ public static void root_left_right_sort(TreeNode node) { //根‐左‐右 if (node != null) { treeNodeList.add(node); root_left_right_sort(node.getLeftChildNode()); root_left_right_sort(node.getRightChildNode()); } }
 /** * 递归调用，中序排序 * @param node */ public static void left_root_right_sort(TreeNode node) { //左‐根‐右 if (node != null) { left_root_right_sort(node.getLeftChildNode()); treeNodeList.add(node); left_root_right_sort(node.getRightChildNode()); } }
 public static void left_right_root_sort(TreeNode node) { //左‐右‐根 if (node != null) { left_right_root_sort(node.getLeftChildNode()); left_right_root_sort(node.getRightChildNode()); treeNodeList.add(node); } }}

看的就懂d二叉树-搜索二叉树-平衡二叉树AVL-红黑树RBT

（二）二叉树种类定义

[1]二叉树的种类是随着不断优化而更加严格定义的

二叉查找树（二叉排序树，二叉搜索树）：即本质是二叉树，其左子节点小于根节
点，右子节点大于根节点，理想时间复杂度为o(logn)，但当极端情况下，二叉查找
树退化为链表结构后会使复杂度上升为o(n)级别
二叉平衡树AVL：在满足二叉查找树的条件下，避免了其极端情况下变为链式结
构，其规定层节点的左右子节点高度相差不大于1。其可以通过二叉查找树，左旋，
右旋变化到二叉平衡树。原变化时的二叉查找树分为LL型，LR型，和RR型。二叉树
结构越平衡，则效率就越好。
红黑树：进一步优化，为了解决转变为二叉平衡树时左旋，右旋效率低下，进一步
作出以下限定。
（1）首先具备二叉查找树的特点。
（2）叶子节点是黑色的空节点，不存数据。
（3）没有相邻的红色节点，之间必然存在黑节点隔开。
（4）根节点是黑色的。
（5）节点到其叶子节点包含的黑色节点数量是相同的。
这样操作能保证复杂度为o(logn)，其特点就是节点增删的时候不会破坏结构。但要从效率上讲，平衡二叉树的效率依然优于，红黑树。

在RBTree中其他性质：

最长路径一定不会长于最短路径的两倍（无论其是否包含NIL）
最长路径和最短路径所经过的黑色节点数量一定相同（无论其-是否包含NIL）
红黑树的效率稍小于平衡二叉树，理想情况下可达到O(logN)，但必然小于2O(logN)【因为最长路径小于两倍的最短路径】
红黑树牺牲了一点性能但保证了3次旋转内必能平衡

[2]二叉树左旋右旋操作
目的：减少树的高度，提高遍历效率，使树更加平衡

(1)左旋

步骤：

确定以哪个目标节点旋转，确定该目标节点是否存在右子节点
以目标节点的右子节点为Y轴，该右子节点的右下方不变，左方逆时针旋转，仅考
虑与该右子节点直接相连的节点及其他们的子节点，其余暂不考虑，将该右子节点的
父节点（就是目标节点）移动到其左子节点且保留其原来目标节点的左子结构。
由于移动，原目标节点的右子节点的原左子丢失，此时目标节点的右指针为空，就
把这个原目标节点的右子节点的左子节点，放在现在目标节点的右子节点上
原目标节点的父节点左指针现在指向改为原目标节点的右子节点，左旋完成
核心:
目标节点的右子节点不为空
目标节点的右子节点的右下部分不会改变
旋转后节点个数不会减少
案例：T为目标节点，Y为其右子节点

(2)右旋：操作类似，和左转反着来

步骤：

确定以哪个目标节点旋转，确定该目标节点是否存在左子节点
以目标节点的左子节点为Y轴，该左子节点的左下方不变，右方顺时针旋转，仅考
虑与该左子节点直接相连的节点及其他们的子节点，其余暂不考虑，将该左子节点的
父节点（就是目标节点）移动到其右子节点且保留其原来目标节点的右子结构。
由于移动，原目标节点的左子节点的原右子丢失，此时目标节点的左指针为空，就
把这个原目标节点的左子节点的右子节点，放在现在目标节点的左子节点上
原目标节点的父节点右指针现在指向改为原目标节点的左子节点，右旋完成
核心:
目标节点的左子节点不为空
左子节点的左下部分不会改变
旋转后节点个数不会减少
案例：T为目标节点，Y为其左子节点