Was ist der Algorithmus, um einen nicht-binären Baum ohne Rekursion (mit Stack) zu durchlaufen

Question

Intuitiv verstehe ich, dass ich auf Stack-Paare wie halten, aber immer noch kann ich nicht zu einer funktionierenden Lösung.

Answer 1

Sie können einen rekursiven Algorithmus immer in einen mit einem expliziten Stapel übersetzen. Beginnen Sie mit rekursiven Code:

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

den rekursiven Aufruf ersetzen:

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; 
} 

Da haben Sie es: eine explizite Stack-Implementierung, die so lange wie die rekursive Version tat arbeiten muss. Das ist gleich.

Jetzt, wenn Sie möchten, tun wir eine Algebra, um die goto s zu beseitigen. Zunächst können wir die for als while umschreiben und Refactoring die rtn Label

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; 
} 

Notiere die ++i innerhalb des while war tot Code, so sicher war zu fallen.

Jetzt beachten Sie, dass der Körper der while nie mehr als einmal ausgeführt wird. Es kann durch eine if ersetzt werden. Wir können goto rtn_2 auch durch den Code ersetzen, der ausgeführt wird.

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; 
    } 
    } 
} 

Schließlich können wir von dem start Etikett loszuwerden, indem eine Schleife statt mit:

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; 
     } 
    } 
    } 
} 

Eine weitere Bereinigung zu beachten ist, dass i ist immer 0 in den ersten if und die continue ist eigentlich Implementieren einer geschachtelten Schleife, die wir explizit machen können. Es gibt auch eine redundante stk[sp].p = p;, die gelöscht werden kann. Es ist das Kopieren nur Wert auf den Stapel, der bereits vorhanden ist:

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; 
     } 
    } 
    } 
} 

Es ist möglich, den Code ein bisschen bisschen besser zu machen, aber ich werde es dich verlassen. Zu beachten ist, dass es keine Intuition gab oder sich vorzustellen versuchte, was Zeiger tun. Wir haben gerade den Code in Algebra erklärt, und es ergab sich eine einigermaßen nette Implementierung. Ich habe es nicht ausgeführt, aber wenn ich keinen Algebra-Fehler gemacht habe (was möglich ist), sollte das "einfach funktionieren".

Beachten Sie, dass dies ein wenig anders ist als das typische Stack-basierte DFS, das Sie in Lehrbüchern sehen. Diese schieben alle Kinder eines neu gefundenen Knotens auf den Stapel, was als erstes Kind gemacht werden muss, um eine normale DFS-Reihenfolge zu erhalten.

Stattdessen drücken wir den Elternteil zusammen mit einer Ganzzahl, die sagt, welches Kind als nächstes gesucht werden soll. Dies ist der von Ihnen erwähnte Knoten + Iterator. Es ist ein bisschen komplexer, aber auch effizienter in der Stapelgröße. Die maximale Größe unseres Stapels ist O (D), wobei D die maximale Tiefe des Baumes ist. Die Größe des Stapels in dem Lehrbuchalgorithmus ist O (KD), wobei K die maximale Anzahl von Kindern ist, die ein Knoten haben kann.