Algorithmus zur Implementierung nicht-binärer Bäume mit 1-dimensionalen Vektor?

Wenn Sie nur einen Vektor verwenden können (nicht in Frage gestellt), und Knoten sollten nicht seine eigene Liste enthalten, nur einige Zeiger (Adressen in Vektor), dann können Sie dies versuchen:

1. jeder Knoten enthält die Adresse seines Geschwisters
2. erster Knoten nach gegeben (wenn es nicht sein Geschwister ist) ist Kind, mit Zeiger auf das zweite Kind und so weiter
3. jedes Kind hat eigene Kinder

Also für einen Baum wie folgt:

Ihr Vektor würde wie folgt aussehen:

Dabei ist _ der Nullzeiger

Bearbeiten:
Ein anderer Ansatz:

1. jeder Knoten enthält die Adresse der Region im Vektor, der von seinen Kindern besetzt ist
2. Kinder sind nebeneinander
3. Es gibt einen Null-Knoten im Vektor und markiert das Ende der Geschwistergruppe

Für diesen Ansatz würde ein gegebener Baum wie folgt aussehen:

Auf diese Weise können Sie leicht untergeordnete Elemente jedes beliebigen Knotens finden und das Array reorganisieren, ohne alle Elemente zu verschieben (kopieren Sie einfach die untergeordneten Elemente an das Ende der Tabelle, aktualisieren Sie den Zeiger und fügen Sie das nächste untergeordnete Element hinzu).

Was Sie im Grunde tun, ist, die Anfänge eines Speichermanagers für einen Lisp-Interpreter zu schreiben, indem Sie die Elemente des Vektors in Cons-Zellen paaren. Hier ist so etwas, was ich gerade in C zusammen gemacht habe:

Die Standardmethode zum Speichern eines vollständigen binären Baums in einem Array (wie für binäre Heap-Implementierungen) ist schön, weil Sie den Baum mit einem Array von Elementen in der Reihenfolge eines traversalen Levels darstellen können. Unter Verwendung dieses Schemas gibt es schnelle Tricks zum Berechnen der Eltern- und Kindknotenpositionen. Der Wechsel zu einem Baum, in dem jeder Knoten eine beliebige Anzahl von Elementen haben kann, löst einen solchen Ansatz aus.

Es gibt jedoch verschiedene Schemata, um beliebige Bäume als Binärbäume darzustellen. Sie werden ausführlich in Donald Knuths Art of Computer Programming, Band I, Abschnitt 2.3, besprochen.

Wenn die Knoten selbst einen Zeiger enthalten dürfen, könnten Sie für jeden Knoten eine Liste mit Kind-Indizes speichern. Ist das in Ihrem Fall möglich?

Sie können es mithilfe einer eindimensionalen verketteten Liste mit geringem Overhead implementieren.

Jeder Elternteil wird Zeiger auf seine Kinder enthalten (aber dies erfordert eine Entscheidung, ob die maximale Anzahl von Knoten vorher bekannt ist).

Für einen Baum mit A als Wurzelknoten und B, C, D als Kinder wird die Darstellung wie folgt aussehen.

A - & gt; B A - & gt; C A - & gt; D

Beachten Sie, dass es drei Links von A gibt.

Eine Möglichkeit, die Obergrenze für die Anzahl der Knoten zu überwinden, ist ein zusätzlicher Zeiger in den Knoten.

Also, jetzt A - & gt; (Kind) B - & gt; (Adj) - & gt; (Adj) C - & gt; (Adj) - & gt; D

In diesem Fall ist es ziemlich kompliziert, den Baum zu aktualisieren, wenn das Löschen auftritt.

Es ist noch einfacher, bessere Datenstrukturen zu entwerfen, wenn Sie Ihre Zeitgrenzen für die verschiedenen Operationen angeben können.

Ohne Einschränkungen für die Werte der Knoten und unter der Annahme, dass Sie nur eine einzige Liste verwenden können, würde ich sie wie folgt konstruieren:

Stellen Sie jeden Knoten als ( val ; [ int ; ...] ) dar, wobei val der Wert des Knotens ist und jedes int die Position in der Liste eines seiner untergeordneten Elemente ist. Verwenden Sie bei Bedarf ein nicht druckbares Trennzeichen.

Traversal ist sehr langsam.