Java二叉搜索树范围查询陷阱与修复方法

本文将深入探讨如何在二叉搜索树（BST）中高效实现范围查询（`inRangeValues`）功能。我们将重点分析递归遍历过程中常见的逻辑错误，即在递归调用时错误地引用根节点而非当前节点，并提供正确的实现方式，以确保数据按前序遍历顺序准确收集在指定键值范围内。

理解二叉搜索树范围查询

在二叉搜索树（BST）中执行范围查询是一项常见操作，其目标是检索所有键值落在指定范围 [key1, key2) 内的键值对。这里的范围是闭区间 key1 到开区间 key2，即键值大于等于 key1 且小于 key2。此外，通常会要求返回的结果列表按照特定的遍历顺序排列，例如前序遍历（Pre-order Traversal）。

为了实现这一功能，我们通常会设计一个公共方法 inRangeValues(K key1, K key2)，它初始化一个空的 ArrayList 来存储结果，并调用一个私有的辅助递归方法 recIRV 来实际遍历树并收集符合条件的元素。

递归实现中的常见陷阱

考虑以下一个尝试实现 inRangeValues 辅助递归方法 recIRV 的初始代码片段：

public class BinarySearchTree {
    private BinaryTreeNode> root; // 树的根节点
    private Comparator keyComparator; // 用于比较键的比较器

    // ... 其他方法和构造函数 ...

    public ArrayList> inRangeValues(K key1, K key2) {
        ArrayList> L = new ArrayList<>();
        recIRV(L, key1, key2, root); // 从根节点开始递归
        return L;
    }

    public void recIRV(ArrayList> L, K key1, K key2, BinaryTreeNode> R) {
        // 1. 检查当前节点是否在范围内，如果在则添加
        if (keyComparator.compare(R.getValue().getKey(), key1) >= 0 && 
            keyComparator.compare(R.getValue().getKey(), key2) < 0) {
            L.add(R.getValue());
        }

        // 2. 递归遍历左子树
        if (R.getLeftChild() != null) {
            recIRV(L, key1, key2, root.getLeftChild()); // 错误：这里使用了 'root.getLeftChild()'
        }

        // 3. 递归遍历右子树
        if (R.getRightChild() != null) { 
            recIRV(L, key1, key2, root.getRightChild()); // 错误：这里使用了 'root.getRightChild()'
        }
        // else { return; } // 此处的else语句逻辑也是有问题的，会提前终止不必要的递归
    }
}

上述代码中存在一个关键的逻辑错误。当 recIRV 方法被调用时，参数 R 代表当前正在处理的节点。然而，在递归调用其左子树和右子树时，代码错误地使用了 root.getLeftChild() 和 root.getRightChild()。这意味着无论当前节点 R 是什么，递归调用总是尝试从 原始根节点 的左子节点或右子节点开始，而不是从 当前节点 R 的左子节点或右子节点开始。

例如，如果树的结构如下：

                 50
         10______||______56 
    2____||___23          |____70             
 0____|                    61____|

当 R 是节点 10 时，代码会检查 10 是否在范围内。然后，它尝试递归遍历左子树。但 root.getLeftChild() 仍然指向 10（因为 root 是 50，50 的左子节点是 10）。这将导致 recIRV 被再次调用，传入的 R 仍然是 10，从而形成无限递归或导致遍历路径错误，无法正确访问 10 的左子节点 2。

正确的递归实现

要修正这个错误，我们需要确保递归调用是针对当前节点的子节点进行的。此外，为了使递归更加健壮，我们应该在方法开头添加一个对 R 是否为 null 的检查，作为递归的基线条件。

以下是修正后的 recIRV 方法：

import java.util.ArrayList;
import java.util.Comparator;

// 假设 BinaryTreeNode 和 KeyValuePair, MapEntry 已经定义
interface KeyValuePair {
    K getKey();
    V getValue();
}

class MapEntry implements KeyValuePair {
    private K key;
    private V value;

    public MapEntry(K key, V value) {
        this.key = key;
        this.value = value;
    }

    @Override
    public K getKey() { return key; }

    @Override
    public V getValue() { return value; }

    @Override
    public String toString() { return key + " " + value; } // 便于打印
}

class BinaryTreeNode> {
    private T value;
    private BinaryTreeNode leftChild;
    private BinaryTreeNode rightChild;

    public BinaryTreeNode(T value) {
        this.value = value;
        this.leftChild = null;
        this.rightChild = null;
    }

    public T getValue() { return value; }
    public BinaryTreeNode getLeftChild() { return leftChild; }
    public BinaryTreeNode getRightChild() { return rightChild; }

    public void setLeftChild(BinaryTreeNode leftChild) { this.leftChild = leftChild; }
    public void setRightChild(BinaryTreeNode rightChild) { this.rightChild = rightChild; }
}

public class BinarySearchTree {
    private BinaryTreeNode> root;
    private Comparator keyComparator;

    public BinarySearchTree(Comparator keyComparator) {
        this.keyComparator = keyComparator;
        this.root = null;
    }

    // 简化版put方法，用于构建示例树
    public void put(K key, V value) {
        root = putRecursive(root, key, value);
    }

    private BinaryTreeNode> putRecursive(BinaryTreeNode> current, K key, V value) {
        if (current == null) {
            return new BinaryTreeNode<>(new MapEntry<>(key, value));
        }

        int cmp = keyComparator.compare(key, current.getValue().getKey());
        if (cmp < 0) {
            current.setLeftChild(putRecursive(current.getLeftChild(), key, value));
        } else if (cmp > 0) {
            current.setRightChild(putRecursive(current.getRightChild(), key, value));
        } else {
            // Key already exists, update value (or handle as error/no-op)
            // current.getValue().setValue(value); // If MapEntry allows value update
        }
        return current;
    }

    /**
     * 实现inRangeValues方法，返回指定键范围内的所有键值对，按前序遍历顺序。
     * 范围为 [key1, key2)，即 key >= key1 且 key < key2。
     */
    public ArrayList> inRangeValues(K key1, K key2) {
        ArrayList> L = new ArrayList<>();
        recIRV(L, key1, key2, root); // 从根节点开始递归
        return L;
    }

    /**
     * 辅助递归方法，执行前序遍历并收集在指定范围内的键值对。
     *
     * @param L 存储结果的列表
     * @param key1 范围的下限（包含）
     * @param key2 范围的上限（不包含）
     * @param R 当前正在处理的节点
     */
    private void recIRV(ArrayList> L, K key1, K key2, BinaryTreeNode> R) {
        // 基线条件：如果当前节点为null，则直接返回
        if (R == null) {
            return;
        }

        // 1. 处理当前节点 (Root)
        // 检查当前节点的值是否在指定范围 [key1, key2) 内
        if (keyComparator.compare(R.getValue().getKey(), key1) >= 0 && 
            keyComparator.compare(R.getValue().getKey(), key2) < 0) {
            L.add(R.getValue());
        }

        // 2. 递归遍历左子树 (Left)
        // 正确的做法是传入当前节点的左子节点 R.getLeftChild()
        recIRV(L, key1, key2, R.getLeftChild());

        // 3. 递归遍历右子树 (Right)
        // 正确的做法是传入当前节点的右子节点 R.getRightChild()
        recIRV(L, key1, key2, R.getRightChild());
    }

    public static void main(String[] args) {
        // 示例用法
        BinarySearchTree T1 = new BinarySearchTree<>(Comparator.naturalOrder());
        T1.put(50, 50);
        T1.put(10, 10);
        T1.put(56, 56);
        T1.put(2, 2);
        T1.put(23, 23);
        T1.put(70, 70);
        T1.put(0, 0);
        T1.put(61, 61);

        System.out.println("Tree structure (conceptual):");
        System.out.println("                 50");
        System.out.println("         10______||______56");
        System.out.println("    2____||___23          |____70");
        System.out.println(" 0____|                    61____|");
        System.out.println();

        // 执行范围查询 inRangeValues(20, 51)
        ArrayList> result = T1.inRangeValues(20, 51);
        System.out.println("inRangeValues(20, 51) Expected value: [50 23]");
        System.out.println("Actual result: " + result); // 应该输出 [50 23]
    }
}

修正与逻辑解析

修正后的 recIRV 方法遵循了标准的前序遍历（根-左-右）模式，并结合了范围检查：

1. 基线条件 (if (R == null)): 这是任何递归方法中至关重要的一步。当 R 为 null 时，表示已经到达了树的末端（叶子节点的子节点），此时没有更多节点可以处理，递归应该终止并返回。
2. 处理当前节点 (if (keyComparator.compare(...)): 在访问子节点之前，首先处理当前节点 R。这确保了结果列表 L 中的元素是按照前序遍历的顺序添加的。如果当前节点的键值符合 [key1, key2) 的范围条件，则将其添加到结果列表。
3. 递归遍历左子树 (recIRV(L, key1, key2, R.getLeftChild())): 调用 recIRV 方法，并将当前节点 R 的左子节点作为新的当前节点传入。这是正确的递归方式，确保遍历沿着树的实际分支向下进行。
4. 递归遍历右子树 (recIRV(L, key1, key2, R.getRightChild())): 类似地，在处理完左子树后，递归遍历右子树，将当前节点 R 的右子节点作为新的当前节点传入。

通过将 root.getLeftChild() 和 root.getRightChild() 替换为 R.getLeftChild() 和 R.getRightChild()，我们确保了递归调用能够正确地沿着树的当前路径向下探索，而不是每次都回到根节点的子节点，从而解决了无限循环和遍历错误的问题。

示例验证

使用修正后的代码，针对给定的树结构和查询 inRangeValues(20, 51)：

                 50
         10______||______56 
    2____||___23          |____70             
 0____|                    61____|

键值范围为 [20, 51)，即键 >= 20 且 < 51。

1. recIRV(..., 50):
   • 50 在 [20, 51) 范围内吗？ `50 >= 20