Java从整数字符串构建二叉搜索树返回根节点为null问题求助

问题原因 #

• 你实现的insert递归方法会返回插入操作完成后的子树根节点，但调用时没有接收返回值，也没有将返回的根节点赋值给BST实例的root成员变量，导致BST内部的root始终保持初始化的null值。
• createTree方法里定义的局部root变量全程没有被赋值，每次调用insert传入的都是null，插入结果也没有回写到BST实例中。

修复方案 #

第一步：修改BST类，增加对外暴露的插入方法 #

不用外部传入节点，直接操作内部的root属性，同时把原递归插入方法改为私有，封装内部实现：

public class BST {
    
    private Node root;
    
    public BST(){
        this.root = null;
    }
    
    public Node getRoot(){
        return this.root;
    }

    // 原有递归插入方法改为私有
    private Node insert(Node x, Integer key){
        if (x == null){
            return new Node(key);
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0){
            x.left = insert(x.left,key);
        }
        else if (cmp > 0){
            x.right = insert(x.right,key);
        }
        else {
            x.key = key;
        }
        return x;
    }

    // 新增对外调用的插入方法
    public void insert(Integer key) {
        this.root = insert(this.root, key);
    }
}

第二步：修改Test类的createTree方法 #

删除无用的局部root变量，直接调用BST封装好的插入方法：

public class Test {
    
    public static BST createTree(String strKey){
        String[] spl = strKey.split(" ");
        BST tree = new BST();
        for (int i=0; i<spl.length; i++){
            Integer key = Integer.parseInt(spl[i]);
            tree.insert(key);
        }
        return tree;
    }
    
    public static void main(String[] args){
        String s = "20 30 40";
        BST tree = createTree(s);
        // 输出根节点key验证结果：20
        System.out.println(tree.getRoot().key);
        // 输出根节点右子节点key验证结果：30
        System.out.println(tree.getRoot().right.key);
    }
}

运行结果 #

修改后运行main方法，将依次输出20、30，说明BST构建成功，根节点不再为null。

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