Ich bin sehr verwirrt über eine Reihe von Artikeln an verschiedenen Standorten bezüglich der Konstruktion eines Binary Search Tree von einem beliebigen traversalen ( pre , post oder in-order ) oder einer Kombination von zweien davon. Auf der Seite dieser Seite wird beispielsweise angegeben, dass bei der Auftragsdurchführung pre , post oder level zusammen mit dem in-order traversal kann man BST konstruieren. Aber hier und dort , zeigen sie uns, ein BST von pre-order allein zu konstruieren. Auch hier hier zeigen sie uns, wie man die BST von gegebenen pre und post-order Traversalen erstellt. In einer anderen Site habe ich eine Lösung gefunden, um ein BST nur aus dem post-order Traversal zu konstruieren.
Jetzt weiß ich, dass es mit den inorder und pre-order Traversalen möglich ist, ein BST eindeutig zu bilden. Was den ersten Link anbelangt, obwohl ich sage, dass wir BST nicht aus pre-order und post-order konstruieren können, kann ich nicht einfach das Array post-order sortieren, um dessen inorder traversal und dann benutze das und das Array pre-order , um BST zu bilden? Wird das gleiche wie die Lösung in der vierten Verbindung oder anders sein? Und wenn ich nur pre-order angegeben habe, kann ich das sortieren, um in-order zu erhalten, dann benutze das und pre-order , um das BST zu erhalten. Wiederum, muss das anders sein als die Lösung in den Links 2 und 3?
Was reicht aus, um BST eindeutig zu generieren? Wenn keine Eindeutigkeit erforderlich ist, kann ich sie einfach sortieren, um den in-order traversal zu erhalten und einen der N möglichen BST s daraus rekursiv aufzubauen.
Um eine BST zu konstruieren, brauchen Sie nur eine Traversierung (nicht in der Reihenfolge).
Um einen Binärbaum zu erstellen, benötigen Sie im Allgemeinen zwei Durchläufe, zum Beispiel in Reihenfolge und Vorbestellung. Für den speziellen Fall von BST - das Intra-Order-Traversal ist immer das sortierte Array, das die Elemente enthält, so dass Sie es immer rekonstruieren und einen Algorithmus verwenden können, um einen generischen Baum aus Vororder- und In-Order-Traversalen zu rekonstruieren. p>
Also ist die Information, dass der Baum eine BST ist, zusammen mit den Elementen darin (sogar ungeordnet) ä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 distinct elements. Es gibt n! mögliche Listen für diese n Elemente, jedoch - die mögliche Anzahl von Bäumen ist viel größer (2 * n! Mögliche Bäume für die n Elemente sind alle verfallene Bäume, so dass node.right = null in jedem Knoten, also der Baum ist eigentlich eine Liste auf der rechten Seite.Es gibt n! solcher Bäume, und andere n! Bäume wo immer node.left = null ) Also, vom Taube-Loch-Prinzip gibt es mindestens eine Liste, die 2 Bäume generiert, also können wir nicht rekonstruiere den Baum aus einer einzigen Traversierung.
(QED)
Wenn die Werte für die Knoten der BST angegeben werden, 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.
Tags und Links algorithm binary-search-tree inorder postorder preorder