Unterschied zwischen vollständigem binärem Baum und vollständigem binärem Baum

Kompletter binärer Baum vs. vollständiger binärer Baum

Binärer Baum ist ein Baum, bei 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 Verweis auf ihr übergeordnetes Element. Ein vollständiger Binärbaum ist ein Binärbaum, in dem alle Ebenen des Binärbaums bis auf die letzte Ebene vollständig gefüllt sind. In der ungefüllten Ebene werden die Knoten ausgehend von der linken Position angefügt. Ein vollständiger binärer Baum ist ein Baum, in dem jeder Knoten im Baum zwei Kinder mit Ausnahme der Blätter des Baums hat.

Was ist voller binärer Baum??

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 zeigt einen vollständigen binären Baum. In einem vollständigen binären Baum hängen die Anzahl der Knoten (n), die Anzahl der Laves (l) und die Anzahl der internen Knoten (i) in besonderer Weise zusammen, sodass Sie die beiden anderen Knoten 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 voller binärer Baum l Blätter hat:

- Gesamtzahl der Knoten n = 2 * l-1

- Anzahl der internen Knoten i = l-1

Was ist ein kompletter binärer Baum??

Wie in Abbildung 2 dargestellt, ist ein vollständiger binärer Baum ein binärer Baum, in dem alle Ebenen des Baums bis auf die letzte Ebene vollständig gefüllt sind. In der letzten Ebene sollten Knoten ausgehend von der linken Position angefügt werden. Ein vollständiger binärer Baum der Höhe h erfüllt die folgenden Bedingungen:

- Vom Stammknoten 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, dann hat a mehr und weniger als b, wenn a links von b liegt

Was ist der Unterschied zwischen Complete Binary Tree und Full Binary Tree??

Vollständige binäre Bäume und vollständige binäre Bäume haben einen klaren 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 alle Ebenen des Binärbaums mit Ausnahme der letzten Ebene vollständig gefüllt sind. Einige spezielle Datenstrukturen wie Heaps müssen vollständige binäre Bäume sein, während sie nicht vollständige binäre Bäume sein müssen. Wenn Sie in einem vollständigen Binärbaum die Anzahl der Gesamtknoten, die Anzahl der Laves oder die Anzahl der internen Knoten kennen, können Sie die anderen beiden sehr leicht finden. Ein vollständiger binärer Baum hat jedoch keine besondere Eigenschaft in Bezug auf diese drei Attribute.