非再帰N線ツリートラバーサル

Question

としてクラス定義を考える：

class Node { 
    public Double value; 
    public List<Node> children; 
} 

非再帰的に以下のプログラムを翻訳：

public static void process(Node node) { 
    for (int i = 0; i < node.children.size(); i++) { 
     Node child = node.children.get(i); 
     if (child.value < node.value) { 
      process(child); 
     } 
    } 
    System.out.println(node.value); 
    for (int i = 0; i < node.children.size(); i++) { 
     Node child = node.children.get(i); 
     if (child.value >= node.value) { 
      process(child); 
     } 
    } 
} 

共通ツリートラバーサルアルゴリズムは、ここで適切であると思われるが、スタックポップは条件をチェックする必要があるからです。

本当に解決策は考えられません。

サンプルツリーを使用する場合のコードに示すように、私は次の出力を得る：

5.7 6.0 1.0 12.0 13.0 5.0 8.0 7.0 10.0 9.0 5.5 15.0 11.0 14.0

public class Node { 
public Double value; 
public List<Node> children; 
public Node(Double value) { 
    this.value = value; 
    this.children = new ArrayList<Node>(); 
} 
public void addChild(Node node) { 
    children.add(node); 
} 
public static Node createSample() { 
    Node node = new Node(10.0); 
    Node node1 = new Node(15.0); 
    Node node2 = new Node(6.0); 
    Node node3 = new Node(11.0); 
    Node node4 = new Node(14.0); 
    Node node5 = new Node(5.0); 
    node.addChild(node1); 
    node.addChild(node2); 
    node.addChild(node3); 
    node.addChild(node4); 
    Node node51 = new Node(8.0); 
    Node node52 = new Node(7.0); 
    node5.addChild(node51); 
    node5.addChild(node52); 
    node.addChild(node5); 
    Node node11 = new Node(9.0); 
    Node node12 = new Node(5.5); 
    node1.addChild(node11); 
    node1.addChild(node12); 
    Node node21 = new Node(5.7); 
    Node node22 = new Node(12.0); 
    node2.addChild(node21); 
    node2.addChild(node22); 
    Node node31 = new Node(13.0); 
    Node node32 = new Node(1.0); 
    node22.addChild(node31); 
    node22.addChild(node32); 
    return node; 
} 

}

Answer 1

1つの方法は、再帰呼び出しが行われたときにメモリによって使用されたのと同じメカニズムを利用して、再帰プロセスが何を手動で実装するかです。すなわち、メモリのスタック構造を利用して再帰呼び出しを行う。非再帰ツリートラバーサルは、メモリで使用されるのと同様のスタックを使用することによってシミュレートすることもできます。次に、トラバーサルはループを構成し、スタックに子供を押し付け続け、最初の子を訪問（ポップ）します。スタックにノードがなくなると、ループは終了します。これは、あなたが作っている再帰的なトラバーサルと同じです。ポストオーダーのツリートラバーサルとも呼ばれます。ツリーの代わりにグラフを扱っていた場合、このアプローチを深さ優先検索と見なすことさえできます。

あなたの質問に口頭で言及しないことの1つは、子供たちを価値の大きさのオーダーで処理する必要があることです。そのためには、要素をスタック内に配置する順序を練るだけで済みます。スタックはLIFO（ラスト・イン・ファースト・アウト）データ構造であるため、親ノードよりも値が小さい要素は、値が小さいものよりも前に配置する必要があります。

以下は、上で説明したソリューションのサンプルであり、それほど効率的ではありません。この解決策を作業hereで観察しても、質問に記載されているのと同じ結果が得られます。

class StackNode { 
    public Node node; 
    public boolean largerChildrenPushed; 
    public StackNode(Node n) { 
     this.node = n; 
     this.largerChildrenPushed = false; 
    } 
} 
public static void process(Node node) { 
    Stack st = new Stack(); 
    st.push(new StackNode(node)); 
    while(!st.empty()) { 
     StackNode stParent = (StackNode)st.pop(); 
     Node parent = stParent.node; 
     if(!stParent.largerChildrenPushed) { 
      for (int i = parent.children.size() - 1; i >= 0; i--) { 
       Node child = parent.children.get(i); 
       if (child.value >= parent.value) { 
        st.push(new StackNode(child)); 
       } 
      } 
      st.push(stParent); 
      stParent.largerChildrenPushed = true; 
      for (int i = parent.children.size() - 1; i >= 0; i--) { 
       Node child = parent.children.get(i); 
       if (child.value < parent.value) { 
        st.push(new StackNode(child)); 
       } 
      } 
     } 
     else { 
      System.out.println(parent.value); 
     } 
    } 
} 

Answer 2

私は解決策を提供することはできませんが、あなたのロジックに移動するヒントはありません。メモリ内で実行されているときに再帰を使用するデータ構造を考えてみましょう。そのデータ構造を使用して、物事をプッシュしてポップアップさせ、あなたのデータ構造が他に何もトラバースしなくなるまでトラバースします。

そして、最初にどのようなタイプのツリートラバーサルなのか把握していますか？あなたのロジックを小さなチャンクに分割し、非再帰的/反復的なコードで順番にそれを処理してください。