Kann ich einen binären Baum aus einem bestimmten dfs Traversal bilden? Ich meine, sagen, dass ich inorder, preorder, postorder, oder alle drei habe, kann ich einen einzigartigen binären Baum aus diesen Traverse whit keine Mehrdeutigkeit mit einem anderen Baum haben?Konvertieren von DFS in binären Baum
Sie könnten jeden Binärbaum wiederherstellen, wenn Sie alle Knoten, einschließlich der externen Knoten, vorbestellen. Um dies zu tun, müssen Sie die internen Knoten von den externen unterscheiden. Die externen Knoten sind die leeren Bäume, die in vielen Implementierungen NULL Zeigern entsprechen.
beispielsweise die folgenden Binärbaum
der interne Knoten mit a und dem externen mit b markiert ist.
So ist die Vorordnungsdurchquerung ist
aaaabbabbaabbbababb
Es dass die Sprache aller möglichen Preorder-Codes dargestellt werden könnte, ist injektiv, so können Sie die Preorder Reihenfolge umkehren könnte und die ursprüngliche Baum wiederherzustellen.
Einige wie (psudocode):
Node * preorder_to_tree(char *& ptr)
{
if (*ptr++ == ''b')
return nullptr;
Node * p = new Node;
LLINK(p) = preorder_to_tree(ptr);
RLINK(p) = preorder_to_tree(ptr);
return p;
}
Natürlich ist der Algorithmus eine gültige Preorder-Sequenz annimmt.
Wenn Sie Schlüssel in den internen Knoten speichern, dann könnten Sie einen speziellen Schlüssel für die Bezeichnung des leeren Baumes verwenden und der Algorithmus wäre derselbe.
Was wäre, wenn wir nicht wüssten, wie viele Knoten jeder Knoten hat? Ich meine, Vororder-Traversierung von (a, b, c, d, e) kann geschrieben werden (b, a, d, c, e), (c, b, a, d, e), usw. in der Invers-Traversierung. Wie können wir wissen, welcher der gewünschte Baum ist? Ich glaube nicht, dass Vorbestellung allein ausreicht, um den Baum zu erstellen:/ –
Ich gehe davon aus, wie Sie angegeben haben. dass es sich um binäre Bäume handelt. Jeder interne Knoten hat also immer zwei Teilbäume mit drei möglichen Kombinationen: voller Knoten mit beiden Teilbäumen, die sich von einem leeren Baum unterscheiden, ein unvollständiger Knoten mit einem leeren Teilbaum und ein Blattknoten mit beiden leeren Teilbäumen. Wenn Sie nun mit einem M-Baum arbeiten, können Sie schließlich einen äquivalenten Binärbaum erhalten, dessen Preorder-Traversal dem Preorder-Traversal auf dem M-Tree entspricht. Ich schlage vor, Knuth TAOCP V I zu überprüfen, um ein besseres Verständnis für diese Äquivalenz zu bekommen – lrleon
Ich glaube nicht. Binärbaum kann leer sein (?). Übrigens, was bedeutet es vollständiger Knoten und unvollständiger Knoten? –