Wie viele Überquerungen müssen bekannt sein, um ein BST

Question

ich durch eine Reihe von Artikeln an verschiedenen Standorten sind sehr verwirrt zu konstruieren, in Bezug auf ein Binary Search Tree von einem Traversal Konstruktion (pre, post oder in-order) oder einer Kombination von beliebigen zwei von ihnen . Zum Beispiel, bei this Seite, heißt es, dass gegeben pre, post oder level Reihenfolge Traversal, zusammen mit der in-order Traversal, kann man die BST konstruieren. Aber here und there, zeigen sie uns, um einen BST von pre-order allein zu konstruieren. Auch, here sie zeigen uns, wie man die BST von pre und post-order Traversalen zu konstruieren. An einer anderen Stelle fand ich eine Lösung, um aus der post-order Traversierung nur eine BST zu konstruieren.

Jetzt weiß ich, dass angesichts der inorder und pre-order Traversalen ist es möglich, eine BST eindeutig zu bilden. Was den ersten Link, den ich zur Verfügung gestellt, obwohl sie sagen, dass wir nicht die BST von pre-order und post-order konstruieren können, kann ich nicht sortieren gerade die post-order Array bekommen seine inorder Traversal, und dann verwenden, und die pre-order Array der Bildung BST? Wird das gleiche wie die Lösung in der vierten Verbindung oder anders sein? Und gegeben nur pre-order, kann ich das sortieren, um die in-order zu bekommen, dann benutze das und die pre-order, um die BST zu bekommen. Muss sich das wieder von der Lösung bei den Links 2 und 3 unterscheiden?

Spezifisch, was ist ausreichend, um die BST eindeutig zu generieren? Wenn keine Eindeutigkeit erforderlich ist, kann ich sie einfach sortieren, um die in-order Traversierung zu erhalten und eine der N möglichen BST s davon rekursiv aufzubauen.

Answer 1

Um eine BST zu erstellen, benötigen Sie nur eine Traversierung (nicht in der Reihenfolge).

Um einen Binärbaum zu erstellen, benötigen Sie im Allgemeinen zwei Durchläufe, in der Reihenfolge und zum Beispiel vorbestellen. Für den speziellen Fall von BST - das In-Order-Traversal ist immer das sortierte Array, das die Elemente enthält, so dass Sie es immer rekonstruieren können und einen Algorithmus verwenden können, um einen generischen Baum aus Vororder- und In-Order-Traversalen zu rekonstruieren.

Also die Information, dass der Baum eine BST ist, zusammen mit den Elementen darin (sogar ungeordnet) sind äquivalent zu einer In-Order-Traversierung.

Bonus: Warum ist eine Traversierung nicht genug für einen allgemeinen Baum, (ohne die Information ist es eine BST)?
Antwort: Nehmen wir an, wir haben n verschiedene Elemente. Es gibt n! mögliche Listen zu diesen n Elementen, jedoch - die mögliche Anzahl der Bäume ist viel größer (2 * n! Mögliche Bäume für die n Elemente sind alle verfallenen Bäume, so dass in jedem Knoten, also der Baum ist eigentlich eine Liste Es gibt solche Bäume, und andere n! Bäume, wo immer node.left = null) Also, vom Taube-Loch-Prinzip - es gibt mindestens eine Liste, die 2 Bäume generiert, also können wir den Baum nicht aus einer einzigen Traversierung rekonstruieren. (QED)

Answer 2

Wenn die Werte für die Knoten der BST angegeben werden, dann ist nur eine Traversierung ausreichend, da der Rest der Daten durch die Werte der Knoten bereitgestellt wird.Aber wenn die Werte unbekannt sind, dann ist meines Erachtens das Konstruieren einer eindeutigen BST aus einer einzelnen Traversierung nicht möglich. Ich bin jedoch offen für Vorschläge.