java - 二叉树插入 3

Question

我正在尝试编写自己的二叉树，但插入时遇到问题。树中的值是重复的。我有带有“节点右、左和 int 值”字段的内部静态类 Node 和带有一个字段的外部类 BinaryTree - 节点根。

插入代码：

public void insert(int number) {
    if (root.isEmpty())
        root.value = number;
    else {
        Node node = root;
        insert(number, node);
    }
}

private void insert(int number, Node node) {
    if (number < node.value && node.left != null) {
        node = node.left;
        insert(number, node);
    } else {
        if (node.left == null)
            node.left = new Node(null, null, number);
    }

    if (number > node.value && node.right != null) {
        node = node.right;
        insert(number, node);
    } else {
        if (node.right == null)
            node.right = new Node(null, null, number);
    }
}

我做错了什么？

Answer 1

假设您有一个名为 X 的节点作为根。您正在插入一些数字

if (number < node.value && node.left != null) {
    node = node.left; // NODE IS NOW Y
    insert(number, node);
} 

现在它进入下一个 if 语句

if (number > node.value && node.right != null) {
    node = node.right;
    insert(number, node);
} else {
    if (node.right == null)
        node.right = new Node(null, null, number);
}

节点现在等于 Y 并且没有子节点。所以 node.right==null。所以这个数字被重新插入为 Y 的右孩子。

所以存在该号码的副本。使用 return 解决它。

private void insert(int number, Node node) {
    if (number < node.value && node.left != null) {
        node = node.left;
        insert(number, node);
        return;
    } 
    else {
        if (node.left == null)
            node.left = new Node(null, null, number);
        return;
    }

    if (number > node.value && node.right != null) {
        node = node.right;
        insert(number, node);
        return;
    }
    else {
        if (node.right == null)
            node.right = new Node(null, null, number);
        return;
    }
}