刪除BST節點（2）

我有BST，當我想從BST刪除節點時，什麼也沒有發生。有人能解釋爲什麼嗎？刪除BST節點（2）

這裏是我的代碼：

private void delete(int value, Node node) { 
    if (value<node.value) delete(value, node.left); 
    else if (value> node.value) 
     delete(value, node.right); 
    else { 
     if (node.left != null && node.right != null) { 
      int maxFromLeft = findMax(node.left); 
      node.value = maxFromLeft; 
      delete(maxFromLeft, node.left); 
     } else if (node.left != null) { 
      Node trash = node; 
      node = node.left; 
      trash = null; 
     } else if (node.right != null) { 
      Node trash = node; 
      node = node.right; 
      trash = null; 
     } else { 
      node = null; 
     } 
    } 
}

來源

2016-04-15 Prone66

請您的問題提供了一個[MCVE（http://stackoverflow.com/help/mcve）。這將幫助其他人重現您的錯誤，並找到它們，因爲有時錯誤隱藏在其他函數中。例如，一個簡化的'Node'類和'findMax'函數。如果你能提供一個簡單的測試用例和錯誤輸出，預期輸出，那將會更好。 – Nier

它看起來像你正在假設通過引用的語義，Java沒有。 –

帶簽名void delete(int,Node)的方法無法工作。考慮當你試圖從只有一個節點的樹中刪除根時會發生什麼：這個方法不能刪除節點，因爲方法參數是按值傳遞的。

你可以做的就是從這個方法返回修改後的BST：

Node delete(int value, Node node) { 
    if (value<node.value) node.left = delete(value, node.left); 
    else if (value> node.value) 
     node.right = delete(value, node.right); 
    ...I'll leave the rest as an exercise... 
    return node; 
}

來源

2016-04-15 07:32:43 Joni

考慮這部分

if (node.left != null) { 
Node trash = node; 
node = node.left; 
trash = null; 
}

您需要刪除node。這沒有做任何事情node = node.left。它只是將一個引用分配給另一個引用。這個dosn't也需要trash = null。

要刪除節點，您需要首先斷開它與父節點的連接，然後將已刪除節點的一個子節點連接到父節點，並將其他子節點插入它應該是的！

來源

2016-04-15 07:14:48

刪除BST節點（2）

回答

相關問題