5 Eigenschaften von Binärbäumen

Binärbaum hat die folgenden fünf Eigenschaften:

1 Die Binärbaum-A-Schicht hat höchstens 2＾(i - 1) Knoten.

2. Ein Binärbaum mit Tiefe k (k>=0) hat mindestens k Knoten und höchstens 2＾k-1 Knoten.

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

4. Die Tiefe eines vollständigen Binärbaums mit n Knoten ist int_UP (log(2,ｎ+1)).

5. Wenn ein vollständiger Binärbaum mit n Knoten von oben nach unten erstellt wird, werden die Knoten in derselben Ebene von links nach rechts fortlaufend mit 1, 2, 3 nummeriert. ． ． ． ． ． , n, und speichern Sie dann jeden Knoten im Baum nacheinander in einem eindimensionalen Array entsprechend dieser Knotennummer und nennen Sie den Knoten mit der Nummer i als Knoten i (i>=1 && i<=n), dann gibt es Folgendes Beziehung:

(1) Wenn i = 1, dann ist Knoten i die Wurzel und hat keinen übergeordneten Knoten, wenn i> 🎜>

(2) Wenn 2*i <= n, dann ist das linke Kind von Knoten i Knoten 2*i

(3) Wenn 2*i (4) Wenn die Knotennummer i eine ungerade Zahl ist und i! =1, er befindet sich an der rechten Geschwisterposition, dann ist sein linker Geschwisterknoten i-1; (5) Wenn die Knotennummer i eine gerade Zahl ist und i! =n, er befindet sich in der linken Geschwisterposition, dann ist sein rechter Geschwisterknoten i+1; (6) Die Ebene des Knotens i ist int_DOWN (log (2, i)) + 1.

Beweis einiger Eigenschaften

Eigenschaft 1 kann durch mathematische Induktion nachgewiesen werden

Beweis von Eigenschaft 2:

Beweis aus Eigenschaft 1 Es ist ersichtlich, dass die maximale Gesamtzahl der Knoten in Schicht k ausgedrückt werden kann als 2＾0＋2＾ 1＋...＋2^ (ｋ-1) = 2^k- 1; 3:

Zuerst sei aus der Perspektive der Knoten n1 + n2 + n0 = n, sei dies Gleichung (1);

Aus der Perspektive der Kanten ist n2 verbunden mit zwei Kanten, n1 ist mit einer Kante verbunden und n Knoten sind paarweise verbunden. Wir benötigen ｎ-1 Seiten und können 2＊ｎ2＋ｎ1=ｎ-1 erhalten, was Formel (2) ist Aus Formel (1)-(2) können wir -n2=1 erhalten.

Das obige ist der detaillierte Inhalt von5 Eigenschaften von Binärbäumen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!