Wie überquere ich einen Baum ohne Rekursion?

19

Ich habe einen sehr großen Knotenbaum im Speicher und muss den Baum durchlaufen. Übergeben der zurückgegebenen Werte jedes untergeordneten Knotens an den übergeordneten Knoten. Dies muss getan werden, bis alle Knoten ihre Datenblase bis zum Wurzelknoten haben.

Traversal funktioniert so.

private Data Execute(Node pNode)
{
    Data[] values = new Data[pNode.Children.Count];
    for(int i=0; i < pNode.Children.Count; i++)
    {
        values[i] = Execute(pNode.Children[i]);  // recursive
    }
    return pNode.Process(values);
}

public void Start(Node pRoot)
{
    Data result = Execute(pRoot);
}

Dies funktioniert einwandfrei, aber ich bin besorgt, dass der Aufrufstapel die Größe des Knotenbaums begrenzt.

Wie kann der Code umgeschrieben werden, damit keine rekursiven Aufrufe Executeerfolgen?

Reactgular
quelle
8
Sie müssten entweder Ihren eigenen Stapel verwalten, um die Knoten zu verfolgen, oder die Form des Baums ändern. Siehe stackoverflow.com/q/5496464 und stackoverflow.com/q/4581576
Robert Harvey
1
Ich habe auch viel Hilfe bei dieser Google-Suche gefunden , insbesondere bei Morris Traversal .
Robert Harvey
@RobertHarvey danke Rob, ich war mir nicht sicher, unter welchen Begriffen das gehen würde.
Reactgular
2
Sie könnten über die Speicheranforderungen überrascht sein, wenn Sie die Mathematik durchgeführt haben. Beispielsweise benötigt ein perfekt ausbalancierter Teranode-Binärbaum nur einen Stapel mit einer Tiefe von 40 Einträgen.
Karl Bielefeldt
@KarlBielefeldt Das setzt allerdings voraus, dass der Baum perfekt ausbalanciert ist. Manchmal muss man Bäume modellieren, die nicht ausbalanciert sind, und in diesem Fall ist es sehr einfach, den Stapel zu sprengen.
Servy

Antworten:

27

Hier ist eine allgemeine Tree Traversal-Implementierung, die keine Rekursion verwendet:

public static IEnumerable<T> Traverse<T>(T item, Func<T, IEnumerable<T>> childSelector)
{
    var stack = new Stack<T>();
    stack.Push(item);
    while (stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach (var child in childSelector(next))
            stack.Push(child);
    }
}

In deinem Fall kannst du es dann so nennen:

IEnumerable<Node> allNodes = Traverse(pRoot, node => node.Children);

Verwenden Sie zuerst a Queueanstelle von a Stackfür einen Atemzug und nicht zuerst die Tiefensuche. Verwenden Sie a PriorityQueuefür eine optimale erste Suche.

Servy
quelle
Bin ich zu Recht der Meinung, dass dies den Baum nur zu einer Sammlung zusammenfasst?
Reactgular
1
@ MathewFoscarini Ja, das ist sein Zweck. Natürlich muss es nicht notwendigerweise in einer tatsächlichen Sammlung materialisiert werden. Es ist nur eine Sequenz. Sie können darüber iterieren, um die Daten zu streamen, ohne den gesamten Datensatz in den Speicher ziehen zu müssen.
Servy
Ich denke nicht, dass dies das Problem löst.
Reactgular
4
Er durchläuft nicht nur den Graphen und führt unabhängige Operationen wie eine Suche durch, sondern aggregiert die Daten von den untergeordneten Knoten. Durch das Reduzieren des Baums werden die Strukturinformationen zerstört, die zum Ausführen der Aggregation erforderlich sind.
Karl Bielefeldt
1
Ich denke, dies ist die richtige Antwort, nach der die meisten Leute suchen, die diese Frage googeln. +1
Anders Arpi
4

Wenn Sie vorher eine Schätzung für die Tiefe Ihres Baums haben, reicht es in Ihrem Fall vielleicht aus, die Stapelgröße anzupassen? In C # seit Version 2.0 ist dies immer dann möglich, wenn Sie einen neuen Thread starten. Siehe hier:

http://www.atalasoft.com/cs/blogs/rickm/archive/2008/04/22/Erhöhen-der-Größe-Ihres-Stack-Net-Memory-Management-Teils-3.aspx

Auf diese Weise können Sie Ihren rekursiven Code beibehalten, ohne etwas Komplexeres implementieren zu müssen. Natürlich kann das Erstellen einer nicht rekursiven Lösung mit Ihrem eigenen Stack zeit- und speichereffizienter sein, aber ich bin mir ziemlich sicher, dass der Code nicht so einfach sein wird wie im Moment.

Doc Brown
quelle
Ich habe gerade einen kurzen Test gemacht. Auf meinem Computer konnte ich 14000 rekursive Aufrufe ausführen, bevor der Stapelüberlauf erreicht wurde. Wenn der Baum ausgeglichen ist, werden nur 32 Aufrufe benötigt, um 4 Milliarden Knoten zu speichern. Wenn jeder Knoten 1 Byte groß ist (was nicht der Fall ist), sind 4 GB RAM erforderlich, um einen ausgeglichenen Baum mit der Höhe 32 zu speichern.
Esben Skov Pedersen
Ich, wir sollten alle 14000 Aufrufe im Stapel verwenden. Der Baum würde 2,6x10 ^ 4214 Bytes belegen, wenn jeder Knoten ein Byte ist (was es nicht sein wird)
Esben Skov Pedersen
-3

Sie können eine Datenstruktur nicht in Form eines Baums ohne Verwendung von Rekursion durchlaufen. Wenn Sie die von Ihrer Sprache bereitgestellten Stapelrahmen und Funktionsaufrufe nicht verwenden, müssen Sie im Grunde genommen Ihre eigenen Stapel- und Funktionsaufrufe programmieren Es ist unwahrscheinlich, dass Sie es auf effizientere Weise in der Sprache schaffen als die Compiler-Autoren auf dem Computer, auf dem Ihr Programm ausgeführt wird.

Das Vermeiden von Rekursionen aus Angst vor Ressourcenbeschränkungen ist daher in der Regel falsch. Sicher ist, dass eine vorzeitige Ressourcenoptimierung immer falsch ist. In diesem Fall ist es jedoch wahrscheinlich, dass Sie die Speichernutzung auch dann nicht verbessern können, wenn Sie den Engpass messen und bestätigen Compiler-Writer.

Kilian Foth
quelle
2
Das ist einfach falsch. Es ist mit Sicherheit möglich, einen Baum ohne Rekursion zu durchlaufen. Es ist nicht einmal schwer . Sie können dies auch effizienter und ganz einfach tun, da Sie nur so viele Informationen in den expliziten Stapel aufnehmen können, wie Sie für Ihre spezifische Durchquerung benötigen. Bei Verwendung der Rekursion werden jedoch in vielen Fällen mehr Informationen gespeichert, als Sie tatsächlich benötigen Fälle.
Servy
2
Diese Kontroverse taucht hier gelegentlich auf. Einige Poster betrachten das Rollen des eigenen Stapels als keine Rekursion, während andere darauf hinweisen, dass sie genau das tun, was die Laufzeit sonst implizit tun würde. Über solche Definitionen zu streiten hat keinen Sinn.
Kilian Foth
Wie definieren Sie dann Rekursion? Ich würde es als eine Funktion definieren, die sich innerhalb ihrer eigenen Definition aufruft. Sie können mit Sicherheit einen Baum überqueren, ohne dies jemals zu tun, wie ich in meiner Antwort gezeigt habe.
Servy
2
Bin ich böse, wenn ich es genieße, jemanden mit einer so hohen Wiederholungszahl mit dem Downvote zu belohnen? Es ist so ein seltenes Vergnügen auf dieser Website.
Reactgular
2
Komm schon @Mat, das ist Kinderkram. Sie können anderer Meinung sein, wenn Sie Angst haben, auf einen zu tiefen Baum zu bombardieren, ist das ein vernünftiges Problem. Das kann man so sagen.
Mike Dunlavey