從二進制搜索樹中返回已刪除的節點

我正在嘗試編寫一個方法，該方法可以通過給定的值從BST中刪除節點，並且我需要它來返回此刪除的值。我發現了遞歸實現的各種示例，但由於它們的本質，它們不能返回刪除的節點，而是返回根節點。下面是我現在從二進制搜索樹中返回已刪除的節點

public TreeNode remove(TreeNode node, int data) { 
     if (null == node) { 
      return null; 
     } 
     if (data < node.st.getkey()) { 
      node.left = remove(node.left, data); 
     } else if (data > node.st.getkey()) { 
      node.right = remove(node.right, data); 
     } else { // case for equality 

      if (node.left != null && node.right != null) { 
       TreeNode minInRightSubTree = min(node.right); 

       copyData(node , minInRightSubTree); 

       node.right = remove(node.right, minInRightSubTree.st.getkey()); 
      } else { 
       if (node.left == null && node.right == null) { 
        node = null; 
       } else {// one child case 
        TreeNode deleteNode = node; 
        node = (node.left != null) ? (node.left) : (node.right); 
        deleteNode = null; 
       } 
      } 
     } 
     return node; 
    }

我可以拿出一些黑客攻擊，使其返回刪除節點，或者我應該考慮的迭代算法（如果有的話，我會很感激，如果你可以幫我介紹了鏈接）。

來源

2017-06-04 Jack Nickolson

您不僅可以返回根，還會返回一對根和已刪除的節點（如果沒有刪除，則返回null）。您可以使用Map.Entry或新類來存儲2個字段（我會推薦新類，因爲它更具描述性）。所以你可能的新簽名將是public Map.Entry<TreeNode, TreeNode> remove(TreeNode node, int data)

來源

2017-06-04 19:17:44

我剛想出聲明一個輔助公共節點，將舉行lastRemovedNode的想法。 –

從二進制搜索樹中返回已刪除的節點

回答

相關問題