Was ist ein vollständiger Binärbaum?
Ein vollständiger Binärbaum kann als definiert werden Binärbaum in dem alle Knoten 0 oder zwei Kinder haben. Mit anderen Worten: Der vollständige Binärbaum kann als Binärbaum definiert werden, in dem alle Knoten außer den Blattknoten zwei untergeordnete Knoten haben.
Der folgende Baum ist ein vollständiger Binärbaum:
Der obige Baum ist ein vollständiger Binärbaum, da alle Knoten außer den Blattknoten zwei untergeordnete Knoten haben.
Vollständiger Satz des Binärbaums:
Betrachten Sie dann einen Binärbaum T als einen nichtleeren Baum:
- Angenommen, I sei ein interner Knoten in einem Baum und L ein Blattknoten in einem Baum, dann wäre die Anzahl der Blattknoten gleich:
L = I + 1 - Wenn T die Anzahl der internen Knoten I hat und N die Gesamtzahl der Knoten ist, dann wäre die Gesamtzahl der Knoten gleich:
N = 2I + 1 - Wenn T die Gesamtzahl der Knoten „N“ enthält und „I“ die Anzahl der internen Knoten ist, dann wäre die Anzahl der internen Knoten gleich:
I = (N-1)/2 - Wenn „T“ eine Gesamtzahl von „N“ Knoten hat und „L“ eine Anzahl von Blattknoten ist, dann wäre die Anzahl der Blattknoten gleich:
L = (N+1)/2 - Wenn „T“ die Anzahl „L“ an Blattknoten enthält, wäre die Gesamtzahl der Knoten gleich:
N = 2L - 1 - Wenn „T“ die Anzahl „L“ an Blattknoten hat und „I“ eine Anzahl interner Knoten sein soll, dann wäre die Anzahl interner Knoten gleich:
I = L - 1
Was ist ein vollständiger Binärbaum?
Ein Binärbaum wird als vollständiger Binärbaum bezeichnet, wenn alle Ebenen vollständig gefüllt sind, mit Ausnahme der letzten Ebene, die von links aus gefüllt wird.
Der folgende Baum ist ein vollständiger Binärbaum:
Der vollständige Binärbaum ähnelt dem vollständigen Binärbaum mit Ausnahme der beiden unten aufgeführten Unterschiede:
- Das Füllen des Blattknotens muss ganz links beginnen.
- Es ist nicht zwingend erforderlich, dass der letzte Blattknoten den richtigen Geschwisterknoten haben muss.
Lassen Sie uns die oben genannten Punkte anhand eines Beispiels verstehen:
Betrachten Sie den folgenden Baum:
Der obige Baum ist ein vollständiger Binärbaum, aber kein vollständiger Binärbaum, da Knoten 6 nicht über seinen rechten Geschwisterknoten verfügt.
Erstellung eines vollständigen Binärbaums
Angenommen, wir haben ein Array mit 6 Elementen, wie unten dargestellt:
Das obige Array enthält 6 Elemente, d. h. 1, 2, 3, 4, 5, 6. Die folgenden Schritte sind zum Erstellen eines vollständigen Binärbaums erforderlich:
Schritt 1: Zuerst wählen wir das erste Element des Arrays, also 1, aus und erstellen einen Wurzelknoten des Baums. Die Anzahl der in der ersten Ebene verfügbaren Elemente beträgt 1.
Schritt 2: Jetzt wählen wir das zweite und dritte Element des Arrays aus. Behalten Sie das zweite und dritte Element des Arrays als linkes und rechtes untergeordnetes Element des Wurzelknotens bei, wie unten gezeigt:
Wie wir oben beobachten können, beträgt die Anzahl der in der zweiten Ebene verfügbaren Elemente 2.
Schritt 3: Jetzt wählen wir die nächsten beiden Elemente aus dem Array aus, d. h. 4 und 5. Behalten Sie diese beiden Elemente links und rechts von Knoten 2 bei, wie unten gezeigt:
Wie wir oben beobachten können, sind die Knoten 4 und 5 das linke bzw. rechte Kind von Knoten 2.
Schritt 4: Jetzt wählen wir das letzte Element des Arrays aus, d. h. 6, und behalten es als linkes untergeordnetes Element des Knotens 3 bei, da wir wissen, dass in einem vollständigen Binärbaum die Knoten von der linken Seite aus gefüllt werden, wie unten gezeigt:
Wie wir beobachten können, enthält die zweite Ebene 3 Elemente.
Lassen Sie uns anhand der Bilder die Unterschiede zwischen vollständigem und vollständigem Binärbaum verstehen.
- Der unten gezeigte Binärbaum ist weder ein vollständiger noch ein vollständiger Binärbaum. Es handelt sich nicht um einen vollständigen Binärbaum, da Knoten 3 nur ein Kind hat. Es handelt sich auch nicht um einen vollständigen Binärbaum, da die Knoten von der linken Seite aus gefüllt werden sollten, Knoten 3 jedoch ein rechtes Kind und kein linkes Kind hat.
- Der unten gezeigte Binärbaum ist ein vollständiger Binärbaum, aber kein vollständiger Binärbaum. Es handelt sich um einen vollständigen Binärbaum, da alle Knoten entweder 0 oder 2 untergeordnete Knoten haben. Es handelt sich nicht um einen vollständigen Binärbaum, da Knoten 3 keine Kinder hat, während Knoten 2 seine Kinder hat und wir wissen, dass die Knoten in einem vollständigen Binärbaum von der linken Seite aus gefüllt werden sollten.
- Der unten gezeigte Binärbaum ist ein vollständiger Binärbaum, aber kein vollständiger Binärbaum. Es handelt sich um einen vollständigen Binärbaum, da alle Knoten gefüllt bleiben. Es handelt sich nicht um einen vollständigen Binärbaum, da Knoten 2 nur ein Kind hat.
- Der unten gezeigte Binärbaum ist sowohl ein vollständiger als auch ein vollständiger Binärbaum. Es handelt sich um einen vollständigen Binärbaum, da alle Knoten gefüllt bleiben. Es handelt sich um einen vollständigen Binärbaum, da alle Knoten entweder 0 oder 2 untergeordnete Knoten haben.
