2

順序付けられていない二分木があり、ルート x のサブツリーを削除する方法を実行する必要がありました。要素 x がバイナリ ツリーに複数回存在する場合、メソッドはルート x のサブツリーの 1 つだけを削除します (最初に見つかったもの)。削除が実行された場合、true を返します。要素 x がバイナリ ツリーに存在しない場合は、false を返します。したがって、方法は次のとおりです。

    public class BinaryTree 
{
    protected class Node 
    {
        Integer element;
        Node left;
        Node right;

        Node(int element) 
        {
            this.element = element;
            left = right = null;
        }

        Node(int element, Node left, Node right) 
        {
            this.element = element;
            this.left = left;
            this.right = right;
        }

    protected Node root;

    public BinaryTree() 
    {
        root = null;
    }

    private class BoolNode 
    {
        boolean ft;
        Node nodo;

        BoolNode(boolean ft, Node nodo) 
        {
            this.ft = ft;
            this.nodo = nodo;
        }
    }

    public boolean removeSubtree(int x) 
    {
        BoolNode ris = removeSubtree(x, root);
        //root = ...;
        return ris.ft;
    }

    private BoolNode removeSubtree(int x, Node node) 
    {
        return null;
    }
}

始め方がわかりません。疑似コードでさえ..ありがとう！

4

1 に答える 1

4

このまま行けばいいのに……。

  • 値 X を含むノード N を見つける
  • N が葉の場合、葉を取り除きます

  • N が親の場合、

     removeNodes(N.left);
 removeNodes(N.right);
 remove(N);

  • 葉っぱに当たるまで繰り返す

     private void removeNodes(Node base);  //prepare for this when the teacher asks you why it's private
 // - because you do not want to expose this functionality outside of the class;
 // the only 'interface' exposed is the wrapper call removeSubtree(...) as the user shouldn't worry about the internal functionality.

removeSubtree() は、再帰的な removeNodes(); のラッパーです。

編集：ミステリーを明確にするためにわかりました。この木があると仮定します

             1 --- this is root
            / \
           3   7
          / \ / \
     (a) 5  4 3  2  //these branches don't matter right now
        / \
       5   6
      / \  / \
     5  4 3   2

ここで、removeSubtree(5, root); を呼び出したとします。

ノード (a) (左側の最初の 5 つ) に到達するまで、ツリーをトラバースします。現在のコードの書き方では、次のようになります。値 X (5) を持つノードが検索されます。次に、彼のすべての左と右のサブチャイルドに対して、値 5 を探します。

これに焦点を当てましょう

             1 --- this is root
            / \
           3   7
            \ / \
            4 3  2

これは、removeSubtree(5, root); を呼び出した後に取得する必要があるものです。つまり、値が 5 の最初のノードを見つけてその子を削除した後に削除されるはずのサブツリーを見てください。

         5  -- we should delete all of these starting from here
        / \
       5   6
      / \  / \
     5  4 3   2

ただし、コードはその後、そのサブツリーで削除する値 5 を探します。そのため、ツリーを走査して見つけたものをすべて削除する汎用の deleteSubtree() ルーチンが必要です。removeSubtree(int, node) ルーチンは、それに依存するか、そのメカニズム自体を実装して「インライン化」する必要があります。

現在、コードはこれのみを削除します

             1 --- this is root
            / \
           3   7
          / \ / \
     (a) 5  4 3  2  //these branches don't matter right now
        / \
  (b)  5   6
      / \  / \
(c)  5  4 3   2

つまり、ノード A (最初の 5) に到達し、ノード (a) の下のすべてを削除する代わりに、A の下の別の値 5 を検索し、(b) を見つけて、ノードのみに一致するサブツリーを削除しようとします。 (c).

最終結果は次のようになります。コードは 3 つの 5 のみを削除し、これが残ります。

             1 --- this is root
            / \
           3   7
          / \ / \
         x  4 3  2  
        / \
       x   6
      / \  / \
     x  4 3   2

同じ関数を再帰的に使用できない理由がわかりましたか? :)少なくともあなたが今望んでいる方法ではありません。ただし、これを試すことができます-

 removeSubtree(node.left.value, node);
 removeSubtree(node.right.value, node);
 removeNode(node);

これにより、適切なサブツリー (ノード (a)) が効果的に検出され、それ自体を呼び出してその子 (ノード (b) の深さのノード 5 と 6) に一致するようになり、それらが削除されます。いずれにしても、以前のようにこれらの呼び出しで値 X を再利用することはできません

 removeSubtree(x, node.left);
 removeSubtree(x, node.right);
 removeNode(node);

私はそれが何かを明確にしたことを願っています:)多分私はこれを教えるべきです:D

于 2012-10-31T18:03:26.703 に答える