Betrachten Sie das folgende Array, das angeblich einen binären Baum darstellt:
[1, 2, 5, 6, -1, 8, 11]
Da der Index mit dem Wert -1 das Wurzelelement angibt, habe ich folgende Fragen:
a) Wie ist das eigentlich dargestellt?
Sollen wir den folgenden Formeln folgen ( Quelle von diesem Link ) um den Baum herauszufinden? Drei einfache Formeln ermöglichen Ihnen, vom Index des Elternteils zum Index seiner Kinder und umgekehrt zu wechseln:
%Vor%Wenn wir obige Formeln verwenden, dann index (root) = 3, index (linkes Kind) = 7, was nicht existiert.
b) Ist es wichtig zu wissen, ob es sich um einen vollständigen Binärbaum handelt oder nicht?
Bei einem gegebenen Array könnten Sie sich viele Möglichkeiten vorstellen, wie dieses Array einen binären Baum darstellen könnte. Also gibt es keine Möglichkeit zu wissen, du musst zur Quelle dieses Arrays gehen (was auch immer das ist).
Eine dieser Möglichkeiten ist die Art und Weise, wie binäre Heaps normalerweise dargestellt werden, wie in Ihrem Link angegeben. Wenn dies die verwendete Repräsentation wäre, wäre -1 nicht das Wurzelelement. Und der Knoten an Position 3 hätte keine Kinder, d. H. Es wäre ein Blatt.
Und, ja, es ist wahrscheinlich wichtig zu wissen, ob es sich um einen vollständigen Baum handelt oder nicht.
Im Allgemeinen sollten Sie nicht versuchen herauszufinden, was einige Daten so bedeuten. Sie sollten eine Dokumentation oder den Quellcode erhalten, der die Daten verwendet. Wenn Sie das nicht haben und Sie es wirklich zurückentwickeln müssen, müssen Sie wahrscheinlich mehr über die Daten wissen. Das Verhalten des Codes, der es verwendet, sollte Ihnen helfen. Oder den Code dekompilieren.
N = 0 muss der Stammknoten sein, da er nach den aufgelisteten Regeln kein Elternteil hat. 0 kann nicht aus einem der Ausdrücke (2 * N + 1) oder (2 * N + 2) erzeugt werden, wenn kein negatives N angenommen wird.
Beachten Sie, dass der Index nicht der im Array gespeicherte Wert ist, sondern der Platz im Array. Für [1, 2, 5, 6, -1, 8, 11] Index 0 = 1 Index 1 = 2 Index 2 = 5, usw.
Wenn es sich um einen vollständigen Baum handelt, ist -1 ein gültiger Wert und Baum ist
%Vor%-1 könnte auch ein "NULL" -Zeiger sein, der anzeigt, dass an diesem Knoten kein Wert existiert.
So würde der Baum wie
aussehen %Vor%Es ist vielleicht kein vollständiger Binärbaum, aber auch kein beliebiger Binärbaum. Sie können einen Baum darstellen, in dem höchstens ein paar der ganz wenigen Blätter fehlen (oder, wenn Sie die Konvention für linke und rechte Kinder austauschen, höchstens ein paar Blätter ganz links fehlen).
Sie können dies nicht in Ihrem Array darstellen:
%Vor%Aber du kannst das darstellen
%Vor%oder das:
%Vor%(für die letzte, haben 2k + 1 die rechts Kind und 2k + 2 die links Kind)
Sie müssen nur die Anzahl der Knoten in den dreien kennen.
Tags und Links data-structures binary-tree