Rekursion und Durchqueren eines Binomialbaums

Question

Ich habe folgende Baumstruktur:

Dieser zeigt 3 Ebenen. Mein eigentliches Problem wird 8 bis 12 Ebenen haben. Ich habe das folgende Programm, von dem ich glaube, dass es den Baum in der richtigen Reihenfolge durchquert. Zwei untergeordnete Knoten melden sich an einen übergeordneten Knoten. Wenn wir beide Kinder kennen, können wir die Eltern finden. Im Wesentlichen wollen wir den Baum von rechts nach links und von unten nach oben durchqueren. Die Zahlen geben die Reihenfolge an, in der die Knoten durchlaufen werden müssen.

Hier ist mein Code, von dem ich glaube, dass er dies erreichen wird:

#include <stdio.h>

int main(void)
{
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            for (int k = 0; k < 2; k++)
            {
                printf("k loop: %d   ", i * 7 + j * 3 + k);
            }
            printf("\n");
            printf("j loop: %d  \n", i * 7 + j * 3 + 2);
        }
        printf("i loop: %d  \n", i * 7 + 6);
    }
    printf("final node: %d\n", 2 * 2 * 2 * 2 - 2);
}

Dies ist nicht sehr hübsch und nicht sehr skalierbar, da ich für jede weitere Ebene eine weitere for-Schleife hinzufügen müsste.

drei Fragen:

1. Wie würde ich das mit Rekursion machen?
2. Gibt es eine skalierbarere Möglichkeit, dies ohne Rekursion zu tun?
3. Dies ist schneller als ein For-Loop-Ansatz oder ein Rekursionsansatz

Answer 1

Sie können dies rekursiv mit den folgenden Schritten ausführen p(n, level):

• Wenn level > 0ja, drucken Sie zuerst die Teilbäume mit
  • Rufen Sie n = p(n, level - 1)für den linken Teilbaum
  • Rufen Sie n = p(n, level - 1)nach dem richtigen Teilbaum
• dann ausdrucken nund zurücksendenn+1

Hier ist eine naive Implementierung:

#include <stdio.h>

int p(int n, int level) {
    if (level > 0) {
        n = p(n, level - 1);
        n = p(n, level - 1);
    }
    printf("%i\n", n);
    return n + 1;
}

// initial call for a depth of 8:
int main() {
    p(0, 8);
    return 0;
}

Answer 2

1. Was Sie suchen, wird als In-Order-Traversal bezeichnet . Es ist im Allgemeinen unabhängig von der Anzahl der Ebenen in Ihrem Baum, da es sich um eine Art Tiefen-Erst-Durchquerung handelt .

Es folgt im Allgemeinen dem folgenden Algorithmus

1. Rekursiv den linken Teilbaum durchlaufen
2. Besuchen Sie den Stammknoten
3. Rekursiv den rechten Teilbaum durchlaufen

Hier ist ein Link für weitere Informationen

---

1. Es ist durchaus möglich und allgemein empfohlen, iterative Methoden der Baumdurchquerung zu verwenden. Obwohl bei kleinen Bäumen die Auswirkungen nicht wirklich zu spüren sind, beansprucht die große rekursive Durchquerung exponentiell viel Speicherplatz. Hier ist ein Beispiel für die In-Order-Durchquerung mit einem Stapel auf Geekforgeeks

---

1. Obwohl Sie es bei einem kleinen Baum nicht bemerken, ist der rekursive Ansatz immer langsamer als die Iteration.