Kompletter Binärbaum gegen Vollständiger Binärbaum
Binärbaum ist ein Baum, in dem jeder Knoten ein oder zwei untergeordnete Elemente hat. In einem Binärbaum kann ein Knoten nicht mehr als zwei untergeordnete Elemente haben. In einem Binärbaum werden Kinder als "linke" und "rechte" Kinder bezeichnet. Die untergeordneten Knoten enthalten einen Verweis auf ihren übergeordneten Knoten. Ein vollständiger Binärbaum ist ein Binärbaum, in dem jede Ebene des Binärbaums mit Ausnahme der letzten Ebene vollständig gefüllt ist. In der ungefüllten Ebene werden die Knoten ausgehend von der Position ganz links angebracht. Ein vollständiger Binärbaum ist ein Baum, in dem jeder Knoten im Baum zwei untergeordnete Elemente außer den Blättern des Baums hat.
Was ist ein vollständiger Binärbaum?
Vollständiger Binärbaum ist ein Binärbaum, in dem jeder Knoten im Baum genau null oder zwei untergeordnete Elemente hat. Mit anderen Worten, jeder Knoten im Baum außer den Blättern hat genau zwei Kinder. Abbildung 1 unten zeigt einen vollständigen Binärbaum. In einem vollständigen Binärbaum hängen die Anzahl der Knoten (n), die Anzahl der Laves (l) und die Anzahl der internen Knoten (i) auf besondere Weise zusammen, sodass Sie die beiden anderen bestimmen können, wenn Sie einen von ihnen kennen Werte wie folgt:
1. Wenn ein vollständiger Binärbaum i interne Knoten hat:
- Anzahl der Blätter l = i + 1
- Gesamtzahl der Knoten n = 2 * i + 1
2. Wenn ein vollständiger Binärbaum n Knoten hat:
- Anzahl der internen Knoten i = (n-1) / 2
- Anzahl der Blätter l = (n + 1) / 2
3. Wenn ein vollständiger Binärbaum l Blätter hat:
- Gesamtzahl der Knoten n = 2 * l-1
- Anzahl der internen Knoten i = l-1
Was ist ein vollständiger Binärbaum?
Wie in Abbildung 2 gezeigt, ist ein vollständiger Binärbaum ein Binärbaum, in dem jede Ebene des Baums mit Ausnahme der letzten Ebene vollständig gefüllt ist. Außerdem sollten in der letzten Ebene Knoten ausgehend von der Position ganz links angebracht werden. Ein vollständiger binärer Baum der Höhe h erfüllt die folgenden Bedingungen:
- Vom Wurzelknoten aus repräsentiert die Ebene über der letzten Ebene einen vollständigen Binärbaum der Höhe h-1
- Ein oder mehrere Knoten in der letzten Ebene können 0 oder 1 Kinder haben
- Wenn a, b zwei Knoten in der Ebene über der letzten Ebene sind, hat a genau dann mehr Kinder als b, wenn a links von b liegt
Was ist der Unterschied zwischen dem vollständigen Binärbaum und dem vollständigen Binärbaum?
Vollständige Binärbäume und vollständige Binärbäume haben einen deutlichen Unterschied. Während ein vollständiger Binärbaum ein Binärbaum ist, in dem jeder Knoten null oder zwei untergeordnete Elemente hat, ist ein vollständiger Binärbaum ein Binärbaum, in dem jede Ebene des Binärbaums mit Ausnahme der letzten Ebene vollständig gefüllt ist. Einige spezielle Datenstrukturen wie Heaps müssen vollständige Binärbäume sein, während sie keine vollständigen Binärbäume sein müssen. Wenn Sie in einem vollständigen Binärbaum die Anzahl der Gesamtknoten oder die Anzahl der Laves oder die Anzahl der internen Knoten kennen, können Sie die beiden anderen sehr leicht finden. Ein vollständiger Binärbaum hat jedoch keine spezielle Eigenschaft, die diese drei Attribute in Beziehung setzt.
