Heim  >  Artikel  >  So zählen Sie Binärbaumknoten

So zählen Sie Binärbaumknoten

尚
Original
2019-06-10 15:30:0128614Durchsuche

So zählen Sie Binärbaumknoten

1. Die i-te Ebene des Binärbaums hat höchstens 2^(i-1) Knoten

2 die meisten 2^k- 1 Knoten

3. Wenn ein Binärbaum n0 Blattknoten und n2 Knoten mit Grad 2 enthält, muss eine Beziehung bestehen: n2=n0-1

4. Die Tiefe eines vollständigen Binärbaums mit n Knoten beträgt [log2n]+1.[] bedeutet Rundung

5. Wenn die Tiefe eines vollständigen Binärbaums mit n Knoten von oben nach unten und von links verläuft Nummerierung von 1 bis n nach rechts, dann gilt für jeden Knoten mit der Nummer i im vollständigen Binärbaum:

Wenn i=1, dann ist der Knoten die Wurzel des Binärbaums und hat keine Eltern Nummer ist Der Knoten [i/2] ist sein übergeordneter Knoten.

Wenn 2i>n, dann hat der Knoten keinen linken untergeordneten Knoten, andernfalls ist der Knoten mit der Nummer 2i sein linker untergeordneter Knoten 🎜>Wenn 2i+1>n, dann hat der Knoten keinen rechten untergeordneten Knoten, andernfalls ist der Knoten mit der Nummer 2i+1 sein rechter untergeordneter Knoten.

Wenn die Anzahl der Knoten eines vollständigen Binärbaums n ist, ermitteln Sie die Höhe h der Zahlen n0, n1, n2, die Anzahl der linken untergeordneten Knoten nl und die Anzahl der rechten untergeordneten Knoten nr?

(n0 ist ein Knoten mit Grad 0, n1 ist ein Knoten mit Grad 1, n2 ist ein Knoten mit Grad 2)

Das obige ist der detaillierte Inhalt vonSo zählen Sie Binärbaumknoten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn