二叉搜索树：给定值x非递归使用Java

我试图写一个非递归方法，如果它包含给定的输入值INT X在Java中，去除二叉搜索树中的一个节点删除树节点。我想我需要使用堆栈，但似乎无法弄清楚如何在不调用本身的函数的情况下移除节点。二叉搜索树：给定值x非递归使用Java

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

来源

2017-04-13 joe van horn

能否请你包括你有什么到目前为止已经试过，有）对于'的removeNode（'。我的建议是第一实施该方法，该方法被广泛记载，然后以使其适应一个迭代的标准递归溶液。唯一的区别将是搜索节点，在那里你会使用'while'循环而不是递归的过程。实际处理父/子链接逻辑的代码应该非常相似。 – Jameson

@Jameson我已更新并添加了代码 –

您的代码需要先执行二进制搜索才能找到要删除的节点。在伪代码，它看起来是这样的：

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

一旦你有针对性的节点，你它的一个子替换它，然后嫁接在其下的其他孤儿，就像你会增加任何节点。

来源

2017-04-13 13:30:07 phatfingers

二叉搜索树：给定值x非递归使用Java

回答

相关问题