二叉搜索树范围查询：递归遍历中的常见错误与修正

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

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

    // 递归遍历左子树
    if(R.getLeftChild() != null) {
        recIRV(L, key1, key2, root.getLeftChild()); // 错误：这里应该使用 R.getLeftChild()
    }
    // 递归遍历右子树
    if(R.getRightChild() != null) { 
        recIRV(L, key1, key2, root.getRightChild()); // 错误：这里应该使用 R.getRightChild()
    }
    else {
        return; // 此处的else块是多余的，递归方法在没有子节点时自然会结束
    }
}

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

inRangeValues(20, 51)
Expected value: [50 23]

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

// 假设 BinaryTreeNode 和 KeyValuePair, MapEntry 已经定义
// 例如：
// interface KeyValuePair<K, V> { K getKey(); V getValue(); }
// class MapEntry<K, V> implements KeyValuePair<K, V> { ... }
// class BinaryTreeNode<T> { T value; BinaryTreeNode<T> leftChild; BinaryTreeNode<T> rightChild; ... }

public class BinarySearchTree<K, V> {
    private BinaryTreeNode<MapEntry<K, V>> root;
    private Comparator<K> keyComparator;

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

    /**
     * 在指定键范围内（[key1, key2)）查找所有键值对，并按前序遍历顺序返回。
     *
     * @param key1 范围的起始键（包含）
     * @param key2 范围的结束键（不包含）
     * @return 包含所有符合条件的键值对的ArrayList
     */
    public ArrayList<KeyValuePair<K, V>> inRangeValues(K key1, K key2) {
        ArrayList<KeyValuePair<K, V>> resultList = new ArrayList<>();
        recIRV(resultList, key1, key2, root); // 从根节点开始递归
        return resultList;           
    }

    /**
     * 辅助递归方法，用于遍历二叉搜索树并收集范围内的键值对。
     * 按照前序遍历的逻辑进行，即先处理当前节点，再递归左子树，最后递归右子树。
     *
     * @param L 存储结果的ArrayList
     * @param key1 范围的起始键
     * @param key2 范围的结束键
     * @param R 当前正在处理的节点
     */
    private void recIRV(ArrayList<KeyValuePair<K, V>> L, K key1, K key2, BinaryTreeNode<MapEntry<K,V>> R) {
        // 基本情况：如果当前节点为空，则返回
        if (R == null) {
            return;
        }

        // 1. 处理当前节点（前序遍历的核心）
        // 检查当前节点是否在范围内，如果在则添加到列表中
        if (keyComparator.compare(R.getValue().getKey(), key1) >= 0 && 
            keyComparator.compare(R.getValue().getKey(), key2) < 0) {
            L.add(R.getValue());
        }

        // 2. 递归遍历左子树
        // 优化：对于BST，如果当前节点的键值已经小于key1，则其左子树中的所有键值也会小于key1，
        // 此时无需遍历左子树。但为了严格遵循“前序遍历所有节点并筛选”的语义，我们通常会遍历。
        // 如果题目要求的是更高效的BST范围查找（非严格前序遍历所有节点），可以添加剪枝逻辑。
        // 当前实现是遍历所有可能路径以确保前序顺序，然后筛选。
        recIRV(L, key1, key2, R.getLeftChild()); // 正确：使用 R.getLeftChild()

        // 3. 递归遍历右子树
        // 优化：如果当前节点的键值已经大于等于key2，则其右子树中的所有键值也会大于等于key2，
        // 此时无需遍历右子树。同上，取决于具体的前序遍历定义和效率要求。
        recIRV(L, key1, key2, R.getRightChild()); // 正确：使用 R.getRightChild()
    }
}

        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);

        // 树结构：
        //               50
        //       10______||______56 
        //  2____||___23          |____70             
        //0____|                    61____|

        inRangeValues(20, 51)
        Expected value: [50 23]