二叉搜索樹：給定值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

回答

相關問題