Kann mir bitte jemand helfen, den folgenden Morris-Inorder-Tree-Traversal-Algorithmus zu verstehen, ohne Stapel oder Rekursion zu verwenden? Ich habe versucht zu verstehen, wie es funktioniert, aber es entgeht mir nur.
1. Initialize current as root
2. While current is not NULL
If current does not have left child
a. Print current’s data
b. Go to the right, i.e., current = current->right
Else
a. In current's left subtree, make current the right child of the rightmost node
b. Go to this left child, i.e., current = current->left
Ich verstehe, dass der Baum so modifiziert ist, dass der current node
, der right child
aus dem max node
In gemacht wird, right subtree
und verwende diese Eigenschaft für die Inorder Traversal. Aber darüber hinaus bin ich verloren.
BEARBEITEN: Diesen zugehörigen C ++ - Code gefunden. Es fiel mir schwer zu verstehen, wie der Baum wiederhergestellt wird, nachdem er geändert wurde. Die Magie liegt in der else
Klausel, die getroffen wird, sobald das rechte Blatt geändert wird. Siehe Code für Details:
/* Function to traverse binary tree without recursion and
without stack */
void MorrisTraversal(struct tNode *root)
{
struct tNode *current,*pre;
if(root == NULL)
return;
current = root;
while(current != NULL)
{
if(current->left == NULL)
{
printf(" %d ", current->data);
current = current->right;
}
else
{
/* Find the inorder predecessor of current */
pre = current->left;
while(pre->right != NULL && pre->right != current)
pre = pre->right;
/* Make current as right child of its inorder predecessor */
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}
// MAGIC OF RESTORING the Tree happens here:
/* Revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else
{
pre->right = NULL;
printf(" %d ",current->data);
current = current->right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */
}
c++
binary-tree
tree-traversal
Brainydexter
quelle
quelle
pre->right = NULL;
Antworten:
Wenn ich den Algorithmus richtig lese, sollte dies ein Beispiel dafür sein, wie er funktioniert:
Erstens
X
ist die Wurzel, also wird sie als initialisiertcurrent
.X
hat ein linkes Kind, wird alsoX
zum am weitesten rechts stehenden Kind desX
linken Teilbaums gemacht - dem unmittelbaren VorgängerX
einer ungeordneten Durchquerung. SoX
wird das richtige Kind daraus gemachtB
, danncurrent
wird auf gesetztY
. Der Baum sieht jetzt so aus:(Y)
oben bezieht sich aufY
und alle seine Kinder, die für Rekursionsprobleme weggelassen werden. Der wichtige Teil ist trotzdem aufgeführt. Nachdem der Baum eine Verknüpfung zu X hat, wird die Durchquerung fortgesetzt ...Dann
A
wird ausgegeben, weil es kein linkes Kind hat, und escurrent
wird zu dem zurückgegebenY
, dasA
in der vorherigen Iteration zum rechten Kind gemacht wurde. Bei der nächsten Iteration hat Y beide Kinder. Die Doppelbedingung der Schleife lässt sie jedoch anhalten, wenn sie sich selbst erreicht. Dies ist ein Hinweis darauf, dass der verbleibende Teilbaum bereits durchlaufen wurde. Also druckt es sich selbst und fährt mit seinem rechten Teilbaum fort, nämlichB
.B
druckt selbst, und danncurrent
wirdX
, die durch die gleiche Prüfprozess geht wieY
tat, auch , dass sein linker Teilbaum durchlaufen wurde realisiert, mit der fortZ
. Der Rest des Baumes folgt dem gleichen Muster.Es ist keine Rekursion erforderlich, da anstelle des Zurückverfolgens durch einen Stapel eine Verknüpfung zurück zur Wurzel des (Unter-) Baums an den Punkt verschoben wird, an dem in einem rekursiven Inorder-Tree-Traversal-Algorithmus ohnehin darauf zugegriffen werden würde - nach dessen linker Teilbaum ist fertig.
quelle
Die rekursive In-Order-Durchquerung ist :
(in-order(left)->key->in-order(right))
. (Dies ist ähnlich wie bei DFS)Wenn wir die DFS durchführen, müssen wir wissen, wohin wir zurückkehren müssen (deshalb behalten wir normalerweise einen Stapel).
Wenn wir einen übergeordneten Knoten durchlaufen, zu dem wir zurückverfolgen müssen ->, finden wir den Knoten, von dem wir zurückverfolgen müssen, und aktualisieren seine Verknüpfung zum übergeordneten Knoten.
Wann ziehen wir uns zurück? Wenn wir nicht weiter gehen können. Wann können wir nicht weiter gehen? Wenn kein linkes Kind anwesend ist.
Wohin ziehen wir zurück? Hinweis: an den NACHFOLGER!
Wenn wir also Knoten entlang des untergeordneten Pfades folgen, stellen Sie den Vorgänger bei jedem Schritt so ein, dass er auf den aktuellen Knoten zeigt. Auf diese Weise erhalten die Vorgänger Links zu Nachfolgern (ein Link zum Zurückverfolgen).
Wir folgen links, solange wir können, bis wir zurückgehen müssen. Wenn wir zurückverfolgen müssen, drucken wir den aktuellen Knoten und folgen dem richtigen Link zum Nachfolger.
Wenn wir gerade zurückgegangen sind -> müssen wir dem rechten Kind folgen (wir sind mit dem linken Kind fertig).
Wie kann man feststellen, ob wir gerade zurückgegangen sind? Holen Sie sich den Vorgänger des aktuellen Knotens und prüfen Sie, ob er eine richtige Verknüpfung (zu diesem Knoten) hat. Wenn ja - dann sind wir ihm gefolgt. Entfernen Sie den Link, um den Baum wiederherzustellen.
Wenn es keinen linken Link gab => haben wir nicht zurückverfolgt und sollten den linken Kindern folgen.
Hier ist mein Java-Code (Entschuldigung, es ist nicht C ++)
quelle
Ich habe hier eine Animation für den Algorithmus erstellt: https://docs.google.com/presentation/d/11GWAeUN0ckP7yjHrQkIB0WT9ZUhDBSa-WR0VsPU38fg/edit?usp=sharing
Dies sollte hoffentlich zum Verständnis beitragen. Der blaue Kreis ist der Cursor und jede Folie ist eine Iteration der äußeren while-Schleife.
Hier ist der Code für Morris Traversal (ich habe ihn von Geeks für Geeks kopiert und geändert):
quelle
print(cursor.value)
nachpre.right = None
Zeile hinzufügenIch denke, dieser Code wäre besser zu verstehen. Verwenden Sie einfach eine Null, um Endlosschleifen zu vermeiden. Sie müssen keine andere Magie verwenden. Es kann leicht auf Vorbestellung geändert werden.
quelle
temp.left = null
Baum verloren.Ich fand eine sehr gute bildliche Erklärung von Morris Traversal .
quelle
Ich hoffe, der folgende Pseudocode ist aufschlussreicher:
Unter Bezugnahme auf den C ++ - Code in der Frage findet die innere while-Schleife den Vorgänger in der Reihenfolge des aktuellen Knotens. In einem Standard-Binärbaum muss das rechte untergeordnete Element des Vorgängers null sein, während in der Thread-Version das rechte untergeordnete Element auf den aktuellen Knoten zeigen muss. Wenn das rechte untergeordnete Element null ist, wird es auf den aktuellen Knoten gesetzt, wodurch effektiv das Threading erstellt wird , das als Rückgabepunkt verwendet wird, der andernfalls gespeichert werden müsste, normalerweise auf einem Stapel. Wenn das rechte untergeordnete Element nicht null ist, stellt der Algorithmus sicher, dass der ursprüngliche Baum wiederhergestellt wird, und setzt dann das Durchlaufen des rechten Teilbaums fort (in diesem Fall ist bekannt, dass der linke Teilbaum besucht wurde).
quelle
Python-Lösung Zeitkomplexität: O (n) Raumkomplexität: O (1)
Ausgezeichnete Morris Inorder Traversal Erklärung
quelle
PFB Erklärung von Morris In-Order Traversal.
quelle