A
Ein Binärbaum
Es gibt verschiedene Arten von Binärbäumen aber hier werden wir über den Unterschied diskutieren Vollständiger Binärbaum Und Vollständiger Binärbaum .
Vollständiger Binärbaum:
Ein vollständiger Binärbaum ist ein Binärbaum, in dem Alle Knoten haben entweder 0 oder 2 Nachkommen . Mit anderen Worten ist ein vollständiger Binärbaum ein Binärbaum, in dem alle Knoten außer den Blattknoten zwei Nachkommen haben.
Ein vollständiger Binärbaum
Hashtabelle JavaLassen, ich sei die Anzahl der internen Knoten
N sei die Gesamtzahl der Knoten
l sei die Anzahl der Blätter
l Anzahl der Ebenen seinDann,
Die Anzahl der Blätter beträgt (ich + 1) .
Die Gesamtzahl der Knoten beträgt (2i + 1) .
Die Anzahl der internen Knoten beträgt (n – 1) / 2 .
Die Anzahl der Blätter beträgt (n + 1) / 2 .
Die Gesamtzahl der Knoten beträgt (2l – 1) .
Die Anzahl der internen Knoten beträgt (l – 1) .
Die Anzahl der Blätter beträgt höchstens (2l- 1) .
Vollständiger Binärbaum:
Ein Binärbaum heißt a vollständiger Binärbaum wenn alle seine Ebenen, außer möglicherweise der letzten Ebene, die maximale Anzahl möglicher Knoten haben und alle Knoten in der Die letzte Ebene erscheint so weit links wie möglich .
Ein vollständiger Binärbaum
123FilmEs gibt 2 Punkte, die Sie hier erkennen können:
- Die äußerste linke Seite des Blattknotens muss immer zuerst gefüllt werden.
- Es ist nicht notwendig, dass der letzte Blattknoten einen rechten Geschwisterknoten hat.
Sehen Sie sich die folgenden Beispiele an, um den vollständigen Binärbaum besser zu verstehen.
Beispiel 1:
Weder vollständig noch vollständig
- Knoten C hat also nur ein Kind, Es handelt sich nicht um einen vollständigen Binärbaum.
- Knoten C hat also auch ein rechtes Kind, aber kein linkes Kind Es handelt sich auch nicht um einen vollständigen Binärbaum.
Daher ist der oben gezeigte Binärbaum weder vollständiger noch vollständiger Binärbaum.
Beispiel 2:
jdbc jdbcVollständig, aber nicht vollständig
- Alle Knoten haben beides 0 oder 2 Nachkommen also, Es handelt sich um einen vollständigen Binärbaum .
Es handelt sich nicht um einen vollständigen Binärbaum, da der Knoten B hat keine Kinder, während node C hat Kinder, und gemäß einem vollständigen Binärbaum sollten Knoten aus dem gefüllt werden linke Seite .Daher ist der oben gezeigte Binärbaum a Vollständiger Binärbaum und es ist kein vollständiger Binärbaum.
String-Array in C-Sprache
Beispiel 3:
Vollständig, aber nicht vollständig
Es handelt sich um einen vollständigen Binärbaum, da alle Knoten gefüllt bleiben.
- Knoten B hat nur ein Kind, daher Es handelt sich nicht um einen vollständigen Binärbaum.
Daher ist der oben gezeigte Binärbaum a Vollständiger Binärbaum und es ist kein vollständiger Binärbaum.
Beispiel 4:
Vollständig und vollständig
- es ist ein Vollständige Binärdatei Baum, weil alle Knoten vorhanden sind links gefüllt .
- Alle Knoten haben beides 0 oder 2 Nachwuchs, daher ist es ein vollständiger Binärbaum .
Daher ist der oben gezeigte Binärbaum sowohl ein vollständiger als auch ein vollständiger Binärbaum.
| Ja Nein. | Kompletter Binärbaum | Vollständiger Binärbaum |
| 1. | In einem vollständigen Binärbaum kann ein Knoten auf der letzten Ebene nur ein untergeordnetes Element haben. | In einem vollständigen Binärbaum kann ein Knoten nicht nur ein untergeordnetes Element haben. |
| 2. | In einem vollständigen Binärbaum sollte der Knoten von links nach rechts gefüllt werden. | In einem vollständigen Binärbaum gibt es keine Reihenfolge zum Füllen von Knoten. |
| 3. | Vollständige Binärbäume werden hauptsächlich in Heap-basierten Datenstrukturen verwendet. | Ein vollständiger Binärbaum hat als solcher keine Anwendung, wird aber auch als echter Binärbaum bezeichnet. |
| 4. | Ein vollständiger Binärbaum wird auch als fast vollständiger Binärbaum bezeichnet. | Ein vollständiger Binärbaum, auch richtiger Binärbaum oder 2-Baum genannt. |
| 5 | Bei einem vollständigen Binärbaum muss der gesamte Blattknoten genau die gleiche Tiefe haben. | Bei einem vollständigen Binärbaum muss die Blattebene nicht unbedingt dieselbe Tiefe haben. |