向 BST 中插入一个节点

Question

我用于将节点插入 BST 的代码无法正常工作。当我尝试显示时，它只显示树的最后两个节点，即它以某种方式覆盖了树中的节点。我做错了什么？提前致谢！

public Node Insert(int value)
    {
        Node newNode = new Node();
        newNode.data = value;
        newNode.left = null;
        newNode.right = null;

        if(root == null){
            root = newNode;
            return root;
        }
        else{
            while(root != null){
                if(root.data < value){
                    if(root.right != null){
                        root = root.right;
                    }
                    else{
                        root.right = newNode;
                        break;
                    }
                }
                else{
                    if(root.left != null){
                        root = root.left;
                    }
                    else{
                        root.left = newNode;
                        break;
                    }

                }
            }
            return root;
        }

    }
    public void inOrder(){
        inOrder(this.root);
    }
    private void inOrder(Node root){
        if(root != null){
            inOrder(root.left);
            System.out.println(root.data);
            inOrder(root.right);
        }
    }

Answer 1

root 指向树的顶部节点。在你改变它的价值的同时。您必须使用另一个变量（比如 'n'）。

'n'的初始值为'root'。而在 while 内你只使用 'n'.

if(root == null){
        root = newNode;
        return root;
    }
    else{
        Node n = root;
        while(n != null){
        ...
        }
        return root;
        ...

您必须 return 'root'，而不是 'n'，因为根不会更改。

Answer 2

请参阅我在代码中的注释。希望对你有帮助。

public Node Insert(int value)
{
    Node newNode = new Node();
    newNode.data = value;
    newNode.left = null;
    newNode.right = null;

    if(root == null){
        root = newNode;
        return root;
    }
    else{
        while(root != null){
            if(root.data < value){
                if(root.right != null){
                    root = root.right;
                    // root should point to the head of the tree.
                    /* Here you are changing the variable root to point to some other memory location and the reference to the head of the tree is lost. You should store the reference to the head of the tree in a temporary variable to return later  */
                }
                else{
                    root.right = newNode;
                    break;
                }
            }
            else{
                if(root.left != null){
                    root = root.left;
                   //root should point to the head of the tree.
                    /* Here you are changing the variable root to point to some other memory location and the reference to the head of the tree is lost. You should store the reference to the head of the tree in a temporary variable to return later  */
                }
                else{
                    root.left = newNode;
                    break;
                }

            }
        }
        // return temporary variable which points to the head of the tree here
        return root;
    }

}
public void inOrder(){
    inOrder(this.root);
}
private void inOrder(Node root){
    if(root != null){
        inOrder(root.left);
        System.out.println(root.data);
        inOrder(root.right);
    }
}

向 BST 中插入一个节点

Inserting a node into a BST

java

algorithm

tree

binary-search-tree