見つかったノードを削除する方法

Question

私はノードを削除する必要があるバイナリ検索ツリーで作業しています。ノードはすでに検出されているので、特定のノードをトラバースして見つける必要はありません。私が必要とするのは、ノードを削除することです。ノードは引数として取られます。

私はノードの削除方法を開始しましたが、現在のところ、子ノードがないかリーフノードである場合にノードを削除するしか方法はありません。どのように私はそれが1つの子供または親を持っている場合、削除するJavaコードを実装するのですか？

私の現在のremoveメソッド：

public void removeHelper(Node focus){ 

     if(focus.leftChild == null && focus.rightChild == null){ 
      focus = null; 
     } 

     // if the node has 1 child 


     // if the node has 2 children 


    } 

Answer 1

は、あなたがルートフィールドを交換する必要がある、または親ノードのleftChildかrightChildのどちらかになるので、ツリーを下に移動する必要があります。

leftChildとrightChildがヌルでないノードを削除するには、ノードを左のサブツリーの最も右のノードまたは右のサブツリーの一番左のノードに置き換えることができます。この例では

は、私が（Tree？）メソッドがクラスであることを前提としていNodeフィールドはrootと呼ばれ、Node sがComparableあるフィールドvalueを持っているしていること：

public void remove(Node focus) { 
    root = removeHelper(root, focus); 
} 

public static Node removeHelper(Node root, Node focus) { 
    if (root == null) { 
     return null; 
    } else if (root == focus) { 
     if (focus.leftChild == null) { 
      return focus.rightChild; 
     } else if (focus.rightChild == null) { 
      return focus.leftChild; 
     } else { 
      Node node = removeLeftMostOfRight(focus); 
      node.leftChild = focus.leftChild; 
      node.rightChild = focus.rightChild; 
      return node; 
     } 
    } else { 
     int r = focus.value.compareTo(root.value); 
     if (r < 0) { 
      root.leftChild = removeHelper(root.leftChild, focus); 
     } else { 
      root.rightChild = removeHelper(root.rightChild, focus); 
     } 
     return root; 
    } 
} 

private static Node removeLeftMostOfRight(Node focus) { 
    Node node = focus.rightChild; 
    if (node.leftChild == null) { 
     focus.rightChild = node.rightChild; 
    } else { 
     Node prev; 
     do { 
      prev = node; 
      node = node.leftChild; 
     } while (node.leftChild != null); 
     prev.leftChild = node.rightChild; 
    } 
    return node; 
} 

C/C++のような言語では、バイナリツリーをはるかに簡単かつ効率的に実装できるポインタへのポインタを持つことができます。