BST刪除方法應該刪除一個節點的子樹嗎？

所以我得到了一個在Java中創建BST的任務，到目前爲止它都進展順利。但是，我有一個關於刪除方法的問題。正如我已經實現的，如果我刪除節點X，則所有節點X的子樹也將被刪除。我只是想知道這是一個常見的實現，還是我應該重新排列節點，如果我刪除一個？我也是從這個類中創建一個AVL樹，所以我需要一個trinodeRestructering方法。我想這將需要一些修改，以及如果我去和deletenodes？BST刪除方法應該刪除一個節點的子樹嗎？

Thiis是我的刪除方法是如何工作的：

private TreeNode remove(TreeNode currN, int dataToRemove) { 
    if (dataToRemove < currN.getData()) { 
     if (currN.getLeft() != null) { 
      if (currN.getLeft().getData() == dataToRemove) { 
       currN.setLeft(null); 
      } else { 
       remove(currN.getLeft(), dataToRemove); 
      } 
     } 
    } else if (dataToRemove > currN.getData()) { 
     if (currN.getRight() != null) { 
      if (currN.getRight().getData() == dataToRemove) { 
       currN.setRight(null); 
      } else { 
       remove(currN.getRight(), dataToRemove); 
      } 
     } 
    } 
    return currN; 
} 


//visual representation 

      /--------85 
     /--------25 
/--------20 
10 
******************************************************************** 


*******removed 20****** 
10 
*******************************************************************

爲後加入的樹：

   /--------85 
     /--------25 
      \--------24 
/--------20 
     |  /--------13 
     \--------12 
     |  \--------11 
10(root)

下面是一些交換我試過了，看起來非常糟糕，難讀代碼：

if (dataToRemove < currN.getData()) { 
     if (currN.getLeft() != null) { 
      if (currN.getLeft().getData() == dataToRemove) { 

       //Om inga barn, sätt noden till null. 
       if(currN.getLeft().getLeft() == null && currN.getLeft().getRight() == null){ 
        currN.setLeft(null); 
       }//Om noden enbart har höger barn 
       else if(currN.getLeft().getLeft() == null){ 
        TreeNode old = currN.getLeft().getRight();// Gamla höger 
        currN.setLeft(currN.getLeft().getLeft()); // 
        currN.getLeft().getRight().setRight((old)); // 
       }//Om noden enbart har vänster barn. 
       else if(currN.getLeft().getRight() == null){ 
        TreeNode old = currN.getLeft().getRight();// Gamla vänster 
        currN.setLeft(currN.getLeft().getLeft()); // 
        currN.getLeft().getLeft().setRight((old)); // 
       }//om två barn 
       else{ 
        TreeNode oldRight = currN.getLeft().getRight();// null 
        currN.setLeft(currN.getLeft().getLeft()); //sätt current left till 11 
        currN.getLeft().setRight((oldRight)); // current left, right till 13 
       } 
      } else { 
       remove(currN.getLeft(), dataToRemove); 
      } 
     }

來源

2016-09-30 spline123

你可以，如果你的應用程序需要這種行爲，但它並不常見。它是「樹」的事實通常是無關緊要的：你只是將「一些」值存儲在「某些」數據結構中。 Java的'TreeSet'是一個二叉搜索樹;當你移除一個元素時，這並不會刪除子元素，如果是這樣的話，它將成爲PITA元素，因爲實際上看不到樹的結構以知道哪些元素將被先前刪除。 –

是啊有一個已知的實現，當你想刪除比奈節點ry搜索樹，將其左子樹的最右邊的葉子或右子樹的最左邊的葉子交換，然後刪除該葉子。

對於AVL，您必須跟蹤平衡條件的遞歸操作，只要違反平衡條件，您需要根據違規的結構進行某種旋轉，如果您做了一些研究你會發現一大堆資源來解釋這個確切的算法。

來源

2016-09-30 07:42:10

好吧，那麼如果我在更新後的帖子中有樹，我想刪除節點「25」會發生什麼？我應該用85還是24來代替它？這是否重要？ – spline123

BST刪除方法應該刪除一個節點的子樹嗎？

回答

相關問題