java - 插入二叉搜索树

Question

我通过以下方式插入 BST :

private void BSTinsert(int toInsert){
        if(root==null){
            root = new Node(toInsert);
            return;
        }
        Node tempRoot = root;
        while(tempRoot!=null){
            if(tempRoot.data > toInsert){
                tempRoot = tempRoot.left;
            }else{
                tempRoot = tempRoot.right;
            }
        }
        tempRoot = new Node(toInsert);
}

但是当我尝试从根打印树时，它会抛出空指针异常。但是，当我尝试在插入时打印出 tempRoot 时，它会正确打印出来，但 root 和 tempRoot 不是同一件事，因为我已经将它们等同了？我在这里缺少什么？

Answer 1

tempRoot 是一个局部变量，因此当您将新节点分配给它时，现有树中没有任何内容引用它。新节点应链接到其父节点(通过 left 或 right 引用)。

当前您的代码仅正确插入第一个节点，因为该节点成为根。

建议的更正(未经测试):

private void BSTinsert(int toInsert){
    if(root==null){
        root = new Node(toInsert);
        return;
    }
    Node tempRoot = root;
    while(tempRoot!=null){
        if(tempRoot.data > toInsert){
            if (tempRoot.left == null) {
                tempRoot.left = new Node(toInsert);
                return;
            } else {
                tempRoot = tempRoot.left;
            }
        }else{
            if (tempRoot.right == null) {
                tempRoot.right = new Node(toInsert);
                return;
            } else {
                tempRoot = tempRoot.right;
            }
        }
    }
}