Kann ein Baum ohne Rekursion, Stapel oder Warteschlange und nur mit einer Handvoll Zeigern überquert werden?

Vor einem halben Jahrzehnt saß ich in einer Klasse für Datenstrukturen, in der der Professor zusätzliche Anrechnungspunkte anbot, wenn jemand einen Baum ohne Verwendung von Rekursion, Stapel, Warteschlange usw. (oder einer ähnlichen Datenstruktur) und nur ein paar Zeigern durchqueren konnte. Ich fand eine aus meiner Sicht offensichtliche Antwort auf diese Frage, die schließlich vom Professor akzeptiert wurde. Ich saß in einer diskreten Matheklasse mit einem anderen Professor in derselben Abteilung - und er behauptete, es sei unmöglich, einen Baum ohne Rekursion, Stapel, Warteschlange usw. zu durchqueren, und meine Lösung sei ungültig.

Also ist es möglich oder unmöglich? Warum oder warum nicht?

Bearbeiten: Um etwas Klarheit zu schaffen, habe ich dies in einem Binärbaum implementiert, der drei Elemente enthält - die auf jedem Knoten gespeicherten Daten und Zeiger auf zwei untergeordnete Elemente. Meine Lösung konnte mit wenigen Änderungen auf n-fache Bäume ausgeweitet werden.

Mein Lehrer für Datenstrukturen stellte keine Einschränkungen gegen das Mutieren des Baums, und tatsächlich stellte ich später fest, dass seine eigene Lösung darin bestand, die untergeordneten Zeiger zu verwenden, um den Baum auf seinem Weg nach unten wieder nach oben zu zeigen. Mein diskreter Mathematikprofessor sagte, jede Mutation eines Baums bedeute, dass es sich nicht mehr um einen Baum gemäß der mathematischen Definition eines Baums handele. Seine Definition würde auch Hinweise auf Eltern ausschließen - was dem Fall entsprechen würde, in dem ich ihn oben gelöst habe.

Auf diesem Gebiet wurde viel Forschung betrieben, die durch die Methode der "billigen" Durchquerung von Bäumen und durch allgemeine Listenstrukturen im Zusammenhang mit der Müllabfuhr motiviert wurde.

Ein Threaded-Binärbaum ist eine angepasste Darstellung von Binärbäumen, bei der einige Nullzeiger zum Verknüpfen mit Nachfolgeknoten im Baum verwendet werden. Diese zusätzlichen Informationen können verwendet werden, um einen Baum ohne Stapel zu durchlaufen. Es ist jedoch ein zusätzliches Bit pro Knoten erforderlich, um Threads von untergeordneten Zeigern zu unterscheiden. Wikipedia: Tree_traversal

Soweit ich weiß, können Binärbäume, die mit Zeigern wie üblich implementiert wurden (linker und rechter Zeiger pro Knoten), mit der Methode von Threads durchlaufen werden, die Morris zugeschrieben wird . Die NIL-Zeiger werden vorübergehend wiederverwendet, um einen Pfad zum Stamm zurückzugewinnen. Der clevere Teil ist, dass man während des Traversierens die ursprünglichen Kanten von den temporären Fadenverbindungen unterscheiden kann, indem man die Art und Weise verwendet, wie sie Zyklen im Baum bilden.

Guter Teil: keine zusätzliche Datenstruktur. Schlimme: leicht zu betrügen, der Stapel innerhalb der Baum in einer klugen Weise. Sehr schlau.

Ein Beweis für den verborgenen Stapel ist in P. Mateti und R. Manghirmalani zu sehen: Morris 'Tree Traversal Algorithm Reconsidered DOI: 10.1016 / 0167-6423 (88) 90063-9

JM Morris: Binäre Bäume einfach und billig durchqueren. IPL 9 (1979) 197-200 DOI: 10.1016 / 0020-0190 (79) 90068-1

Dann ist da noch Lindstroms Scannen. Diese Methode "dreht" die drei Zeiger, die an jedem Knoten beteiligt sind (übergeordnete und zwei untergeordnete). Wenn Sie ordentliche Vorbestellungs- oder Nachbestellungsalgorithmen ausführen möchten, benötigen Sie zusätzliche Bits pro Knoten. Wenn Sie nur alle Knoten besuchen möchten (dreimal, aber nie wissen, welchen Besuch Sie durchführen), können Sie auf die Bits verzichten.

G. Lindstrom: Durchsuchen von Listenstrukturen ohne Stapel oder Markierungsbits. IPL 2 (1973) 47-51. DOI: 10.1016 / 0020-0190 (73) 90012-4

Der vielleicht einfachste Weg ist eine Methode von Robson . Hier wird der für den klassischen Algorithmus benötigte Stack durch die Blätter gezogen.

JM Robson: Ein verbesserter Algorithmus zum Durchlaufen von Binärbäumen ohne Hilfsstapel IPL 1 (1973) 149-152. 10.1016 / 0020-0190 (73) 90018-5

IPL = Information Processing Letters

$v$

Meine Lösung war eine brutth-first-Überquerung, bei der verschachtelte for-Schleifen verwendet wurden, um den Baum brutal zu forcieren. Dies ist keineswegs effizient, und tatsächlich bittet eine rekursive Datenstruktur wie ein Baum um eine rekursive Durchquerung, aber die Frage war nicht, ob ein Baum effizient durchquert werden konnte, sondern ob es überhaupt möglich war.

Pseudocode:
root = pointer root 
depth = integer 0
finished = bool false
//If we n-ary tree also track how many children have been found 
//on the node with the most children for the purposes of this psuedocode 
//we'll assume a binary tree and insert a magic number of 2 so that we 
//can use bitwise operators instead of integer division 
while(!finished)
    ++depth
    treePosition = pointer root
    finished = true;
    for i := 0..2**depth
        for j := 0..depth
            if (i & j) //bitwise operator explained below
                // if right child doesn't exist break the loop
                treePosition = treePosition.rightChild
            else
                // if left child doesn't exist break the loop
                treePosition = treePosition.leftChild
        if j has any children
            finished = false
            do anything else you want when visiting the node

Wie Sie sehen, sieht der bitweise Operator im Pseudocode für die ersten Ebenen einfach so aus:

2**1       0               1
2**2   00      01      10      11
2**3 000 001 010 011 100 101 110 111

Für n-ary würden Sie i% (maxChildren ** j) / j nehmen, um zu bestimmen, welcher Pfad zwischen 0 und maxChildren liegen soll.

An jedem Knoten auf n-ary müssten Sie außerdem überprüfen, ob die Anzahl der untergeordneten Knoten größer als maxChildren ist, und diese entsprechend aktualisieren.