Unterschied zwischen vollständigem Binärbaum und vollem Binärbaum

Kompletter binärer Baum gegen volle binäre Baum

Binärbaum ist ein Baum, an dem jeder Knoten ein oder zwei Kinder hat. In einem binären Baum 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 enthalten einen Hinweis auf ihren Elternteil. Ein vollständiger binärer Baum ist ein binärer Baum, bei dem jede Ebene des binären Baums mit Ausnahme der letzten Ebene vollständig gefüllt ist. In der unbesetzten Ebene werden die Knoten ab der links am meisten angehängt. Ein voller Binärbaum ist ein Baum, bei dem jeder Knoten im Baum zwei Kinder außer den Blättern des Baumes hat.

Was ist voller binärer Baum?

Voller binärer Baum ist ein binärer Baum, bei dem jeder Knoten im Baum genau 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 vollen binären Baum. In einem vollen binären Baum hängt die Anzahl der Knoten (n), die Anzahl der Laves (L) und die Anzahl der internen Knoten (i) auf besondere Weise zusammen, wenn Sie einen von ihnen kennen, können Sie die anderen beiden bestimmen Werte wie folgt:

1. Wenn ein vollständiger binärer Baum ich interne Knoten hat:

- Anzahl der Blätter l = i+1

- Gesamtzahl der Knoten n = 2*i+1

2. Wenn ein vollständiger binärer Baum n Knoten hat:

- Anzahl der internen Knoten I = (n-1)/2

- Anzahl der Blätter l = (n+1)/2

3. Wenn ein voller Binärbaum l Blätter hat:

- Gesamtzahl der Knoten n = 2*l-1

- Anzahl der internen Knoten i = l-1

Was ist vollständiger binärer Baum?

Wie in Abbildung 2 gezeigt, ist ein vollständiger binärer Baum ein binärer Baum, bei dem jede Ebene des Baumes vollständig gefüllt ist, mit Ausnahme der letzten Ebene. Auch in der letzten Ebene sollten Knoten ab der links am meisten angehängt werden. Ein vollständiger binärer Höhe der Höhe H erfüllt die folgenden Bedingungen:

- Aus dem Wurzelknoten repräsentiert die Ebene über der letzten Ebene einen vollständigen binären Baumhochbaum 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 mehr Kinder als B, wenn a links von B liegt

Was ist der Unterschied zwischen vollständigem Binärbaum und vollem Binärbaum?

Komplette binäre Bäume und volle binäre Bäume haben einen klaren Unterschied. Während ein vollständiger binärer Baum ein binärer Baum ist, bei dem jeder Knoten null oder zwei Kinder hat, ist ein vollständiger binärer Baum ein binärer Baum, bei dem jede Ebene des binären Baums mit Ausnahme der letzten Ebene vollständig gefüllt ist. Einige spezielle Datenstrukturen wie Haufen müssen vollständige binäre Bäume sein, während sie keine vollen binären Bäume sein müssen. Wenn Sie in einem vollen binären Baum die Anzahl der Gesamtknoten oder die Anzahl der Laves oder die Anzahl der internen Knoten kennen, finden Sie die beiden anderen sehr leicht. Ein vollständiger binärer Baum hat jedoch keine spezielle Eigenschaft, die diese drei Attribute bezieht.