Vollständiger Binärbaum vs. Vollständiger Binärbaum
Binärer Baum ist ein Baum, in dem jeder Knoten ein oder zwei Kinder hat. In einem Binärbaum kann ein Knoten nicht mehr als zwei Kinder haben. In einem binären Baum werden Kinder als "linke" und "rechte" Kinder bezeichnet. Die untergeordneten Knoten enth alten einen Verweis auf ihre übergeordneten Knoten. Ein vollständiger Binärbaum ist ein Binärbaum, bei dem jede Ebene des Binärbaums mit Ausnahme der letzten Ebene vollständig gefüllt ist. In der ungefüllten Ebene werden die Knoten beginnend von der Position ganz links angefügt. Ein vollständiger binärer Baum ist ein Baum, in dem jeder Knoten im Baum zwei Kinder 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 Kinder 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 stehen die Anzahl der Knoten (n), die Anzahl der Laves (l) und die Anzahl der internen Knoten (i) in einer besonderen Beziehung, sodass Sie, wenn Sie einen von ihnen kennen, die anderen beiden bestimmen können Werte wie folgt:
1. Wenn ein vollständiger Binärbaum i interne Knoten hat:
– Blattzahl l=i+1
– Gesamtzahl der Knoten n=2i+1
2. Wenn ein vollständiger Binärbaum n Knoten hat:
– Anzahl der internen Knoten i=(n-1)/2
– Blattzahl l=(n+1)/2
3. Wenn ein vollständiger Binärbaum l Blätter hat:
– Gesamtzahl der Knoten n=2l-1
– Anzahl der inneren 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 beginnend von der Position ganz links angefügt werden. Ein vollständiger Binärbaum der Höhe h erfüllt die folgenden Bedingungen:
– Vom Wurzelknoten aus repräsentiert die Ebene über der letzten Ebene einen vollständigen binären Baum der Höhe h-1
– Ein oder mehrere Knoten in der letzten Ebene können 0 oder 1 Kind haben
– Wenn a, b zwei Knoten in der Ebene über der letzten Ebene sind, dann hat a genau dann mehr Kinder als b, wenn a links von b liegt
Was ist der Unterschied zwischen Complete Binary Tree und Full Binary Tree?
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 Kinder 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. Aber ein vollständiger Binärbaum hat keine besondere Eigenschaft in Bezug auf diese drei Attribute.
