이진 검색 트리 : Java를 사용하여 주어진 값 x 재귀 적으로 TreeNode를 제거하십시오.

Question

Java에서 주어진 입력 값 int x를 포함하는 경우 이진 탐색 트리 내의 노드를 제거하는 비 재귀 적 메소드를 작성하려고합니다. 내가 스택을 사용해야하지만 그 자체로 함수를 호출하지 않고 노드를 제거하는 방법을 알아낼 수 없다는 것을 알았습니다.

이것은 현재 내 TreeNode 클래스입니다.

class TreeNode { 

    private int data;    // data item (key) 
    private TreeNode left;   // this node's left child 
    private TreeNode right;  // this node's right child  

    // The "external node" is a special node that acts as a sentinel. 

    private final static TreeNode externalnode = TreeNode.createExternalNode(); 

    /* Return a TreeNode that represents an "external node"*/ 
    public static TreeNode getExternalNode() { 
      return externalnode; 
    } 

    /* Creates a new TreeNode with no children. 
     */ 
    public TreeNode(int id) {  // constructor 
      data = id; 
      left = externalnode; 
      right = externalnode; 

    } 

나는 이것을 시도했지만 작동하지 않습니다.

public TreeNode removeB(int x){ 
    if (this == externalnode) return externalnode; 
    TreeNode one = new TreeNode(this.data); 
    System.out.println(this); 
    Stack<TreeNode> s = new Stack();  
    s.push(one); 
    //System.out.println(s); 
    boolean check; 
    boolean check1; 
    while(check = true){ 
     if(x == one.left.data){ 
      System.out.println(one.left.data); 
      check = false; 
      return one.left; 
     } 


     if(x == one.right.data){ 
      System.out.println(one.right.data); 
      check1 = false; 
      return one.right; 
    } 
    } 

Answer 1

코드에서 먼저 제거 할 노드를 찾으려면 이진 검색을 수행해야합니다. 당신이 노드, 당신은 추가하는 것처럼, 그 아래에 다른 고아 아이에 이식 한 후, 아이의로 교체하고 있음을 대상으로하면

while (currentNode != null && currentNode.value != target) { 
    if (currentNode.value > target) { 
    currentNode = currentNode.left; 
    } else if (currentNode.value < target) { 
    currentNode = currentNode.right; 
    } 
} 

: 의사 코드에서는 같이 보입니다 모든 노드.