目前,我正在使用BST,虽然我觉得这很合逻辑,但是我的插入方法存在一些问题。调试之后,我发现我使用的变量分配存在问题,就像每次尝试插入节点一样,它都会作为根插入,因此会打印出来,“不允许重复”。
为此,我正在分别处理4个类。 BinarySearchTree类中的以下方法扩展了BinaryTree类。在二叉树类中,我有一个受保护的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()
方法开始。
for (int i = 1; i <= numElt; i++) {
System.out.print("Enter next element ");
num = input.nextInt();
x.setNum(num);
tree.insert(x);
}
遍历元素时,您只是在更改单个
DataElement
对象(x
)的值。当您将此
insert
对象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))
这应该按值而不是按引用检查它们。