Unterschied zwischen vollständiger binärer und vollständiger binärer Baum

Vollständiger binärer Baum vs vollständiger binärer Baum

sein. 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ärbaum werden Kinder als "linke" und "richtige" Kinder benannt. Die untergeordneten Knoten enthalten eine Referenz auf ihr übergeordnetes Element. Ein vollständiger binärer Baum ist ein binärer Baum, in dem jede Ebene des binären Baums bis auf die letzte Ebene vollständig gefüllt ist. In der ungefüllten Ebene werden die Knoten beginnend von der Position ganz links angehängt. Ein vollständiger binärer Baum ist ein Baum, in dem jeder Knoten im Baum außer den Blättern des Baumes zwei Kinder hat.

Was ist Full Binary Tree?

Voller 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 mit Ausnahme der Blätter hat genau zwei Kinder. Abbildung 1 zeigt einen vollständigen Binärbaum. In einem vollständigen binären Baum wird die Anzahl der Knoten (n), die Anzahl der Laves (l) und die Anzahl der internen Knoten (i) in einer speziellen Weise miteinander in Beziehung gesetzt, so dass, wenn Sie eine von ihnen kennen, Sie die anderen zwei Werte wie folgt:

1. Wenn ein vollständiger Binärbaum i interne Knoten hat:

- Anzahl der Blätter l = i + 1

- Gesamtanzahl 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 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ärbaum ein Binärbaum, in dem jede Ebene des Baums bis auf die letzte Ebene vollständig gefüllt ist. In der letzten Ebene sollten Knoten von der am weitesten links gelegenen Position angehängt werden. Ein vollständiger binärer Baum der Höhe h erfüllt die folgenden Bedingungen:

- Vom Knoten aus stellt der Level über dem letzten Level einen vollständigen Binärbaum der Höhe h-1

dar. - Ein oder mehrere Knoten in der letzten Ebene können 0 oder 1 Kinder

- Wenn a, b zwei Knoten in der Ebene oberhalb der letzten Ebene sind, hat a mehr Kinder als b, wenn und nur wenn a links von b liegt

Was ist der Unterschied zwischen Complete Binary Tree und voller binärer Baum?

Vollständige Binärbäume und vollständige Binärbäume haben einen deutlichen Unterschied. Während ein vollständiger binärer Baum ein binärer Baum ist, in dem jeder Knoten null oder zwei Kinder hat, ist ein vollständiger binärer Baum ein binärer Baum, in dem jede Ebene des binären Baums bis auf die letzte 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 anderen beiden sehr leicht finden.Ein vollständiger Binärbaum hat jedoch keine spezielle Eigenschaft, die diese drei Attribute betrifft.