如何在二叉樹的遞歸操作中刪除根節點？

Question

我正在寫二進制樹的刪除功能。我把我的案例分成了三份。一個有一個孩子，一個孩子不爲空。我遞歸調用刪除操作的情況下3後前，你可以看到我已經呼籲節點50.刪除操作這與75替換父節點50現在我已經刪除右子樹的節點75。所以我遞歸地運行了刪除過程。但我沒有得到期望的輸出，因爲75是在50右子樹如何解決它，這樣我能夠刪除根

class BST { 
    public static void main(String args[]) { 
     Tree tr; 
     tr = new Tree(100); 
     tr.insert(50); 
     tr.insert(125); 
     tr.insert(150); 
     tr.insert(25); 
     tr.insert(75); 
     tr.insert(20); 
     tr.insert(90); 
     tr.delete(50); 
    } 
} 

class Tree { 

    public Tree(int n) { 
     value = n; 
     left = null; 
     right = null; 
    } 

    public void insert(int n) { 
     if (value == n) 
      return; 
     if (value < n) 
      if (right == null) 
       right = new Tree(n); 
      else 
       right.insert(n); 
     else if (left == null) 
      left = new Tree(n); 
     else 
      left.insert(n); 
    } 

    public Tree min() { 
     if(left == null) 
      return this; 
     else 
      return left.min(); 
    } 

    public Tree max(){ 
     if(right == null) 
      return this; 
     else 
      return right.max(); 
    } 

    public Tree find(int n) 
    { 
     if(n == value) 
      return this; 
     else if(n > value) 
      return right.find(n); 
     else if(n < value) 
      return left.find(n); 
     else 
      return null; 
    } 

    public Tree findParent(int n, Tree parent) 
    { 
     if(n == value) 
      return parent; 
     else if(n > value) 
      return right.findParent(n, this); 
     else if(n < value) 
      return left.findParent(n, this); 
     else 
      return null; 
    } 

    public void case1(int n, Tree tr, Tree parent) 
    { 
     if(parent.left.value == n) 
      parent.left = null; 
     else 
      parent.right = null; 
    } 

    public void case2(int n, Tree tr, Tree parent) 
    { 

     if(parent.left!=null && parent.left.value == n) 
      parent.left = parent.left.left; 
     else 

      parent.right = parent.right.right; 

    } 

    public void case3(int n, Tree tr, Tree parent) 
    { 
     int min = tr.right.min().value; 
     tr.value = min; 
     tr.right.delete(min); 
    } 


    public void delete(int n) { 

    // fill in the code for delete 

     Tree tr = find(n); 
     Tree parent = findParent(n, this); 

     if(tr == null) 
     { 
      System.out.println("The tree is not present in Binary Tree"); 
      return; 
     } 
     if(tr.left == null && tr.right == null) 
     { 
      case1(n, tr, parent); 

     } 
     else if((tr.left == null) || (tr.right == null)) 
     { 
      System.out.print(tr.right.value); 
      System.out.print(parent.right.value); 
      case2(n, tr, parent); 
     } 
     else 
     { 
      case3(n, tr, parent); 
     } 

    } 

    protected int value; 
    protected Tree left; 
    protected Tree right; 
} 

Answer 1

好根節點，你有兩個選擇：

第一種方式：你可以在隱藏了數據結構的實現細節的對象包樹結構。轉發所有相關的修改調用根節點，並執行刪除操作來處理時，根節點應刪除的情況：在這種情況下，只需更換的包裝對象的引用。

方式二：重用你有什麼。不要刪除根節點，而是用所需的新內容覆蓋它。這樣您就不必查找和更改節點的父節點，問題就解決了。這似乎更容易，但。