Java中使用String作为二叉搜索树（BST）键的问题求助

看起来你遇到的核心问题是：BST只保留了第一个插入的节点（值为A），后续插入的节点根本没被正确加入树中，导致搜索时返回null。从你贴的addNode方法片段来看，问题大概率出在未完成正确的BST插入遍历逻辑——你只处理了根节点为空的情况，后续的节点插入逻辑缺失或错误，导致新节点没被放到树的正确位置上。

先看你现有的代码片段：

public void addNode(String key, String name) { 
    // Create a new Node and initialize it 
    Node newNode = new Node(key, name); 
    // If there is no root this becomes root 
    if (root == null) { 
        root = newNode; 
    } else { 
        // Set root as the Node we will start 
        // with as we traverse the...
        // 这里的遍历插入逻辑缺失/错误！
    }
}

问题根源 #

BST的插入逻辑核心是根据键的大小递归/迭代找到空的子节点位置：对于String类型的键，需要用compareTo()方法比较字典序，决定新节点该放在当前节点的左子树还是右子树，直到找到一个空的左/右叶子位置，才能把新节点挂上去。如果你的代码在else块里没有完成这个遍历过程，后续节点根本没被插入到树中，自然搜不到。

修正后的完整实现示例 #

下面是修复后的addNode方法，搭配对应的搜索方法，保证节点能正确插入和查找：

public class BST {
    private Node root;

    // 内部节点类
    private class Node {
        String key;
        String name;
        Node left;
        Node right;

        public Node(String key, String name) {
            this.key = key;
            this.name = name;
            this.left = null;
            this.right = null;
        }
    }

    public void addNode(String key, String name) {
        Node newNode = new Node(key, name);

        // 根节点为空时直接设为根
        if (root == null) {
            root = newNode;
            return;
        }

        Node current = root;
        Node parent = null;

        // 迭代遍历找到插入位置
        while (true) {
            parent = current;
            // 用String的compareTo比较字典序，不能直接用==或< >
            int compareResult = key.compareTo(current.key);

            if (compareResult < 0) {
                // 新键更小，去左子树找位置
                current = current.left;
                if (current == null) {
                    parent.left = newNode;
                    return;
                }
            } else if (compareResult > 0) {
                // 新键更大，去右子树找位置
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    return;
                }
            } else {
                // 遇到重复键，这里选择覆盖原有值，也可以抛异常/忽略
                current.name = name;
                return;
            }
        }
    }

    // 对应的搜索方法
    public String searchNode(String key) {
        Node current = root;

        while (current != null) {
            int compareResult = key.compareTo(current.key);
            if (compareResult < 0) {
                current = current.left;
            } else if (compareResult > 0) {
                current = current.right;
            } else {
                // 找到匹配的键，返回对应值
                return current.name;
            }
        }
        // 遍历完没找到，返回null
        return null;
    }
}

关键注意点 #

1. String键的比较：必须用compareTo()方法，不能用==（==比较的是对象引用，不是字符串内容），也不能直接用</>运算符。
2. 遍历逻辑完整性：一定要循环到找到空的子节点位置再插入，不能中途停止或错误挂载节点。
3. 重复键处理：如果插入重复键，示例中选择覆盖原有值，你可以根据需求改成抛出异常或忽略插入。

现在测试一下：先调用addNode("key1", "A")，再插入addNode("key2", "B")、addNode("key0", "C")，调用searchNode("key2")会返回"B"，searchNode("key0")返回"C"，不会再出现null的情况。

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