二叉树插入元素 - 仅适用于插入根，不适用于任何其他节点

Question

我正在学习算法。我了解如何实现二叉树，但我的

insert

代码不起作用：当我从一棵空树开始并调用

insert

向树中插入一些值时，它只插入根节点，而不插入任何其他节点。

你能解释一下为什么吗？

public class Tree {

    private class Node {
        int value;
        Node leftChild;
        Node rightChild;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node=" + value;
        }
    }

    private Node root;

    public void insert(int value) {
        var node = new Node(value);
        if(root == null) {
            root = node;
            return;
        }

        var current = root;

        while (current != null) {
            if(value > current.value) {
                current = current.rightChild;
            }
            else {
                current = current.leftChild;
            }
        }

        current = node;

    }
}

Answer 1

current = node

不会改变树。看起来您期望当

current

变为

null

时（在到达叶节点的左侧或右侧之后），此分配将更新该叶的左/右字段。那不是真的。此赋值仅影响

current

变量，不会影响其他任何内容。

您需要跟踪您遍历到的叶子，然后更新该叶子的左/右字段。

这是更正后的代码：

public void insert(int value) {
    var node = new Node(value);
    if (root == null) {
        root = node;
        return;
    }

    var current = root;

    while (true) {
        if (value > current.value) {
            if (current.rightChild == null) {
                // Don't make current null, but update its field
                current.rightChild = node;
                break;
            }
            current = current.rightChild;
        }
        else {
            if (current.leftChild == null) {
                // Don't make current null, but update its field
                current.leftChild = node;
                break;
            }
            current = current.leftChild;
        }
    }
}