Die Anzahl der Blattknoten eines vollständigen Binärbaums

Ein vollständiger Binärbaum mit n Knoten, die Anzahl der Blattknoten n0 beträgt: n/2 aufgerundet oder (n+1)/2 Abrundung

Erweiterte Informationen:

Vollständiger Binärbaum

Der vollständige Binärbaum ist eine sehr effiziente Datenstruktur. Ein vollständiger Binärbaum besteht aus einer vollständigen Binärdatei Baum und herausgebracht. Ein Binärbaum mit n Knoten der Tiefe K wird genau dann als vollständiger Binärbaum bezeichnet, wenn jeder Knoten eins zu eins mit den von 1 bis n nummerierten Knoten im vollständigen Binärbaum der Tiefe K übereinstimmt.

Definition

Wenn die Tiefe des Binärbaums h ist, mit Ausnahme der h-ten Ebene, alle andere Ebenen (1 ~ h-1) Die Anzahl der Knoten hat die maximale Anzahl erreicht und alle Knoten in der h-ten Ebene sind kontinuierlich auf der äußersten linken Seite konzentriert.

Vollständige Binärbäume werden aus vollständigen Binärbäumen abgeleitet. Ein Binärbaum mit n Knoten der Tiefe K wird genau dann als vollständiger Binärbaum bezeichnet, wenn jeder Knoten eins zu eins den von 1 bis n nummerierten Knoten im vollständigen Binärbaum der Tiefe K entspricht.

(1) Alle Blattknoten erscheinen auf der k-ten Ebene oder k-l-Ebene (den beiden größten Ebenen)

(2) Für jeden Knoten, wenn sein rechter Teilbaum Die maximale Ebene von ist L, dann ist die maximale Ebene seines linken Teilbaums L oder L+l.

In einem Binärbaum kann der Grad der Knoten auf den unteren beiden Ebenen höchstens kleiner als 2 sein, und die Knoten auf der untersten Ebene sind alle an den Positionen ganz links auf der Ebene konzentriert Binärbaum wird vollständig. Ein Binärbaum, in dem die Knoten auf der untersten Ebene an den Positionen ganz links auf der Ebene konzentriert sind und auf der letzten Ebene einige Knoten auf der rechten Seite fehlen, wird dieser Binärbaum zu einem vollständigen Binärbaum .

Weitere technische Artikel zu häufig gestellten Fragen finden Sie in der Spalte FAQ mehr!

Das obige ist der detaillierte Inhalt vonDie Anzahl der Blattknoten eines vollständigen Binärbaums. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!