Java의 이진 검색 트리에서 삭제

삭제 알고리즘에 문제가있는 것을 찾을 수 없습니다. BST의 루트에서 delete 메소드를 실행하면 루트가 하위 트리의 최소값으로 바뀌지 만 이후에는 노드가 삭제되지 않습니다.Java의 이진 검색 트리에서 삭제

public void delete(BinaryTreeNode node, int x){ 
    if (node==null) 
     return; 
    else if (x<node.getKey()) 
     delete(node.getLeftChild(),x); 
    else if (x>node.getKey()) 
     delete(node.getRightChild(),x); 
    else{ 
     if (node.getLeftChild()==null) 
      node = node.getRightChild(); 
     else if (node.getRightChild()==null) 
      node = node.getLeftChild(); 
     else{ 
      BinaryTreeNode temp = findMin(node.getRightChild()); 
      System.out.println(temp.getKey() + " " + node.getKey()); 
      node.setKey(temp.getKey()); 
      System.out.println(temp.getKey() + " " + node.getKey()); 
      delete(node.getRightChild(), node.getKey()); 
     } 
    } 
}

내 findMin() 메소드

public BinaryTreeNode findMin(BinaryTreeNode node){ 
    if (node.getLeftChild()==null) 
     return node; 
    else 
     return findMin(node.getLeftChild()); 
}

(4)의 루트로 모든 정수 1-9 함유 BST 들어 inorderPrint() 내 출력

1,2,3,5,5,6,7,8,9

수득

1,2,3,5,6,7,8,9

출처

2014-04-18 user1901074

당신의'findMin (...)'방법을 수행 반복적으로 대신 재귀. 아무 관련이 없습니다 –

@CyberneticTwerkGuruOrc을 문제가 생기면 이것이 꼬리 재귀이기 때문에 어쨌든 대부분의 컴파일러에 의해 최적화됩니다. 이 경우 재귀 적 솔루션을 더 읽기 쉽다고 생각합니다. – amit

@amit 분명히 문제와 관련이 없습니다. 그래서 대답 대신 댓글로 게시했습니다. 이 경우 컴파일러가 처리하더라도 OP는 재귀 적으로 반복적으로 * 대부분의 * 메소드를 수행하는 방법을 배워야합니다 (재귀를 연구하지 않는 한). –

당신이 node = node.getLeftChild();을 설정하는 (또는 symetrically node = node.getRightChild(); 로컬 변수 node의 값을 변경하는, 그리고 아버지로부터이 노드에 대한 참조

당신은 뭔가를 누락 :. node.father.left = .... (또는 node.father.right = ...) .
당신은 나무 자체의 값을 변경해야하고,뿐만 아니라 참조 당신은 방법을 누르십시오.

출처

2014-04-18 20:44:59 amit

대신 삭제 된 노드의 부모 포인터를 올바른 노드와 비교합니다. 삭제 된 노드의 흔적을 제거해야합니다. 부모 노드를 추적하는 임시 노드가 있으므로 삭제할 노드를 찾으면 쉽게 수행 할 수 있습니다.

출처

2014-04-18 20:44:21

Java의 이진 검색 트리에서 삭제

답변

관련 문제