从整数串构造一个二叉查找树

Question

在包含 main 函数的类中，定义一个函数调用 createTree（String strKey）。给出一个整数字符串（用空格字符分隔），此函数将创建一个 BST 树，其中整数键跟在输入字符串之后。示例：给定一个字符串 s = “30 20 40”。调用函数 createTree（s） 来创建二叉搜索树：root = 30，root.left = 20，root.right = 40。以下是我的代码：

• 节点.java

public class Node {
    Integer key;
    Node left, right;
    
    public Node(Integer key){
        this.key = key;
        this.left = this.right = null;
    }
}

• 英国夏令时.java

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

    public 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;
    }
}

< li>Test.java

public class Test {
    
    public static BST createTree(String strKey){
        String[] spl = strKey.split(" ");
        BST tree = new BST();
        Node root = null;
        for (int i=0; i<spl.length; i++){
            Integer key = Integer.parseInt(spl[i]);
            tree.insert(root,key);
        }
        return tree;
    }
    
    public static void main(String[] args){
        String s = "20 30 40";
        BST tree = createTree(s);
        System.out.println(tree.getRoot());
    }
}

结果也是空的（根为空），我不知道为什么键没有插入到树中。希望你们能帮我解决这个问题。谢谢

Answer 1

if (x == null){
    return new Node(key);
}

返回的节点未分配给BST类中的根。此外，您在createTree方法中有根。

您可以将其更改为包含重载的插入函数，该函数仅接受要插入的整数并将现有整数设为私有。

private Node insert(Node x, Integer key){
    //your existing code
}

public void insert(Integer key) {
    this.root = insert(this.root, key);
}

有了这个，根将在第一次创建时更新。

从createTree调用一个参数insert方法。

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