중복 검색 트리에 중복을 허용하지 않으려면 어떻게합니까?

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 items=new HashSet(); 

Answer 2

는 equals와 일관성 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. 
} 

---

은을 변경, 문제의 하반기를 해결하려면메서드를 사용하여 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. 
}