이진 검색 트리에서 요소 삭제

현재 이진 검색 트리에서 주어진 값을 제거하는 방법을 쓰고 있습니다. 그러나 내가 그것을 부를 때, 그것은 상기 값을 삭제하지만 다른 모든 값을 복제한다. 나는 이유를 모른다. 잘못된 점을 말해주십시오. 두 가지 방법이 있습니다. 하나는 요소를 찾고 다른 하나는 요소를 삭제하는 방법입니다. 여기 이진 검색 트리에서 요소 삭제

public static TreeNode delete(TreeNode t, Comparable x, TreeDisplay display) 
{ 
    if(x.compareTo(t.getValue()) > 0) 
     { 
      display.visit(t); 

      t.setRight(delete(t.getRight(), x, display)); 

    } 
    else if (x.compareTo(t.getValue()) < 0) 
    { 
     display.visit(t); 

     t.setLeft(delete(t.getLeft(), x, display)); 
    } 
    else 
    { 
     t = deleteNode(t, display); 
    } 

    return t;

이

사전에 값을

private static TreeNode deleteNode(TreeNode t, TreeDisplay display) 
    { 

    if (t.getRight()!=null) 
    { 
     TreeNode right = t.getRight(); 
     TreeNode max = (TreeNode)TreeUtil.leftmost(right); 
     TreeNode previous = null; 
     while (right.getLeft()!=null&&right.getLeft().getLeft()!=null) 
     { 
      right = right.getLeft(); 
     } 
     t.setValue(max.getValue()); 
     if (max.getRight()==null) 
     { 
      right.setLeft(null); 
     } 
     else 
     { 
      right.setLeft(max.getRight()); 
     } 
    } 
    else if (t.getLeft() !=null) 
    { 
     TreeNode left = t.getLeft(); 
     TreeNode max = (TreeNode)TreeUtil.rightmost(left); 
     while(left.getRight()!=null &&left.getRight().getRight()!=null) 
     { 
      left = left.getRight(); 
     } 
     t.setValue(max.getValue()); 
     if (max.getLeft()==null) 
     { 
      left.setRight(null); 
     } 
     else 
     { 
      left.setRight(max.getLeft()); 
     } 
    } 
    else 
    { 
     t = null; 
    } 
    return t; 
}

감사를 삭제하는 방법입니다 ... 그 요소를 발견 하나입니다!

출처

2014-12-15 Robert

이런 종류의 디버거가 유용합니다. 코드 실행을 단계별로 실행하여 실제로 잘못된 작업을 확인할 수 있습니다. 또한 deleteNode에서 새 값을 반환하도록 설정하지 않습니다. 당신은 t를 반환하지만 t는 결코 수정되지 않습니다. 예 : '''t = t.getLeft()'''어딘가에 있어야합니다. – kristianp

박쥐 오른쪽에서 불필요하게 너무 복잡해 보이는 것처럼 보입니다. 당신이 그 일을하는 방법을 아는 것처럼 보이는 적절한 노드를 얻으십시오. 그런 다음 maxLeft 또는 minRight 노드를 삭제하십시오. 너무 많은 수표와 변화가 너무 단순 해 보이는 것처럼 보입니다. – ChiefTwoPencils

...이 값을 삭제하지만 다른 모든 값은 중복됩니다. 나는 이유를 모른다. 잘못된 점을 말해주십시오.

당신이 deleteNode()에서 삭제 된 노드를 반환하고, 그리고 재귀 다시 나무 위로 풀릴 첫 번째 방법 delete()에, setRight() 및 setLeft()에 통화가 삭제 된 요소에 모든 횡단 요소를 설정하는 때문입니다.

출처

2014-12-15 01:38:56 gknicker

이진 검색 트리에서 요소 삭제

답변

관련 문제