バイナリツリーで再帰的操作中にルートノードを削除するにはどうすればよいですか？

Question

バイナリツリーの削除機能を書いています。私は私のケースを3つに分けました。 1つの子がヌルで、1つが両方の子がヌルでないもの。私は再帰的にケース3の後にdelete操作を呼び出しています。たとえば、私がノード50で削除操作を呼び出したことがわかります。これは親ノード50を75に置き換えます。今度は右のサブツリーからノード75を削除する必要があります。だから私は再帰的に削除手順を実行した。 75は私がルート

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

まあを削除することができていますように、私はそれを修正するにはどうすればよい50の右部分木のルートノードがあるので、しかし、私は所望の出力を得ていないのです、あなたは、2つのオプションがあります。

最初の方法：このデータ構造の実装の詳細を隠すオブジェクトにツリー構造をラップすることができます。すべての関連する変更呼び出しをルートノードに転送し、ルートノードを削除する必要がある場合に対処するdelete操作を実装します。この場合、ラッパーオブジェクト内の参照を置き換えることができます。

第2の方法：あなたの持っているものを再利用してください。ルートノードは削除しませんが、目的の新しい内容で上書きしてください。そうすれば、ノードの親を見つけて変更する必要がなくなり、問題は解決されます。しかし、これはずっと簡単です。