이진 검색 트리에서 노드 삭제

Question

deleteNode 메서드를 호출하면 My Binary Search Tree 프로그램이 아무 것도 삭제하지 않는 것 같습니다. BST는 완벽하게 구축되어 작동하지 않는 노드 부분 만 삭제합니다. 나는 다음과 같은 내 deleteNode 메소드를 구현 내 BinarySearchTree 클래스에서

System.out.println("Please enter a number you would like to delete from the tree"); 
    temp = reader.nextLine(); 
    try { 
     int numTemp = Integer.parseInt(temp); 
     TreeNode treeTemp = bst.deleteNode(numTemp, bst.getRoot()); 
     bst.setRoot(treeTemp); 
    } 
    catch(Throwable e){ 
     System.err.println(e); 
    } 
    bst.printInBST(bst.getRoot()); 

: :이처럼 내 메인에서 호출이 유일한 문제가 확실

public TreeNode deleteNode(int x, TreeNode temp){ 
    if(temp != null){ 
     if(x > (int)((Integer)temp.getValue())){ 
      temp.setLeft(deleteNode(new Integer(x), temp.getLeft())); 
     } 
     else if(x < (int)((Integer)temp.getValue())){ 
      temp.setRight(deleteNode(new Integer(x), temp.getRight())); 
     } 
     else if(temp.getLeft() != null & temp.getRight() != null){ 
      TreeNode temp2 = new TreeNode(temp.getRight().getValue()); 
      while(temp2.getLeft() != null){ 
       temp2 = temp2.getLeft(); 
      } 
      temp = temp2; 
      temp.setRight(remove(temp.getRight())); 
     } 
    } 
    return temp; 
} 
public TreeNode remove(TreeNode temp){ 
     if(temp.getLeft() != null){ 
      temp.setLeft(remove(temp.getLeft())); 
      return temp; 
     } 
     else { 
      return temp.getRight(); 
     } 
} 

Answer 1

100 %,하지만 수행해야합니다

else if(temp.getLeft() != null & temp.getRight() != null) 

실제로 수 :

else if(temp.getLeft() != null && temp.getRight() != null) 

즉 두 개가 있어야 할 때 "and"작업에 대해 하나만 &이 있습니까? 삭제 노드가 다른 단지 한 아이

---

을 가지고 다음 삭제 노드가 잎 노드를

경우 2 :

Answer 2

나는 당신이

경우 1을 처리하지 생각 부품이 이런 식으로 있어야합니다.

else if(temp.getLeft() != null && temp.getRight() != null) // Two children 
{ 
     temp.setValue(findMin(temp.getRight()).getValue()); 
     temp.setRight (deleteNode(temp.getValue(), temp.getRight()); 
} 
else 
    temp = (temp.getLeft() != null) ? temp.getLeft() : temp.getRight(); 

return temp; 

---

findMin 방법은 노드의 중위 후속 삭제 될 찾을 수 있습니다.

private TreeNode findMin(TreeNode t) 
{ 
     if(t == null) 
      return null; 
     else if(t.getLeft() == null) 
      return t; 
     return findMin(t.getLeft()); 
} 

---

나는이 질문에 대한 답변 바랍니다.

Answer 3

읽을 수있는 코드를 작성하면 버그가 자신과 다른 사람이 쉽게 발견 할 수 있습니다. 첫 번째 단계는 temp, temp2 및 treeTemp보다 더 표현 변수 이름을 선택하는 것입니다.

또한 new Integer(x)을 입력하여 int 유형의 매개 변수를 할당 할 필요가 없습니다. 단순히 x을 쓰는 것만으로도 동일한 효과를 가지며 런타임이 빠르며 중요한 코드를 쉽게 찾을 수 있습니다.

버그에 관해서는, 내가 보는 첫 번째는 다음의 TreeNode의 복사본을 생성

TreeNode temp2 = new TreeNode(temp.getRight().getValue()); 

. 해당 사본을 변경해도 원래 노드에는 영향을주지 않습니다. 또한 value 만 생성자에 전달했기 때문에 사본에는 left 또는 right 세트가 없을 것입니다. 왜 사본이 필요하다고 생각하니? 결국, 당신은 여기에 하나를 생성하지 않는 중 하나

deleteNode(new Integer(x), temp.getRight()) 

다음, Sashwat가 지적으로 삭제하는 노드가 2 이하 아이가있는 경우, 코드는 조건 없음으로, 아무것도하지 않습니다 deleteNode과 일치합니다.

Answer 4

public class BSTNode { 
    … 

    public boolean remove(int value, BSTNode parent) { 
     if (value < this.value) { 
       if (left != null) 
        return left.remove(value, this); 
       else 
        return false; 
     } else if (value > this.value) { 
       if (right != null) 
        return right.remove(value, this); 
       else 
        return false; 
     } else { 
       if (left != null && right != null) { 
        this.value = right.minValue(); 
        right.remove(this.value, this); 
       } else if (parent.left == this) { 
        parent.left = (left != null) ? left : right; 
       } else if (parent.right == this) { 
        parent.right = (left != null) ? left : right; 
       } 
       return true; 
     } 
    }