So durchlaufen Sie einen Binärbaum in O (n) -Zeit ohne zusätzlichen Speicher

Question

Gegeben ein Binärbaum mit einer ganzen Zahl, Left & Rechte Zeiger, wie kann man den Baum in O (n) -Zeit und O (1) Extra-Speicher durchlaufen (kein Stapel/Warteschlange/Rekursion)?

This guy ergab eine Lösung, die nicht O (n) Gesamtzeit ist, die den aktuellen Pfad als Ganzzahl codiert (und daher für Bäume mit begrenzter Tiefe funktioniert).

Ich bin für die klassische Lösung

(SPOILER)

, die die Eltern jedes Knotens in den Kindern codiert.

Answer 1

Jedes gute Algorithmus Buch wird diesen Algorithmus haben, schauen Sie z.B. in Knuth (TAOCP I.2.3.1 Traversing binary trees, Übung 21). Da dieser Algorithmus jedoch den vorhandenen Baum ändert, müssen Sie in einer Umgebung mit mehreren Threads extreme Vorsicht verwenden.

Sie können auch Gewindebäume verwenden (siehe Knuth).

Answer 2

Der Typ-Algorithmus ist interessant, aber es muss darauf hingewiesen werden, dass es funktioniert O erfordern (log n) zusätzliche Bits Platz, um einen binären Baum mit n Knoten zu durchqueren. Platzanforderungen müssen in Bits und nicht in Bytes gemessen werden - normalerweise fallen sie in dieselbe Sache zusammen, wenn Big-Oh-Notation verwendet wird, aber Fälle wie diese weisen darauf hin, warum es wichtig ist, die Unterscheidung zu treffen.

Um dies zu sehen, fragen Sie, wie ein Baum mit mehr als 2^32-1 Knoten mit einer einzigen Ganzzahl von Speicher (auf einer 32-Bit-Plattform) durchlaufen werden kann.

Answer 3

Verwenden Sie den O (1) -Speicher, um sich an den Zeiger "Zuletzt besuchter Knoten" zu erinnern. Sie können es auf 0 oder einen unbekannten Wert initialisieren.

Um den Baum zu begehen, beginnen Sie am Wurzelknoten. Sehen Sie sich beide Kinder des Knotens an. Wenn Ihr "zuletzt besuchter Knoten" gleich dem RECHTEN Knoten ist, wechseln Sie zum übergeordneten Knoten. Wenn "Zuletzt besucht" gleich dem LINKEN Knoten ist, dann gehe zum rechten Knoten. Sonst gehe zum linken Knoten.

Wiederholen Sie den Vorgang, bis Sie den ganzen Baum fertiggestellt haben. Die einzige wirkliche Schlauheit ist, die eine Variable zu verwenden, um sich daran zu erinnern, woher du kommst, um zu entscheiden, wohin du als nächstes gehst. Dies macht die Durchquerung deterministisch.

Sie werden am Ende O (n) Schritte nehmen. Du wirst jeden mittleren Knoten dreimal und jedes Blatt einmal besuchen, also bist du immer noch O (N). Lagerung ist O (1).

Answer 4

Die Hauptidee ist ähnlich dem Listeninversionsalgorithmus, mit einem super-hässlichen kniffligen Hack (aus theoretischer Sicht wahrscheinlich ein Cheat), basierend auf der Tatsache, dass Zeiger (in allen derzeit dem Menschen bekannten Sprachen) sind), 0 Modus 4 als Ganzzahlen.

Die Idee ist, dass Sie die Zeiger auf dem Pfad den Baum nach unten zeigen können, um nach oben zu zeigen. Das Problem ist, dass - und das ist, wo Sie von der Liste Inversion Algorithmus umleiten - wenn Sie Backtrack müssen Sie wissen, ob links oben oder rechts zeigt nach oben; An diesem Punkt benutzen wir den Hack.

Pseudo-Code folgt:

current = root->left 
next = current 
while (current != null) { 
    next = current->left 
    current->left = static_cast<int>(prev) + 1 // ugly hack. 
    current = next 
} 
status = done 
while (current != root or status != done) { 
    if (status = done) { 
    if (static_cast<u32>(current->left) %4 = 1) { 
     next = static_cast<u32>(current->left) -1 
     current->left = prev 
     status = middle 
    } 
    else { 
     next = current->right 
     current->right = prev 
     status = done 
    } 
    prev = current 
    current = next 
    } 
    else if (status == left) { 
    if (current->left) { 
     prev = current->left 
     current->left = static_cast<u32>(next) +1 
     next = current 
    } 
    else 
     status = middle 
    } 
    else if (status == right) { 
    if (current->right) { 
     prev = current->right; 
     current ->right = next; 
     next = current 
    } 
    else 
     status = done 
    } 
    else {// status == middle 
    work_on_node(current) 
    status = right 
    } 
} 

Answer 5

Hier ist eine andere Lösung

http://sites.google.com/site/debforit/efficient-binary-tree-traversal-with-two-pointers

Aber ich frage mich, ob es einen Weg gibt diese in Sprachen wie Java zu tun, die keine Zeiger in wahrer Sinn.