二叉搜索树：使用Java非递归地删除具有给定值x的TreeNode

Question

我正在尝试编写一个非递归方法，如果二进制搜索树中包含Java中给定的输入值intx，则该方法将删除该树中的节点。我想我需要使用一个堆栈，但似乎不知道如何在不调用自身函数的情况下删除节点

这是我现在的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;
  }
}

一旦确定了该节点的目标，就用它的一个子节点替换它，然后在它下面移植另一个孤立子节点，就像添加任何节点一样