Einen Baum vertikal drucken

Du musst jeden Knoten einmal besuchen, um seinen Wert zu erhalten - also gibt es keine Alternative, als eine vollständige Traversierung zu machen, wie du gesagt hast. Es ist trivial, den horizontalen Abstand des aktuellen Knotens während des Traversierens zu verfolgen.

Sie können den ersten zu druckenden Wert nicht kennen, bis Sie den gesamten Baum durchlaufen haben. Sie müssen also alle Werte in einer Datenstruktur sammeln, bevor Sie etwas drucken. Also die einzige Wahl ist, welche Datenstruktur zu verwenden ist.

Welche Strukturen Ihnen zur Verfügung stehen, hängt von Ihrer Sprache ab.

Ich würde das Äquivalent zu Java Map<HorizontalDistance,List<Node>> Ihrer Sprache verwenden.

Ich sehe keine speziellen Anforderungen für Map . Die List muss billig sein, um hinzuzufügen. Wenn es sich um eine verkettete Liste handelt, sollte es zumindest einen Zeiger auf seinen Schwanz behalten. Es kann nicht viele Mainstream-List-Implementierungen geben, die diese Anforderung nicht erfüllen. Das Standard-Java LinkedList tut das.

Sie durchlaufen also den Baum in der Reihenfolge und rufen dies für jeden Knoten auf:

... und drucken Sie es dann aus, indem Sie die Map-Tasten durchlaufen und jede Liste drucken.

Sie könnten, denke ich, die Karte durch ein Array / eine Liste ersetzen, indem Sie Ihre positiven HDs auf gerade Indizes und Ihre negativen auf ungerade setzen.

Abhängig von der Kartenimplementierung - und der Array-Implementierung - und in einigen Sprachen, ob Sie genug wissen, um das Array im Voraus zu skalieren, ist dies möglicherweise schneller und speichereffizienter.

Ich bezweifle, dass die Double-Linked-List-Lösung viel schneller ist als die Map-Lösung, aber ich denke, Sie könnten es so machen:

Wenn Sie den Baum jedes Mal durchlaufen, wenn Sie nach links gehen, übergeben Sie den linken Knoten der doppelt verketteten Liste + die horizontale Entfernung dieses Knotens (d. h. den crt hd-1). Etwas Ähnliches mit dem Fall rechts.

Diese Aufgabe kann durch eine einfache Struktur erreicht werden, die als Reißverschluss bekannt ist. Diese Struktur dient dazu, den Zustand während der Reise durch die Liste beizubehalten. Es ist eine technische Struktur, die (einzelne) verkettete Liste auf zwei Teile aufteilt. Zuerst ist ein Teil der Liste links (oder vor) des aktuellen Ortes in umgekehrter Reihenfolge gespeichert und der zweite Teil ist Mitglieder übrig. Stellen Sie sich eine solche Struktur vor.

Oder in einer funktionalen Sprache mit Listen als einzelne verknüpfte Liste, zum Beispiel Erlang

Jedes Mitglied dieser Listen wird eine Liste mit einer vertikalen Linie sein.

Dann müssen wir die Operationen zip_left und zip_right definieren. Jeder dieser Vorgänge bewegt ein Element von einer Seite des Reißverschlusses zur anderen Seite. Diese Operation muss auch eine leere Liste erstellen, wenn kein Element zu entfernen ist. Zum Beispiel in Erlang:

[H|T] ist der Vorgang, den Kopf der Liste zu entfernen oder einen neuen Kopf zur Liste hinzuzufügen, abhängig davon, welche Seite von -> es ist. Auf der linken Seite wird es entfernt, auf der rechten Seite wird es hinzugefügt.

Dann müssen wir die Operation zip_add definieren, die den Baumknotenwert der entsprechenden vertikalen Linie hinzufügt. Nur für die Konvention nehmen Sie an, dass der aktuelle Wert der Kopf der rechten Seite des Reißverschlusses ist. Wir müssen mit der leeren Liste fertig werden.

Und jetzt müssen wir einfach einen Reißverschluss um den Baum schicken. Wenn wir nach rechts gehen, werden wir den Zip nach rechts bewegen und dann, wenn wir zurückkommen, den Teilbaum zurück nach links. Wenn wir nach links gehen, bewegen wir uns nach links und dann nach rechts. Es ist egal in welcher Reihenfolge. Es beeinflusst nur die Reihenfolge der Werte in jeder vertikalen Linie.

Und das ist alles. Alle Operationen zip_left , zip_right und zip_add sind O(1) -Operationen. In jedem Knoten führen wir sie eine bestimmte Anzahl von Wiederholungen durch ( zip_left x2, zip_right x2, zip_add x1), also ist es nett O(N) mit nur einer einfach verknüpften Listenstruktur. Die Implementierung in jeder Sprache ist ziemlich einfach, außer es wird weniger ausführlich sein.

Erste Baumformfrage

Zweiter Baum

Es gibt einen vollständigen Code mit einem hübschen Baumdrucker.

BTW Es gibt viel mehr Arten von Reißverschlüssen als für die Arbeit mit einzelnen verknüpften Listen. Zum Beispiel kann ein Reißverschluß zum Überqueren von Bäumen geschaffen werden, der eine Überlaufliste ohne Rekursion oder nur tailrekursive Funktionen erlaubt.

Dies erfordert 3 Durchgänge vollständiges Traversal, wenn Sie sie wirklich drucken möchten, anstatt sie nur zu speichern.

Wenn wir map anstelle von array verwenden, und auch nur Knoten in Listen nach vertikalen Linien speichern müssen und nicht drucken, dann reicht 1 pass full traversal aus.

Die folgende Idee geht davon aus, dass wir map nicht verwenden können, verwenden Sie einfach array.

1. Jeder Knoten hat eine virtuelle Position, linkes Kind hat pos-1, und rechtes Kind hat pos + 1

2. Durchquere den ganzen Baum (egal in welcher Reihenfolge), zeichne die am weitesten links stehende pos * min_pos * und die rechte pos * max_pos * auf. ( 1. Durchlauf )

3. Erstellen Sie eine Array-Länge ist max_pos-min_pos + 1, jeder Steckplatz ist eine leere Liste

4. Durchquere den ganzen Baum erneut, mit dem Array, dem min_pos und verfolge die Pos. Wenn wir einen Knoten besuchen, erhalten wir seinen pos, wir fügen den Knoten über den Index pos - min_pos zum Array hinzu. ( 2. Durchlauf )

5. Drucken Sie alle Listen im Array ( 3. Durchlauf )

Hier ist der Code in OCaml, ohne den letzten Druckteil.

Überprüfen Sie die horizontale Entfernung von der Wurzel zu allen Knoten, wenn zwei Knoten die gleiche horizontale Entfernung haben, dann befinden sie sich auf derselben vertikalen Linie. Speichern Sie diese horizontale Distanz in hash map .

C ++ - Codes

Doubly-Link-Liste-Ansatz: Stellen Sie sich jede vertikale Liste als einen Knoten in einer doppelt verknüpften Liste vor: Node1 & lt; - & gt; Node2 & lt; - & gt; Node3 & lt; - & gt; Node4 .....

Knoten1: 8 Knoten2: 4 Knoten3: 2,9 Knoten4: 1,5,6 ...

Die Idee ist: Wenn Sie zum linken Kind / Elternteil gehen, gehen Sie zum linken Knoten in der verknüpften Liste, speichern Sie den Baumknoten im aktuellen Knoten der verknüpften Liste; Wenn du zum rechten Kind / Elternteil gehst, gehst du den rechten Knoten in der verknüpften Liste, speichere den Knoten wie oben.

Der Knoten ganz links würde die linke Liste ganz links speichern, in diesem Fall Knoten1. Sie können diese verknüpfte Liste von links nach rechts drucken, um das Endergebnis zu erhalten.

Hier ist Map-basierte Java-Implementierung

Hier ist Unit Test