Java 语言中移除 BST 范围外的键

引言

二叉搜索树（BST）是计算机科学中用于执行快速搜索、插入和删除操作的基础数据结构。然而，在某些情况下，需要删除位于特定范围之外的 BST 键。本文探讨了实现此目标的多种方法和算法。

理解二叉搜索树

二叉搜索树是一种数据结构，每个节点最多有两个子节点，称为左子节点和右子节点。BST 属性规定，对于任何给定的节点，其左子树中的所有节点的值都小于其值，而其右子树中的所有节点的值都大于其值。

算法

步骤 1：从 BST 的根节点开始。

步骤 2：如果根节点为 null，则返回 null（基本情况）。

步骤 3：调用 removeOutsideRange(root.left, min_val, max_val) 递归地从左子树中删除超出范围的键。

步骤 4：使用 removeOutsideRange(root.right, min_val, max_val) 递归地从右子树中删除超出范围的键。

步骤 5：检查当前根节点的值。

1. 如果 root.val 小于 min_val，则返回正确的子树。
2. 如果 root.val > max_val，则返回左子树。
3. 否则，该值在范围内；因此，根节点保持不变。

步骤 6：返回更新后的根节点。

示例

BST

指定的范围是 [-10, 13]。

逐步使用算法

1. 从节点 6 开始，递归地从左子树中删除超出范围 (-13, -8) 的键。

• -13 在范围内，所以保留它。
• -8 也在范围内，所以保留它。

2. 递归地从右子树（14、15）中删除超出范围的键。

• 14 超出范围（大于 13）；因此，删除它及其右子树。
• 对于 15，它超出范围，所以删除它及其左子树。

3. 检查根值 6

• 它在范围内，所以保留它。

5. 更新后的子树变为

返回更新后的根节点。

因此，删除超出范围 [-10,13] 的键的 BST 是

这个修改后的 BST 只包含范围内的键，同时保留了 BST 属性。

实施

输出

说明

1. TreeNode 类：TreeNode 类表示二叉树中的一个节点。每个节点都有一个值 (val) 以及指向其左子节点和右子节点的指针。
2. Main 类：这是定义删除超出范围节点和遍历树的方法的类。
3. RemoveOutsideRange 方法：此方法接受三个参数：二叉搜索树的根节点 (root)、范围的最小值 (min) 和最大值 (max)。它会删除树中值超出范围 [min, max] 的所有节点。它会递归地遍历树，根据需要删除节点。
4. 中序遍历方法：此方法以反向顺序遍历二叉树。它按照以下顺序递归地遍历树：左子节点、根节点、右子节点，并打印每个节点的值。
5. Main 方法：这是程序的入口点。Main 方法创建一个 Main 类 (bst) 的实例，并构建一个具有不同值的二叉搜索树。然后，我们打印原始树的中序遍历，然后使用 removeOutsideRange 函数删除超出范围 [6, 22] 的节点，最后打印更改后树的中序遍历。