Kann man einen binären Baum zeichnen, wenn man seine binäre Sequenz/Reihenfolge vorbestellt?

Question

Binärbäume (und damit geordnete Gesamtstrukturen) können als Binärzeichenfolgen dargestellt werden. Die binäre Zeichenfolge wird erhalten, indem ein binärer Baum in der Vorreihenfolge durchlaufen wird, wobei für jeden Knoten eine 1 und für jeden leeren Unterbaum eine 0 aufgezeichnet wird (Nullverknüpfung).

Das bedeutet, wenn ich einen binären Baum bekomme, kann ich eine Preorder-Traversierung durchführen und eine binäre Sequenzrepräsentation erzeugen.

Ist das Gegenteil auch möglich? Wenn ich diese binäre Sequenz 11011000101101010001 bekomme, kann ich den Binärbaum zeichnen?

Answer 1

Ja, Sie können.

Beschriften Sie die internen Knoten als a und die externen als b; natürlich kann man a als 0 und b als 1 annehmen (und umgekehrt). Aber ich denke, es ist einfacher, Buchstaben als Zahlen zu unterscheiden (obwohl dies eine Frage des "Geschmacks" ist).

Wenn Sie nicht wissen, was die "externen Knoten" sind, dann können Sie davon ausgehen, dass sie die NULL Zeiger sind.

Jetzt bildet die Preorder-Traversierung irgendeines Baumes, der wie ich gesagt habe, ein Wort, das zur Lukasiewicz-Sprache gehört. Es konnte gezeigt werden, dass dieses Wort einzigartig ist. Das heißt, für jedes Paar von Bäumen t1 und t2, code(t1) != code(t2); immer! Zusätzlich (und das sollte der Grund sein, warum Sie sich für die Huffman-Kodierung interessieren), ist die Lukasiewicz-Sprache ein Präfix.

Zum Beispiel für den Baum

Seine Vorordnungsdurchquerung ist aaaabbabbaabbbababb oder 000011011001110111

ich Ihnen überlassen, den Code einen Code zu erzeugen; es ist eine Preorder-Traversierung. Wenn Sie es in Umkehrung interessiert sind, das heißt, da der Baum, den Code zu bekommen, dann diesem Pseudo-Code, der Ihre Frage zu beantworten versucht, es tun würde:

Node * code_to_tree(char *& code) 
{ 
    if (*code++ == 'b') 
    return nullptr; 

    Node * p = new Node; 
    LLINK(p) = code_to_tree(code); 
    RLINK(p) = code_to_tree(code); 

    return p; 
} 

In einer realen Implementierung, würden Sie Bits lesen.

Die obige Routine geht davon aus, dass der Code richtig ist; das heißt, es wurde von einem Binärbaum erzeugt. Beachten Sie, dass nicht alle Wörter, die von a 's und b zusammengesetzt sind, zur Sprache von Lukasiewicz gehören. Aber es könnten einige vorstellbare Regeln auf sie angewendet werden.

Erstens muss die Anzahl der b genau die Anzahl der a plus eins sein. Zweitens, wenn jeder a einen (1) gewichtet und jeder b Gewichte minus eins (-1), dann, bei der Ausnahme letzten b, kann die Addition durch alle Wörter für jeden Buchstaben nie kleiner als Null sein. Nur am Ende des Wortes wird der Zusatz -1 sein. Wenn das Wort diese Bedingung nicht erfüllt, können Sie davon ausgehen, dass es ungültig ist.

Answer 2

Sicher!

Erstellen eines binären Baum, eine Nummer, die jedem Element zuordnen

 0 
    1----|-----2 
3-|-4  5--|--6 
7|8 9|10 11|12 13|14 
... 

Dies sind Ihre Indizes.

eine Größe für Ihre Knotendaten definieren und Sie können die Informationen für einen Knoten im Baum bei data_size * index

Dies ist häufig zu bekommen, wie Haufen dargestellt werden.

Es gibt viele Möglichkeiten, einen Binärbaum als String darzustellen. Da es jedoch so viele Möglichkeiten gibt, müssen Sie sich auf eine bestimmte Darstellung einigen, bevor Sie fortfahren können. Was ich oben erwähnt habe, ist nur eine Möglichkeit, einen Binärbaum darzustellen, und es ist möglicherweise nicht der Standard, den Sie alle verwenden.