二叉搜索树(BST)仅保留最后3个元素，搜索范围受限问题求助

问题根源 #

你的add方法存在致命错误：在遍历寻找插入位置时，直接修改了类的成员变量this.root，导致每次插入后根节点被替换成遍历路径上的最后一个节点，最终整个BST的结构完全被破坏——原来的根节点和上层节点都丢失了，搜索时只能访问最后几次插入形成的局部子树。

举个例子，你插入5→4→2→3→6→1的过程中：

• 插入5后，root是5
• 插入4时，遍历到root.left并插入，随后root被改成4
• 插入2时，遍历到root.left并插入，随后root被改成2
• 以此类推，最后root会变成1，搜索时只能访问1、6、3这些节点，原来的5、4、2都无法被找到。

修复方案 #

修改add方法，使用临时变量遍历树，绝对不能直接修改this.root。用一个current节点跟踪当前遍历位置，保留原始根节点的引用。

修正后的完整代码 #

public class BinarySearchTree<T extends Comparable<T>> {

    BstNode root;
    private int sizeoftree = 0;

    // 二叉搜索树节点类
    class BstNode {
        T val;
        BstNode left, right;

        public BstNode(T val) {
            this.val = val;
            left = null;
            right = null;
        }
    }

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

    public int size() {
        return sizeoftree;
    }

    public boolean add(T val) {
        if (this.root == null) {
            this.root = new BstNode(val);
            sizeoftree++;
            return true;
        }
        // 用临时变量current遍历，不修改原始root
        BstNode current = this.root;
        while (true) {
            int compareResult = val.compareTo(current.val);
            if (compareResult < 0) {
                if (current.left == null) {
                    current.left = new BstNode(val);
                    sizeoftree++;
                    return true;
                }
                current = current.left;
            } else if (compareResult > 0) {
                if (current.right == null) {
                    current.right = new BstNode(val);
                    sizeoftree++;
                    return true;
                }
                current = current.right;
            } else {
                // 元素已存在，直接返回false
                return false;
            }
        }
    }

    public boolean contains(T val) {
        return search(this.root, val);
    }

    private boolean search(BstNode root, T data) {
        if (root == null) {
            return false;
        } else if (root.val.compareTo(data) == 0) {
            return true;
        } else if (root.val.compareTo(data) > 0) {
            return search(root.left, data);
        }
        return search(root.right, data);
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
        tree.add(5);
        tree.add(4);
        tree.add(2);
        tree.add(3);
        tree.add(6);
        tree.add(1);
        // 现在所有元素都能被正确找到
        System.out.println(tree.contains(5)); // 输出true
        System.out.println(tree.contains(4)); // 输出true
        System.out.println(tree.contains(2)); // 输出true
        System.out.println(tree.contains(3)); // 输出true
        System.out.println(tree.contains(6)); // 输出true
        System.out.println(tree.contains(1)); // 输出true
    }
}

关键修改说明 #

• 新增BstNode current = this.root;，用临时变量遍历树，彻底避免修改类的根节点引用
• 提取compareResult变量，减少重复的比较计算，提升代码可读性
• 调整循环逻辑为while(true)，逻辑更清晰：只要没找到插入位置或重复元素，就持续遍历

内容的提问来源于stack exchange，提问作者amjad salih