二叉排序树（BST）Java 完整实现 + 删除思路详解

一、二叉排序树核心特性左子树所有节点值根节点值右子树所有节点值根节点值中序遍历结果为升序数组核心操作新增、查找、遍历、删除重难点二、删除节点三大场景核心思路设待删除节点为target场景 1target 是叶子节点无左、无右孩子直接把父节点指向 target 的引用置为null释放节点。场景 2target 只有单侧子树只有左 / 只有右用 target 唯一的子节点顶替 target父节点直接指向该孩子。场景 3target 同时有左、右子树最复杂两种经典方案任选一种这里采用右子树最小值顶替找到 target右子树最小节点右子树最左下节点把最小节点的val赋值给 target覆盖待删值递归删除右子树中原来的最小节点最小节点一定满足场景 1/2替代方案取左子树最大值顶替逻辑完全对称。三、完整 Java 代码实现java运行/** * 二叉排序树节点类 */ class BSTNode { int val; BSTNode left; BSTNode right; public BSTNode(int val) { this.val val; this.left null; this.right null; } } /** * 二叉排序树工具类封装增、删、查、遍历 */ public class BinarySortTree { private BSTNode root; public BinarySortTree() { this.root null; } // 1. 添加节点 public void add(int val) { root addRecursion(root, val); } /** * 递归新增节点 */ private BSTNode addRecursion(BSTNode node, int val) { // 递归终止找到空位新建节点返回 if (node null) { return new BSTNode(val); } // 小于当前节点往左子树递归 if (val node.val) { node.left addRecursion(node.left, val); } // 大于当前节点往右子树递归 else if (val node.val) { node.right addRecursion(node.right, val); } // 相等二叉排序树不允许重复值直接返回原节点 else { return node; } return node; } // 2. 查找节点 public boolean search(int val) { return searchRecursion(root, val); } private boolean searchRecursion(BSTNode node, int val) { if (node null) { return false; } if (val node.val) { return true; } else if (val node.val) { return searchRecursion(node.left, val); } else { return searchRecursion(node.right, val); } } // 3. 中序遍历升序 public void inOrder() { System.out.print(中序遍历(升序)); inOrderRecursion(root); System.out.println(); } private void inOrderRecursion(BSTNode node) { if (node null) return; inOrderRecursion(node.left); System.out.print(node.val ); inOrderRecursion(node.right); } // 4. 删除节点核心方法 public void delete(int val) { root deleteRecursion(root, val); } /** * 递归删除目标值节点返回处理后的子树根节点 * param node 当前递归节点 * param val 待删除值 * return 删除后该分支新根 */ private BSTNode deleteRecursion(BSTNode node, int val) { // 递归终止未找到待删除节点 if (node null) { return null; } // 1. 待删值 当前节点向左递归删除 if (val node.val) { node.left deleteRecursion(node.left, val); return node; } // 2. 待删值 当前节点向右递归删除 else if (val node.val) { node.right deleteRecursion(node.right, val); return node; } // 3. val node.val找到待删除节点分3种情况处理 else { // 情况1叶子节点直接删除返回null if (node.left null node.right null) { return null; } // 情况2只有右孩子右孩子顶替当前节点 else if (node.left null) { return node.right; } // 情况2只有左孩子左孩子顶替当前节点 else if (node.right null) { return node.left; } // 情况3同时存在左右子树取右子树最小值顶替 else { // 步骤1获取右子树最小节点 BSTNode minNode getMinNode(node.right); // 步骤2用最小值覆盖待删除节点的值 node.val minNode.val; // 步骤3递归删除右子树中原最小节点 node.right deleteRecursion(node.right, minNode.val); return node; } } } /** * 获取一棵子树中的最小节点最左下节点 */ private BSTNode getMinNode(BSTNode node) { while (node.left ! null) { node node.left; } return node; } // 测试主方法 public static void main(String[] args) { BinarySortTree bst new BinarySortTree(); // 构建树5,3,7,2,4,6,8 int[] arr {5, 3, 7, 2, 4, 6, 8}; for (int num : arr) { bst.add(num); } bst.inOrder(); // 输出2 3 4 5 6 7 8 System.out.println( 删除叶子节点 2 ); bst.delete(2); bst.inOrder(); // 3 4 5 6 7 8 System.out.println( 删除单侧子树节点7只有右孩子8 ); bst.delete(7); bst.inOrder(); // 3 4 5 6 8 System.out.println( 删除左右都有子树的根节点5 ); bst.delete(5); bst.inOrder(); // 3 4 6 8 } }四、代码逻辑逐段解析1. 节点类 BSTNode存储数值、左右子节点引用基础实体类。2. add 新增逻辑递归向下查找空位小于当前节点 → 左子树大于当前节点 → 右子树相等直接忽略不支持重复值3. deleteRecursion 删除核心递归递归定位待删除节点小往左、大往右匹配到目标节点后分 3 种场景无左右孩子叶子return null父节点指向空只有单侧孩子直接返回唯一子节点完成顶替左右孩子都存在getMinNode找到右子树最小值覆盖当前节点值等价于 “删除原节点替换成最小值”递归删除右子树里原来的最小节点最小节点必然无左孩子属于场景 1/2。4. getMinNode 工具方法循环遍历左子树直到左为空得到当前子树最小值。5. 中序遍历验证二叉排序树中序遍历一定升序用来校验增删是否正确。五、运行输出结果plaintext中序遍历(升序)2 3 4 5 6 7 8 删除叶子节点 2 中序遍历(升序)3 4 5 6 7 8 删除单侧子树节点7只有右孩子8 中序遍历(升序)3 4 5 6 8 删除左右都有子树的根节点5 中序遍历(升序)3 4 6 8六、拓展补充删除方案替换如果想用「左子树最大值顶替」写getMaxNode取左子树最右节点即可非递归删除递归写法简洁易理解面试优先写递归非递归需要额外记录父节点、标记左右分支代码冗余重复值处理如需支持重复数字可在节点新增count计数删除时先减计数计数为 0 再执行删除逻辑。