如何不允许将重复项添加到二进制搜索树中？

Question

我一直想弄清楚如何编辑我的给定代码，如果它已经存在，它将不允许元素进入我的二叉树。我的提示是修改测试器以外的两个不同的类来完成。

我第一类是：

public void addNode(Node <T> newNode){ 
     Comparable<T> tempElement = (Comparable<T>) newNode.element; 

     int comp = tempElement.compareTo(element); 
      if (comp < 0) 
      { 
      if (left == null) 
       {left = newNode;} 
      else 
       {left.addNode(newNode);} 
      } 
      else 
      { 
      if (right == null) 
       {right = newNode;} 
      else 
       {right.addNode(newNode);} 

      } 
    } 

而第二个是：

public void add(T obj) // add root first 
    { 
     Node<T> newNode = new Node<T>(obj); 
     if (root == null) { 
      root = newNode; 
     } else { 
      root.addNode(newNode); 
     } 
     count++; 

    } 

如果有人可以帮助我将不胜感激！

Answer 1

尝试将您的项目添加到Set中，因为集合只允许一个项目相等的实例。

Set items=new HashSet(); 

Answer 2

假设您正在使用与等于一致的Comparable实例;那就是：

a.compareTo(b) == 0 

在当前的代码来实现这一点的最简单方法就是检查的comp值：

a.compareTo(b) == 0 iff a.equals(b) 

然后，你可以简单地通过检查的情况下消除重复

if (comp < 0) 
{ 
    // Insert to the left, as you currently do. 
} 
else if (comp > 0) 
{ 
    // Insert to the right, as you currently do. 
} 
else 
{ 
    // Handle the duplicate: maybe do nothing, maybe throw an exception etc. 
    // If you want to do nothing, you don't need the else block at all. 
} 

---

为了解决这个问题的后半部分，改变你addNode返回boolean的方法，其中true表示已添加节点，而false则不是。

然后：

Node<T> newNode = new Node<T>(obj); 
if (root == null) { 
    root = newNode; 
    count++; // "added" unconditionally. 
} else { 
    if (root.addNode(newNode)) count++; // Only increment if it was really added. 
}