二叉树插入元素 [Java] - 算法问题

Question

我正在学习算法，但不知何故陷入困境。我了解如何实现二叉树，但我的代码（Java）不起作用。

你能解释一下为什么吗？

谢谢！

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