java - 在二叉搜索树上打印重复项

Question

我想实现一个二叉树，使其不包含重复项。这是我的 insert() 方法。

public  BinaryNode insert(BinaryNode node, int x) {

    if (node == null) {
        node = new BinaryNode(x);
    } else if (x < node.element) {
        node.left = insert(node.left, x);
    } else if (node.element < x) {
        node.right = insert(node.right, x);
    } else {
        System.out.println("Duplicates not allowed");
        return null;
    }

    return node;
}


public static void main (String args[]) {
    BinaryTree t = new BinaryTree();
    t.root=t.insert(t.root, 5);
    t.insert(t.root, 6);
    t.insert(t.root, 4);
    t.insert(t.root, 60);
    t.insert(t.root, 25);
    t.insert(t.root, 10);
    t.insert(t.root, 10);

为什么在这个二叉树中打印重复的 10。我认为 else 语句中的 return null 会在发现重复项时停止递归。当再次插入 10 时，它会打印出“不允许重复”，但不会从那里停止，它还会继续第二次添加 10。

Answer 1

解决方案:

从原始代码中删除行return null;。这是您应该保留的代码:

public BinaryNode insert(BinaryNode node, int x) {

    if (node == null) {
        node = new BinaryNode(x);
    } else if (x < node.element) {
        node.left = insert(node.left, x);
    } else if (node.element < x) {
        node.right = insert(node.right, x);
    } else {
        System.out.println("Duplicates not allowed");
    }

    return node;
}

说明:

添加所有节点后，您将得到一棵如下所示的树:

        5
    4       6
                60
            25
        10

您的代码的一个问题是，当遇到重复项时，您将返回 null。此代码(从节点 25 调用)

node.left = insert(node.left, x);

然后得到这个

node.left = null;

换句话说；当您为重复项返回 null 时，您将删除现有节点。据我所知，新的尚未插入。因此，如果存在重复节点，您最终只需删除现有节点即可。但是，它会打印“不允许重复”。

如果您删除return null;，现有的 10 个节点将保持原样。新的 10 将被忽略。