二叉排序树（有序二叉树 / BST）… 1
一、基本概念… 1
二、节点结构（Java 通用定义）… 3
三、二叉排序树五大核心操作… 3
1. 插入节点（构建 BST 最基础操作）… 3
2. 查找节点… 5
3.广度优先遍历… 6
4.深度优先遍历… 8
—先序遍历… 8
–中序遍历… 10
—后序遍历… 11
5. 删除节点（最难重点，分 3 种情况）… 12
情况 1：待删节点是叶子节点（无左、无右孩子）… 12
情况 2：待删节点只有单侧子树（只有左孩子 / 只有右孩子）… 14
情况 3：待删节点左右子树都存在（最难）… 16
6. 获取最小值 / 最大值… 18
四、优缺点… 19
二叉排序树（有序二叉树 / BST）
一、基本概念
二叉排序树全称：二叉搜索树 Binary Search Tree，简称 BST
满足三大规则（核心判定条件）
✅ 重要特性：
对二叉排序树进行中序遍历（左→根→右），遍历结果一定是升序有序数组，这也是它叫有序二叉树的原因。
示例：
50
30 70
20 40 60 80
中序遍历：20,30,40,50,60,70,80（从小到大排列）
二、节点结构（Java 通用定义）
二叉树每个节点包含：数据域、左孩子指针、右孩子指针
三、二叉排序树五大核心操作
1. 插入节点（构建 BST 最基础操作）
插入规则：
运行
2. 查找节点
查找逻辑：
3.广度优先遍历
规则：从上至下，逐层遍历，每层从左到右
核心逻辑
借助队列：先进先出，根节点入队，出队时，它的左右节点入队
1. 根节点入队
2. 循环：队列不为空
– 队首节点出队，访问数值
– 左孩子不为空 → 入队
– 右孩子不为空 → 入队
4.深度优先遍历
—先序遍历
先序遍历：根 → 左 → 右
–中序遍历
中序遍历：左 → 根 → 右
遍历结果永久升序排列
—后序遍历
后序遍历：左 → 右 → 根
5. 删除节点（最难重点，分 3 种情况）
情况 1：待删节点是叶子节点（无左、无右孩子）
1.找到目标节点 target
2.找到目标节点的父节点parent 没有父节点：root=null；有父节点：直接将父节点指向该节点的引用置为 null 即可。
情况 2：待删节点只有单侧子树（只有左孩子 / 只有右孩子）
1.找到目标节点 target
2.找到目标节点的父节点parent 没有父节点：判断目标节点是有左子树还是右子树，root=target.left或root=target.right，用它唯一的子节点顶替自己的位置即可。有父节点，则：
情况 3：待删节点左右子树都存在（最难）
两种替换方案任选其一：
原理：左最大、右最小的数字，放到当前位置依旧满足 BST 规则
6. 获取最小值 / 最大值
- 最小值：一路向左遍历到底（最左下角节点）
- 最大值：一路向右遍历到底（最右下角节点）
// 找最小值
public Node getMin(Node root) {
while(root.left != null) root = root.left;
return root;
}
// 找最大值
public Node getMax(Node root) {
while(root.right != null) root = root.right;
return root;
}
四、优缺点
✅ 优点：
❌ 缺点：
