バイナリ検索ツリー：指定された値xを持つTreeNodeをJavaを使用して再帰的に削除します。

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; 
    } 
} 

を、あなたはその子のものと交換し、その後、追加するのと同様に、その下に他の孤立した子にグラフト任意のノード。