再帰なしで非バイナリツリーをトラバースするアルゴリズムは何ですか（スタックを使用）

Question

直感的に私は(node, iterator)のようなスタックのペアを維持していますが、それでも解決策はありません。

Answer 1

再帰アルゴリズムは、常に明示的なスタックを持つアルゴリズムに変換できます。再帰的なコードで起動します。

void traverse(NODE *p) { 
    if (p) { 
    for (int i = 0; i < p->n_children; ++i) { 
     traverse(p->child[i]); 
    } 
    } 
} 

は再帰呼び出しを置き換えます。そこ

struct { 
    NODE *p; 
    int i; 
} stk[MAX_RECURSION_DEPTH]; 
int sp = 0; 

void traverse(NODE *p) { 
start: 
    if (p) { 
    for (int i = 0; i < p->n_children; ++i) { 
     // Save local values on stack. 
     stk[sp].p = p; 
     stk[sp++].i = i; 
     // Simulate recursive call. 
     p = p->child[i];   
     goto start; 
     // Goto this label for return. 
    rtn: 
    } 
    } 
    // Simulate recursive return, restoring from stack if not empty. 
    if (sp == 0) return; 
    p = stk[--sp].p; 
    i = stk[sp].i; 
    goto rtn; 
} 

あなたはそれを持っています持っている明示的なスタックの実装は限り再帰バージョンが同じように動作します。それは同じことです。

あなたが好きなら、gotoを削除するために代数を行います。まず、whileとしてforを書き換え、rtnラベル

void traverse(NODE *p) { 
    int i; 
start: 
    if (p) { 
    i = 0; 
    rtn_2: 
    while (i < p->n_children) { 
     stk[sp].p = p; 
     stk[sp++].i = i; 
     p = p->child[i];   
     goto start; 
    } 
    } 
    if (sp == 0) return; 
    p = stk[--sp].p; 
    i = stk[sp].i; 
    ++i; 
    goto rtn_2; 
} 

注while内部++iはデッドコードだったので、落としても安全だったリファクタリングすることができます。

whileの本文は、複数回実行されることはありません。それはifと置き換えることができます。 goto rtn_2は、実行されるコードに置き換えることもできます。

void traverse(NODE *p) { 
    int i; 
start: 
    if (p) { 
    i = 0; 
    if (i < p->n_children) { 
     stk[sp].p = p; 
     stk[sp++].i = i; 
     p = p->child[i];   
     goto start; 
    } 
    } 
    for (;;) { 
    if (sp == 0) return; 
    p = stk[--sp].p; 
    i = stk[sp].i; 
    ++i; 
    if (i < p->n_children) { 
     stk[sp].p = p; 
     stk[sp++].i = i; 
     p = p->child[i];   
     goto start; 
    } 
    } 
} 

最後に、我々は代わりにループを使用してstartラベルを取り除くことができます。

void traverse(NODE *p) { 
    int i; 
    for (;;) { 
    if (p) { 
     i = 0; 
     if (i < p->n_children) { 
     stk[sp].p = p; 
     stk[sp++].i = i; 
     p = p->child[i];   
     continue; 
     } 
    } 
    for (;;) { 
     if (sp == 0) return; 
     p = stk[--sp].p; 
     i = stk[sp].i; 
     ++i; 
     if (i < p->n_children) { 
     stk[sp].p = p; 
     stk[sp++].i = i; 
     p = p->child[i];   
     break; 
     } 
    } 
    } 
} 

別のクリーンアップはiは常に最初ifで0であることに注意することがあり、そしてcontinueは実際にありますネストされたループを実装しています。削除できる冗長stk[sp].p = p;もあります。

void traverse(NODE *p) { 
    for (;;) { 
    while (p && p->n_children > 0) { 
     stk[sp].p = p; 
     stk[sp++].i = 0; 
     p = p->child[0];   
    } 
    for (;;) { 
     if (sp == 0) return; 
     p = stk[--sp].p; 
     int i = stk[sp].i + 1; 
     if (i < p->n_children) { 
     stk[sp++].i = i; // stk[sp].p = p; was redundant, so deleted 
     p = p->child[i];   
     break; 
     } 
    } 
    } 
} 

それはコードが少しきれいにすることが可能だが、私はあなたにそれを残しておきます：ちょうど、すでにありますスタックに値をコピーします。注意すべき点は、直感がなく、ポインタが何をしているのか想像してみることです。私たちはコード上で代数を行いました。そして、合理的に素晴らしい実装がもたらされました。私はそれを実行していませんが、私は代数の間違い（可能）をしない限り、これは "ちょうど働く"べきです。

これは、教科書に表示される典型的なスタックベースのDFSとは少し異なります。それらは、スタック上に新しく発見されたノードのすべての子をプッシュします。通常のDFS順序を取得するには、最初に右端の子で行う必要があります。

代わりに、次に子を検索する必要があることを示す整数とともに親をプッシュします。これはあなたが言及したノード+イテレータです。もう少し複雑ですが、スタックサイズの方が効率的です。スタックの最大サイズはO（D）です。ここで、Dはツリーの最大深さです。教科書アルゴリズムにおけるスタックのサイズはO（KD）であり、Kはノードが持つことができる子の最大数である。