ソートの量によって順序付けられていないツリーノードが、私は現在、自分のロバート・セッジウィック（第3版、ドイツ語版）による「Javaでアルゴリズム」を通じて働いていると演習の一つを解決しようとしています

Question

を持っている子供は、ノード現在、「創造的ソリューション」のセクションからのものです。

私は、各ノードが持つ子供の量によってソートされていない木を並べ替えしようとしている1つのエクササイズ、最初に来る子どもたちのより多くの量を持つノードのソリューションの一部として：

1. ソートすべての子ノード、子ノード自身の持つ子ノードの数に応じて、親ノードn0のノード番号を左から右にソートする。ツリー内のすべてのノードに対してこの並べ替えを実行します。
2. これらの子ノードの2つの兄弟ノードn1とn2が同じnNodesの場合は、n1とn2の子ノードに移動して、最大の子のnNodesに従ってこれらの2つをソートします。何の違いが見つからない場合、あなたは子供たちが不足した場合、子供や繰り返しの最大量を2子の子ノードに移動
3. など、自分の2番目に大きな子供のnNodesに応じて並べ替えしよう2.などなど
4. すべての比較の後に、それはN1とN2の両方が同一の形状を持つ樹木の根であることが判明した場合、最初に来る2のどの問題ではありません。

視覚的な比較を行うために、この「規則」は、ここに示すように、次のツリーソートをもたらすでしょう：Example of Sorting。

コード

私が正しく並べ替えを実施しているにこだわっている問題。各ツリーはノードで構成されています。各ノードには値が格納されています（つまり、ノードの「名前」を持ち、各ノードが持つ子の数だけを気にするソート自体は重要ではありません）、そのノードの子ノードへのノード参照のarrayListノード。 ArrayListのサイズが0である子供がいないノードの場合、ここで重要な点は、コンパレータオブジェクトで組み込みソートメソッドを使用して現在実行しようとしているすべてのノードのArrayListをソートすることです。私はこのメソッドに再帰的にアプローチする必要があると思います。これは、現在、同じメソッド内の他のArraListsに対して「ソート」を呼び出している間に、自分自身を呼び出すコンパレータメソッドを持つため、すべてが本当に面倒です。以下のsortForestメソッドは、テストするためにいくつかのメインメソッドでスタックオーバーフローエラーを試しています。

static NodeComparator comp = new NodeComparator(); 

    static class Node { 
     int value; 
     ArrayList<Node> children; 

     Node(int value, ArrayList<Node> children) { 
      this.value = value; 
      this.children = children; 
     } 
    } 

    static class NodeComparator implements Comparator<Node> { 
     public NodeComparator() { 
     } 

     public int compare(Node n1, Node n2) { 
      /*- 
      * Base Case 1: Both Nodes are leafs (isEmpty() is true) - they are 
      * equal -> return 0. 
      * Base Case 2/3: One of the Nodes is a leaf while the other isn't - 
      * the one that is a leaf is "lower" than the one that isn't. -> 
      * return (-) 1. 
      */ 
      if (n1.children.isEmpty() && n2.children.isEmpty()) { 
       return 0; 
      } else if (n2.children.isEmpty()) { 
       n1.children.sort(comp); 
       return 1; 
      } else if (n1.children.isEmpty()) { 
       n2.children.sort(comp); 
       return -1; 
      } else { 
       /* Get the amount of children the 2 nodes n1 and n2 have */ 
       int nChildren1 = (n1.children.isEmpty()) ? 0 : n1.children.size(); 
       int nChildren2 = (n2.children.isEmpty()) ? 0 : n2.children.size(); 
       /* Always sort the ArrayList of children that they have */ 
       n1.children.sort(comp); 
       n2.children.sort(comp); 

       /* 
       * If n1 and n2 have equal amounts of children, compare the 
       * amounts of children their children have, from largest to 
       * lowest 
       */ 
       if (nChildren1 == nChildren2) { 
        int result = 0; 
        for (int i = 0; (i < nChildren1) && (result == 0); i++) { 
         compare(n1.children.get(i), n2.children.get(i)); 
        } 
        return result; 
       } else { 
        /*- If one node has more children than the other, sort accordingly */ 
        return ((nChildren1 > nChildren2) ? 1 : -1); 
       } 
      } 
     } 
    } 

    static void sortForest(Node root) { 
     for (int i = 0; i < root.children.size(); i++) { 
      sortForest(root.children.get(i)); 
      root.children.sort(comp); 
     } 
     return; 
    } 

質問

どのようにして、このコードは、仕事を得ることができますか？私はこれがおおよそ正しい解決策の球場にあると確信していますが、私は数時間以上これを考えようとしましたが、それを理解することはできません。私はこれが私にスタックオーバーフローを与えていると確信しています。終わりのない再帰がどこかにあるため、私はそれを見ません。通常、再帰は私にこの問題を精神的に正しく行うための問題を与えています。私はこれと同じ質問を見つけることができず、類似しているものは順序付けられていないツリーの代わりにバイナリツリーに関係していました。 Javaのデフォルトのスタックサイズに関するsortForestを呼び出すときに

Answer 1

上記のコードが間違っていくつかのものがある：

1. コードは、各ツリーのルートノードが本来引き起こされる、（上記のコードには示されていない）自体への参照を含んでいなかったと仮定しルートを何度も呼び出すメソッドを比較すると、これは修正されました。

2. 比較方法でソートを呼び出すことは絶対に不要で実際には間違っています。コードはすでに、葉から始まる​​を持つすべてのノードのソートメソッドを呼び出すので、そこには場所がなく、compareメソッドのコードのすべての部分から削除する必要があります。

3. compareメソッドは、最大から最小のソートにはなりませんが、最小から最大のソートになります。それは-1を返す場所で1を返す必要があり、その逆もあります。

4. また、比較方法では、compare()の戻り値をresultに格納する必要があります。それ以外の場合は結果が変更されず、類似性が検出されてもループは停止しません。

5. あなたはまだ正確にすべてのコールを実行するために、元のためにそれらを必要としながら、そうでない場合には、ArrayListのいくつかの並べ替え、外forLoopの起こらなければなりません​​でroot.children.sort(comp);絶対にでソート。

これらの全てを整流した後、​​とcompare()方法は、上記のように、例えば木の正しいソート結果配信：

int[] tree1 = { 2, 3, 3, 3, 2, 2, 1, 0, 7, 5, 3, 10, 10, 6 };

int[] tree2 = { 4, 10, 11, 0, 4, 0, 12, 4, 7, 8, 0, 3, 4, 12 };

およびthis pictureに示すようにそれらを並べ替えます。

一緒に不要なコードのいくつかの最適化と除去と、固定のソートとソリューションの完全なコードはhere

Answer 2

ツリーのサイズによっては、制限に抵触する可能性があります。それを回避する方法は、それが非再帰的またはTrampoline patternを使用して再書き込み、Threadconstructorでスタックサイズを設定し、-Xss JVMオプションを経由して、それを増やしています。