Ist es möglich, iterative * Vorbestellung * Traversierung in einem binären Baum durchzuführen, ohne Knoten-Stacks oder "besuchte" Flags zu verwenden?
Soweit ich weiß, erfordern solche Ansätze normalerweise, dass die Knoten im Baum Zeiger auf ihre Eltern haben. Nun, um sicher zu sein, weiß ich, wie man die Traversierung vor der Order mit den Eltern-Pointern und visited-flags durchführt, wodurch die Notwendigkeit von Knotenstapeln für iteratives Traversal entfällt.
Aber ich habe mich gefragt, ob Besuchsflaggen wirklich notwendig sind. Sie würden viel Speicher belegen, wenn der Baum viele Knoten hat. Außerdem wäre es nicht sinnvoll, sie zu haben, wenn viele Baumüberquerungen vor einem Baum eines Binärbaums parallel gleichzeitig ausgeführt werden.
Wenn es möglich ist, dies durchzuführen, wäre ein Pseudocode oder besser ein kurzes C ++ - Codebeispiel wirklich nützlich.
BEARBEITEN: Ich möchte insbesondere nicht die Rekursion für die Vorbestellung verwenden. Der Kontext für meine Frage ist, dass ich einen Octree (der wie ein Binärbaum ist), den ich auf der GPU konstruiert habe. Ich möchte viele Threads starten, von denen jeder unabhängig voneinander und parallel eine Baumdurchquerung durchführt.
Erstens unterstützt CUDA keine Rekursion. Das Konzept der besuchten Flags gilt nur für eine einzelne Traversierung. Da viele Durchquerungen gleichzeitig ablaufen, hat das Besuchten-Flag-Feld in der Knotendatenstruktur keinen Nutzen. Sie würden nur auf der CPU sinnvoll sein, wo alle unabhängigen Baumdurchquerungen serialisiert werden / können. Um genauer zu sein, können wir die visited-flags nach jedem Tree-Traversal auf false setzen, bevor wir eine weitere Tree-Traversal-Pre-Order durchführen.
Sie können diesen Algorithmus verwenden, der nur übergeordnete Zeiger und keinen zusätzlichen Speicher benötigt:
Für einen inneren Knoten ist der nächste Knoten in einer Pre-Order-Traversierung sein linkstes Kind.
Für einen Blattknoten: Gehen Sie im Baum nach oben, bis Sie vom linken Kind eines Knotens mit zwei Kindern kommen. Das rechte Kind dieses Knotens wird dann als nächster Knoten durchlaufen.
%Vor%Sie können jedem Blattknoten einen Zeiger auf den Knoten geben, der nach einer Preorder-Traversierung als nächstes kommen würde.
Zum Beispiel, angesichts der binären Struktur:
%Vor%D müsste einen Zeiger auf E speichern, und F müsste einen Zeiger auf C speichern. Dann können Sie den Baum einfach iterativ durchlaufen, als wäre es eine verknüpfte Liste.
Sie können dies ohne zusätzlichen Speicher tun, indem Sie den gleichen Zeiger sowohl im linken als auch im rechten Teilbaumknoten speichern. Da eine solche Struktur in einem Baum nicht erlaubt ist (das würde sie zu einem DAG machen), können Sie sicher schließen, dass jeder Knoten, auf den alle "Child" -Zeiger auf denselben Platz zeigen, ein Blattknoten ist.
Wenn Sie darauf bestehen, können Sie jeden möglichen Pfad durch den Baum nummerieren und dann jedem Worker diesen Pfad folgen lassen.
Ihr Nummerierungsschema kann einfach sein, dass jedes Nullbit das linke Kind und jedes Einbit das richtige Kind nimmt. Um eine Tiefensuche durchzuführen, verarbeiten Sie Ihre Nummer von niedrigstwertigem Bit zu höchstwertig.
Obwohl es nicht notwendig ist, die Tiefe des Baumes im Voraus zu kennen, müssen Sie den Fall behandeln, in dem alle weiteren Zahlen auf ein Blatt treffen, bevor die Zahl vollständig verbraucht ist.
Es gibt einen Hack, der die absoluten Werte der Zeiger {- & gt; links, - & gt; rechts} verwendet, um ein Bit pro Knoten zu codieren. Es braucht einen ersten Durchlauf, um die Anfangszeiger- "Polarität" richtig zu bekommen. Es scheint DSW genannt zu werden. Weitere Informationen finden Sie in diesem Ссылка Usenet-Thread.
Ich weiß nicht, ob es zu Quad-Bäumen oder Okt-Bäumen erweitert werden kann, und ich bezweifle ernsthaft, ob es auf Multithread-Zugriff erweitert werden kann. Das Hinzufügen eines Elternzeigers ist wahrscheinlich einfacher ...
Eine Richtung, die Sie in Betracht ziehen sollten, besteht darin, die Knoten des Baums zu löschen, während Sie sie durchqueren, und diese Knoten in einen neuen Baum einzufügen. Wenn Sie Knoten in Vorbestellung einfügen, wird der neue Baum genau gleich sein. Aber das Problem hier ist, wie erhalten Sie die Integrität der ursprünglichen Struktur beim Löschen von Elementen.
Tags und Links algorithm