Wozu dienen Binärbäume?

Binärbäume können zur Implementierung binärer Suchbäume und binärer Heaps verwendet werden. In der Informatik ist ein Binärbaum eine Baumstruktur mit höchstens zwei Teilbäumen pro Knoten „Rechter Teilbaum“ kann je nach Verwendungszweck unterteilt werden in: 1. Vollständiger Binärbaum; 2. Vollständiger Binärbaum;

Die Rolle von Binärbäumen

Binärbäume werden häufig zur Implementierung binärer Suchbäume und Binärbäume verwendet Haufen.

In der Informatik ist ein Binärbaum eine Baumstruktur mit höchstens zwei Teilbäumen pro Knoten. Normalerweise werden Teilbäume als „linker Teilbaum“ und „rechter Teilbaum“ bezeichnet.

Je nach Verwendung kann es unterteilt werden in:

1. Vollständiger Binärbaum – wenn die Höhe des Binärbaums h ist, mit Ausnahme der h-ten Ebene, alle anderen Ebenen (1~h-1) Die Anzahl der Knoten hat die maximale Anzahl erreicht. Es gibt Blattknoten in Schicht h, und die Blattknoten sind von links nach rechts angeordnet.

2. Vollständiger Binärbaum – ein Binärbaum, in dem jeder Knoten außer den Blattknoten linke und rechte Unterblätter hat und die Blattknoten alle unten liegen.

3. Ausgeglichener Binärbaum – Ein ausgeglichener Binärbaum wird auch AVL-Baum genannt (im Gegensatz zum AVL-Algorithmus). Er ist ein binärer Sortierbaum und hat die folgenden Eigenschaften: Er ist ein leerer Baum Der absolute Wert des Höhenunterschieds zwischen dem linken und dem rechten Teilbaum überschreitet nicht 1, und sowohl der linke als auch der rechte Teilbaum sind ausgeglichene Binärbäume.

Erweiterte Informationen

Ein Binärbaum mit der Tiefe h hat höchstens einen Knoten (h>=1) und mindestens h Knoten. Wenn für jeden Binärbaum die Anzahl der Blattknoten N0 und die Gesamtzahl der Knoten mit Grad 2 N2 beträgt, dann ist N0=N2+1.

Wenn jeder Knoten eines vollständigen Binärbaums mit N Knoten sequentiell gespeichert wird, haben die Knoten die folgende Beziehung: Wenn I die Knotennummer ist, dann ist, wenn I> 1, die Nummer seines übergeordneten Knotens ist I/2. Wenn 2*IN, gibt es kein linkes Kind. Wenn 2*I+1

Das obige ist der detaillierte Inhalt vonWozu dienen Binärbäume?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!