從Java中的二進制搜索樹中刪除

我找不到我的刪除算法出了什麼問題。當我在BST的根上運行我的刪除方法時，它將用右子樹的最小值替換根，但此後不刪除節點。從Java中的二進制搜索樹中刪除

public void delete(BinaryTreeNode node, int x){ 
    if (node==null) 
     return; 
    else if (x<node.getKey()) 
     delete(node.getLeftChild(),x); 
    else if (x>node.getKey()) 
     delete(node.getRightChild(),x); 
    else{ 
     if (node.getLeftChild()==null) 
      node = node.getRightChild(); 
     else if (node.getRightChild()==null) 
      node = node.getLeftChild(); 
     else{ 
      BinaryTreeNode temp = findMin(node.getRightChild()); 
      System.out.println(temp.getKey() + " " + node.getKey()); 
      node.setKey(temp.getKey()); 
      System.out.println(temp.getKey() + " " + node.getKey()); 
      delete(node.getRightChild(), node.getKey()); 
     } 
    } 
}

和我的findMin（）方法：

public BinaryTreeNode findMin(BinaryTreeNode node){ 
    if (node.getLeftChild()==null) 
     return node; 
    else 
     return findMin(node.getLeftChild()); 
}

對於包含的所有整數1-9具有4根一BST，我的用於inorderPrint（）輸出產生

1,2,3,5,5,6,7,8,9

而不是

1,2,3,5,6,7,8,9

來源

2014-04-18 user1901074

做你'findMin（...）'方法迭代而不是遞歸。 –

@CyberneticTwerkGuruOrc一個沒有連接問題，我懷疑它會反正大多數編譯器都會優化，因爲這是尾遞歸。在這種情況下，我發現遞歸解決方案更具可讀性。 – amit

@amit顯然它沒有連接到問題。這就是爲什麼我把它發佈爲評論而不是答案。即使編譯器在這種情況下處理它，OP也許應該學習以遞歸方式迭代地執行* most *方法（除非學習遞歸）。 –

當設置node = node.getLeftChild();（或symetrically node = node.getRightChild();要更改局部變量node的價值，而不是引用來自父親這個節點

你失去了一些東西，如：。node.father.left = ....（或node.father.right = ...）。
您應該更改值樹本身，你的方法持有不僅引用。

來源

2014-04-18 20:44:59 amit

更新您的已刪除節點的父節點的指針與正確的節點。您需要擺脫已刪除節點的任何痕跡。有一個臨時節點來跟蹤父節點，因此，一旦找到要刪除的節點，就會更容易。

來源

2014-04-18 20:44:21

從Java中的二進制搜索樹中刪除

回答

相關問題