Binärbaumformeln, die Sie verstehen müssen

1. Eigenschaften allgemeiner Binärbäume

Eigenschaften 1. Auf der i-Ebene eines nicht leeren Binärbaums gibt es höchstens 2^i Knoten .

Eigenschaft 2. In einem Binärbaum mit der Höhe K gibt es höchstens 2^(k+1)-1 Knoten.

Eigenschaft 3. Wenn für jeden nicht leeren Binärbaum die Anzahl der Blattknoten n0 und die Anzahl der Knoten mit Grad 2 n2 beträgt, dann ist n0 = n2 + 1.

2, Vollständiger Binärbaum

Definition: Wenn in einem Binärbaum nur die Grade der Knoten auf den unteren beiden Ebenen kleiner als 2 sind, sind die Grade von Wenn die Knoten auf allen anderen Ebenen gleich 2 sind und die Knoten der unteren Ebene an den Positionen ganz links in der Ebene konzentriert sind, wird dieser Binärbaum als vollständiger Binärbaum bezeichnet.

Eigenschaft 1. Die Höhe k eines vollständigen Binärbaums mit n Knoten beträgt [log^2n].

Eigenschaft 2. Wenn für einen vollständigen Binärbaum mit n Knoten alle Knoten im Binärbaum von oben (Wurzelknoten) nach unten (Blattknoten) und von links nach rechts geordnet sind, beginnt die Nummerierung von 0 bis n-1, dann gibt es für jeden Knoten, dessen Index i ist:

(1) Wenn i=0, dann ist es der Wurzelknoten und er hat keinen übergeordneten Knoten; wenn i>0, dann Der Index seines übergeordneten Knotens ist (i-1)/2.

(2) Wenn 2i+1<=n-1, dann ist der Index des linken untergeordneten Knotens des Knotens mit dem Index i 2i+1; andernfalls hat der Knoten mit dem Index i keinen linken untergeordneten Knoten Knoten.

(3) Wenn 2i+2<=n-1, dann ist der Index des rechten untergeordneten Knotens des Knotens mit dem Index i 2i+2; andernfalls hat der Knoten mit dem Index i kein rechtes Kind Knoten.

3. Vollständiger Binärbaum

Definition: Wenn ein Knoten eines Binärbaums entweder ein Blatt ist oder zwei nicht leere Teilbäume hat, dann ist es dieser Binärbaum namens Vollständiger Binärbaum.

Eigenschaft: In einem vollständigen Binärbaum ist die Anzahl der Blattknoten um 1 größer als die Anzahl der Verzweigungsknoten.

4. Erweiterter Binärbaum

Definition: Ein erweiterter Binärbaum ist eine Erweiterung eines vorhandenen Binärbaums. Nach der Erweiterung werden die Knoten des ursprünglichen Binärbaums zu Zweigen mit Grad 2. Knoten. Das heißt, wenn der Grad des ursprünglichen Knotens 2 ist, bleibt er unverändert; wenn der Grad 1 ist, wird ein Zweig hinzugefügt, wenn der Grad 0 ist, werden zwei Zweige hinzugefügt.

Eigenschaft 1. In einem erweiterten Binärbaum ist die Anzahl der externen Knoten um 1 größer als die Anzahl der internen Knoten.

Eigenschaft 2. Für jeden erweiterten Binärbaum ist die folgende Beziehung zwischen der externen Pfadlänge E und der internen Pfadlänge I erfüllt: E=I+2n, wobei n die Anzahl der internen Knoten ist.

Weitere technische Artikel zu häufig gestellten Fragen finden Sie in der Spalte FAQ mehr!

Das obige ist der detaillierte Inhalt vonBinärbaumformeln, die Sie verstehen müssen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!