이진 검색 트리에 중복 인쇄가 발생했습니다.

Question

중복이 포함되지 않도록 이진 트리를 구현하고 싶습니다. 여기에 내 insert() 메소드가있다.

public BinaryNode insert(BinaryNode node, int x) { 

    if (node == null) { 
     node = new BinaryNode(x); 
    } else if (x < node.element) { 
     node.left = insert(node.left, x); 
    } else if (node.element < x) { 
     node.right = insert(node.right, x); 
    } else { 
     System.out.println("Duplicates not allowed"); 
     return null; 
    } 

    return node; 
} 


public static void main (String args[]) { 
    BinaryTree t = new BinaryTree(); 
    t.root=t.insert(t.root, 5); 
    t.insert(t.root, 6); 
    t.insert(t.root, 4); 
    t.insert(t.root, 60); 
    t.insert(t.root, 25); 
    t.insert(t.root, 10); 
    t.insert(t.root, 10); 

왜이 이진 트리에 인쇄되는 중복 (10)이다. 나는 else 문에서 return null이 중복이 발견되었을 때 재귀를 멈추게한다고 생각했다. 10을 다시 넣으면 "Duplicates not allowed"이 인쇄되지만 거기에서 멈추지 않고 두 번째 시간에 10을 더합니다.

Answer 1

솔루션 :

원래 코드에서 줄 return null;를 제거합니다.

public BinaryNode insert(BinaryNode node, int x) { 

    if (node == null) { 
     node = new BinaryNode(x); 
    } else if (x < node.element) { 
     node.left = insert(node.left, x); 
    } else if (node.element < x) { 
     node.right = insert(node.right, x); 
    } else { 
     System.out.println("Duplicates not allowed"); 
    } 

    return node; 
} 

설명 : 모든 노드를 추가 한

, 당신이 나무는 다음과 같이보고했다 :

 5 
    4  6 
       60 
      25 
     10 

이것은 당신이 남아 있어야 코드입니다 귀하의 코드에 대한 하나의 문제는 중복을 직면 할 때 null을 반환한다는 것입니다. (노드 25에서 호출)이 코드

node.left = insert(node.left, x); 

는 다음의에게 즉이

node.left = null; 

를 얻을; 중복에 대해 null을 반환하면 기존 노드를 지 웁니다. 그리고 내가 볼 수있는 한, 새로운 것이 삽입되지 않습니다. 따라서 복제본의 경우 기존 노드를 삭제하면됩니다. 그러나 "Duplicates not allowed"이 인쇄됩니다.

그러나 return null;을 삭제하면 기존의 10 개 노드가있는 그대로 유지됩니다. 그리고 새로운 10은 무시 될 것입니다.

Answer 2

내가 말할 수있는 한 다른 게시물은 정확하지만 몇 가지 변경 사항을 제안합니다.

우선 -이 라인

t.root=t.insert(t.root,5);

은

t.insert(5); 

빈 나무가 당신의 재귀 삽입의 첫 번째 반복에 null이됩니다되어야한다. 귀하의 생성자는 단지

BinaryTree t = new BinaryTree(); 

이어야하며 BinaryTree 클래스는 구성원 노드 변수가 루트 여야합니다.