Java二叉搜索树范围查询：递归实现中的常见陷阱与修正

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

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

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

    public void recIRV(ArrayList<KeyValuePair<K, V>> L, K key1, K key2, BinaryTreeNode<MapEntry<K,V>> 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语句逻辑也是有问题的，会提前终止不必要的递归
    }
}

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

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> {
    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<T extends KeyValuePair<?, ?>> {
    private T value;
    private BinaryTreeNode<T> leftChild;
    private BinaryTreeNode<T> rightChild;

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

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

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

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

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

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

    private BinaryTreeNode<MapEntry<K, V>> putRecursive(BinaryTreeNode<MapEntry<K, V>> 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<KeyValuePair<K, V>> inRangeValues(K key1, K key2) {
        ArrayList<KeyValuePair<K, V>> L = new ArrayList<>();
        recIRV(L, key1, key2, root); // 从根节点开始递归
        return L;
    }

    /**
     * 辅助递归方法，执行前序遍历并收集在指定范围内的键值对。
     *
     * @param L 存储结果的列表
     * @param key1 范围的下限（包含）
     * @param key2 范围的上限（不包含）
     * @param R 当前正在处理的节点
     */
    private void recIRV(ArrayList<KeyValuePair<K, V>> L, K key1, K key2, BinaryTreeNode<MapEntry<K,V>> 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<Integer, Integer> 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<KeyValuePair<Integer, Integer>> result = T1.inRangeValues(20, 51);
        System.out.println("inRangeValues(20, 51) Expected value: [50 23]");
        System.out.println("Actual result: " + result); // 应该输出 [50 23]
    }
}

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