如何不允許將重複項添加到二進制搜索樹中？

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. 
}