java - 为什么我的 BinarySearchTree 实现总是将插入的元素报告为重复元素？

Question

我目前正在使用 BST，我的插入方法有一些问题，尽管这对我来说似乎很合乎逻辑。调试后，我发现我使用的变量赋值有问题，就像每次我尝试插入一个节点时，它都会作为根插入，因此打印出来，“不允许重复”。

为此，我分别使用 4 个类。以下方法在扩展 BinaryTree 类的 BinarySearchTree 类中。在二叉树类中，我有一个 protected BinaryTreeNode 和其他用于树遍历的方法。

Main 的方法调用:

    int value;
    System.out.println("Number of elements to be inserted: ");
    value = input.nextInt();

    for (int i = 0; i < value; i++) {
        System.out.print("Enter next element ");
        num = console.nextInt();
        x.setNum(num);

        tree.insert(x);
    }

问题出在 main 方法中的方法调用，而不是 inset 本身。

Answer 1

问题出在几个地方。让我们从您的 main() 方法开始。

for (int i = 1; i <= numElt; i++) {
    System.out.print("Enter next element ");
    num = input.nextInt();
    x.setNum(num);

    tree.insert(x);
}

当您遍历元素时，您只是在更改单个 DataElement 对象 (x) 的值。

当您将此 DataElement 对象插入到您的 BST 时，您创建了一个新的 BinaryTreeNode，然后设置对此 的引用DataElement 对象。

BinaryTreeNode node = new BinaryTreeNode();
node.info = insertItem; //Reference set to the object here.

现在，暂时忽略 insert 方法的其余部分，然后返回到您的循环。在下一次迭代中，您将更改 DataElement 对象的值。

但是您刚刚插入的 BinaryTreeNode 包含对同一 DataElement 对象的引用。因此，当您在新迭代中更改值时，最后一个 BinaryTreeNode 也会看到更改。

相反，您需要在循环的每次迭代中创建一个新的 DataElement，并将其传递给 insert() 方法。

所以，

for (int i = 1; i <= numElt; i++) {
    x = new DataElement(...); //... means whatever constructor parameters it takes.
    System.out.print("Enter next element ");
    num = input.nextInt();
    x.setNum(num);

    tree.insert(x);
}

这将为每个 BinaryTreeNode 提供它自己的 DataElement 对象实例。

---

检测重复

等等，还有更多。您将重复项定义为具有相同值的对象，而不是相同的引用。因此还有更多工作要做。

在这里，在您的 insert 方法中，您检查 insertItem 是否与最后一个节点的引用相同。

if (temp.info == insertItem) {
    System.out.println("We can't have duplicates!");
    return;
}

如果你想按值比较它们，你应该使用equals方法:

if (temp.info.equals(insertItem))

这应该按值而不是按引用来检查它们。