二叉樹通過合併遞歸實現刪除

我已經通過合併實現了迭代版本的刪除，但我努力實現遞歸。二叉樹通過合併遞歸實現刪除

這是我的迭代版本：

public void deleteByMerging(T el) { 
    BSTNode<T> tmp, node, p = root, prev = null; 
    while (p != null && !p.el.equals(el)) { 
     prev = p;       
     if (el.compareTo(p.el) < 0) 
       p = p.right; 
     else p = p.left; 
    } 
    node = p; 
    if (p != null && p.el.equals(el)) { 
     if (node.right == null) 
       node = node.left; 
     else if (node.left == null) 
       node = node.right; 
     else {     
       tmp = node.left; 
       while (tmp.right != null) 
        tmp = tmp.right;  
       tmp.right =   
        node.right;  

       node = node.left; 
     } 
     if (p == root) 
       root = node; 
     else if (prev.left == p) 
       prev.left = node; 
     else prev.right = node; // 5. 
    } 
    else if (root != null) 
     System.out.println("el " + el + " is not in the tree"); 
    else System.out.println("the tree is empty"); 
}

現在我需要實現這樣的遞歸函數：

public void delete(T info) { 
    root = delete(root, info); 
} 

public TreeNode<T> delete(TreeNode<T> node, T info) 
    { 

    }

林很新遞歸，我沒有從哪裏開始的想法。

來源

2014-02-27 beckinho

（通過「你的」迭代版本，當然，你的意思是亞當·德羅齊德克的。）

這應該工作：

public void delete(T info) { 
    root = delete (root.info); 
} 

public TreeNode<T> delete(TreeNode<T> node, T info) { 

    // if this node is null, we have reached the end of the tree 
    // so the node is not in the tree. 
    if (node == null) { 
     return node; // or handle as required 

    // if this is not the node to delete; 
    // recursively call this on the node's correct child 
    else if (info.compareTo(node.info) <0) { 
     node.left = delete(node.left, info); 
     return node; 
    } else { 
     node.right = delete(node.right, info); 
     return node; 
    } 

    // if this is the node to delete: 
    else if (node.info.equals(info)) { 
     // to delete it, we must return a sub-tree without it. 

     if (node.left == null) 
      // this node is a leaf node, or 
      // node.right contains only child. 
      // either way, return node.right 
      return node.right; 

     if (node.right == null) 
      // node.left contains only child 
      return node.left; 

     // else node has 2 children, so delete by merging: 
     // first, find its direct predecessor: 
     TreeNode<T> tmp = node.left; 
     while (tmp.right != null) 
      tmp = tmp.right; 
     // then append the node's right sub-tree 
     // to its direct predecessor: 
     tmp.right = node.right; 
     // lastly, replace the node by its left sub-tree: 
     return node.left; 
    } 
}

首先，我們檢查，如果node爲null。如果是這樣，那意味着我們要刪除的元素不在樹中，因爲我們遍歷了，直到我們用盡了所有可能已經存在的節點。

接下來，我們檢查元件比大於當前節點的元件大或更大。如果是這樣，我們需要繼續遍歷樹，根據元素的比較方向左右移動。請注意，在遞歸步驟中，我們將刪除操作的結果分配給node的孩子之一。我們已經從第一個函數中獲得了這個提示，其中root被分配了root上的刪除操作的結果。這將遞歸遍歷樹，直到node引用您想要刪除的節點。我們在這裏也返回node，這樣如果沒有發生變化，例如對node.right = delete(node.right, info)的調用將不會改變當前節點。

當我們找到的節點，4方案是可能的：所述節點可以是葉節點（沒有孩子），或者它可以具有1向左或向右1子，或者它可以有2個孩子。前3個場景是由線

if (node.left == null) 
    return node.right; 
if (node.right == null) 
    return node.left;

注意覆蓋，如果node沒有孩子，第一if檢查將是真實的，所以node的右子（其爲null）將被退回，刪除節點。

爲什麼返回null刪除節點？因爲在上面討論的遍歷步驟中，我們將刪除操作的結果分配給node的孩子。請注意，在上一個遞歸步驟中，node在此步驟中是node的父級，因爲刪除是在該節點的子節點上遞歸調用的。因此，在這裏返回null將導致先前的調用將null分配給父項的子項，從而刪除該子項。基本上，只要我們返回node以外的任何東西，我們就會用樹中返回的任何東西替換當前節點。

在第四種情況下，我們需要通過合併進行簡單的刪除。您可以通過將node的右子樹添加到其左子樹中最右邊的節點來完成此操作。首先，我們發現在左子樹中最右邊的節點，這是node的直接前身：

TreeNode<T> tmp = node.left; 
while (tmp.right != null) 
    tmp = tmp.right;

所以tmp現在node的直接前身。接下來，我們鎖定node的右子樹到tmp：

tmp.right = node.right;

最後，通過它的左子樹來代替node，我們就返回node.left，因爲這將與node.left取代node爲node孩子在之前的遞歸調用中的父母。

如果我的解釋讓你困惑，你可以試試this one。這很容易用紙上的圖片來解釋，這就是爲什麼你應該在實際會議中問我（是的，我設置了這個實踐），而不是這樣:)希望你在截止日期之前找出它！

來源

2014-02-28 21:43:58

二叉樹通過合併遞歸實現刪除

回答

相關問題