TechCodeview

Der Binärbaum bedeutet, dass der Knoten maximal zwei Kinder haben kann. Hier deutet der binäre Name selbst darauf hin, dass „zwei“ ist; Daher kann jeder Knoten entweder 0, 1 oder 2 Kinder haben.

Lassen Sie uns den Binärbaum anhand eines Beispiels verstehen.

Der obige Baum ist ein Binärbaum, da jeder Knoten die höchsten zwei untergeordneten Knoten enthält. Die logische Darstellung des obigen Baums ist unten angegeben:

Im obigen Baum enthält Knoten 1 zwei Zeiger, nämlich einen linken und einen rechten Zeiger, die auf den linken bzw. rechten Knoten zeigen. Der Knoten 2 enthält beide Knoten (linker und rechter Knoten); Daher hat es zwei Zeiger (links und rechts). Die Knoten 3, 5 und 6 sind die Blattknoten, also enthalten alle diese Knoten NULL Zeiger auf den linken und rechten Teil.

Eigenschaften des Binärbaums

• Auf jeder Ebene von i beträgt die maximale Anzahl von Knoten 2^ich.
• Die Höhe des Baumes ist definiert als der längste Pfad vom Wurzelknoten zum Blattknoten. Der oben gezeigte Baum hat eine Höhe von 3. Daher ist die maximale Anzahl von Knoten in der Höhe 3 gleich (1+2+4+8) = 15. Im Allgemeinen ist die maximale Anzahl von Knoten in der Höhe h möglich ist (2⁰+ 2¹+ 2²+….2^H) = 2^h+1-1.
• Die minimal mögliche Anzahl von Knoten in der Höhe h ist gleich h+1 .
• Wenn die Anzahl der Knoten minimal ist, ist die Höhe des Baums maximal. Wenn umgekehrt die Anzahl der Knoten maximal ist, ist die Höhe des Baums minimal.

Wenn der Binärbaum n Knoten enthält.

Die Mindesthöhe kann wie folgt berechnet werden:

Wie wir das wissen,

n = 2^h+1-1

n+1 = 2^h+1

Auf beiden Seiten Holzscheite nehmen,

Protokoll₂(n+1) = log2(2^h+1)

Protokoll₂(n+1) = h+1

h = log₂(n+1) - 1

Die maximale Höhe kann wie folgt berechnet werden:

Wie wir das wissen,

n = h+1

h= n-1

Arten von Binärbäumen

Es gibt vier Arten von Binärbäumen:

Vollständiger/richtiger/strikter Binärbaum Vollständiger Binärbaum Perfekter Binärbaum Entarteter Binärbaum Ausgeglichener Binärbaum

1. Vollständiger/richtiger/strikter Binärbaum

Der vollständige Binärbaum wird auch als strikter Binärbaum bezeichnet. Der Baum kann nur dann als vollständiger Binärbaum betrachtet werden, wenn jeder Knoten entweder 0 oder 2 untergeordnete Knoten enthalten muss. Der vollständige Binärbaum kann auch als der Baum definiert werden, in dem jeder Knoten außer den Blattknoten zwei untergeordnete Knoten enthalten muss.

Schauen wir uns das einfache Beispiel des vollständigen Binärbaums an.

Im obigen Baum können wir beobachten, dass jeder Knoten entweder null oder zwei untergeordnete Knoten enthält; Daher handelt es sich um einen vollständigen Binärbaum.

Eigenschaften des vollständigen Binärbaums

• Die Anzahl der Blattknoten ist gleich der Anzahl der internen Knoten plus 1. Im obigen Beispiel beträgt die Anzahl der internen Knoten 5; Daher beträgt die Anzahl der Blattknoten 6.
• Die maximale Anzahl an Knoten entspricht der Anzahl der Knoten im Binärbaum, also 2^h+1-1.
• Die Mindestanzahl an Knoten im vollständigen Binärbaum beträgt 2*h-1.
• Die Mindesthöhe des vollständigen Binärbaums beträgt Protokoll₂(n+1) - 1.
• Die maximale Höhe des vollständigen Binärbaums kann wie folgt berechnet werden:

n= 2*h - 1

n+1 = 2*h

h = n+1/2

Kompletter Binärbaum

Der vollständige Binärbaum ist ein Baum, in dem alle Knoten bis auf die letzte Ebene vollständig gefüllt sind. In der letzten Ebene müssen alle Knoten möglichst links liegen. In einem vollständigen Binärbaum sollten die Knoten von links hinzugefügt werden.

Lassen Sie uns einen vollständigen Binärbaum erstellen.

Der obige Baum ist ein vollständiger Binärbaum, da alle Knoten vollständig gefüllt sind und alle Knoten der letzten Ebene zuerst links hinzugefügt werden.

Eigenschaften des vollständigen Binärbaums

• Die maximale Anzahl von Knoten im vollständigen Binärbaum beträgt 2^h+1- 1.
• Die Mindestanzahl an Knoten im vollständigen Binärbaum beträgt 2^H.
• Die Mindesthöhe eines vollständigen Binärbaums beträgt Protokoll₂(n+1) - 1.
• Die maximale Höhe eines vollständigen Binärbaums beträgt

Perfekter Binärbaum

Ein Baum ist ein perfekter Binärbaum, wenn alle internen Knoten zwei untergeordnete Knoten haben und alle Blattknoten auf derselben Ebene liegen.

Schauen wir uns ein einfaches Beispiel eines perfekten Binärbaums an.

Der folgende Baum ist kein perfekter Binärbaum, da sich nicht alle Blattknoten auf derselben Ebene befinden.

Hinweis: Alle perfekten Binärbäume sind sowohl vollständige Binärbäume als auch vollständige Binärbäume. Das Gegenteil gilt jedoch nicht, d. h. alle vollständigen Binärbäume und vollständigen Binärbäume sind perfekte Binärbäume.

Entarteter Binärbaum

Der entartete Binärbaum ist ein Baum, in dem alle internen Knoten nur ein Kind haben.

Lassen Sie uns den entarteten Binärbaum anhand von Beispielen verstehen.

Der obige Baum ist ein degenerierter Binärbaum, da alle Knoten nur ein Kind haben. Er wird auch als rechtsschiefer Baum bezeichnet, da alle Knoten nur einen rechten untergeordneten Knoten haben.

Der obige Baum ist ebenfalls ein degenerierter Binärbaum, da alle Knoten nur ein Kind haben. Er wird auch als linksschiefer Baum bezeichnet, da alle Knoten nur ein linkes untergeordnetes Element haben.

Ausgewogener Binärbaum

Der ausgeglichene Binärbaum ist ein Baum, in dem sich sowohl der linke als auch der rechte Baum um höchstens 1 unterscheiden. Zum Beispiel: AVL Und Rot-Schwarze Bäume sind ausgeglichene Binärbäume.

Lassen Sie uns den ausgeglichenen Binärbaum anhand von Beispielen verstehen.

Der obige Baum ist ein ausgeglichener Binärbaum, da die Differenz zwischen dem linken Teilbaum und dem rechten Teilbaum Null ist.

Der obige Baum ist kein ausgeglichener Binärbaum, da die Differenz zwischen dem linken Teilbaum und dem rechten Teilbaum größer als 1 ist.

Binärbaum-Implementierung

Ein Binärbaum wird mit Hilfe von Zeigern implementiert. Der erste Knoten im Baum wird durch den Wurzelzeiger dargestellt. Jeder Knoten im Baum besteht aus drei Teilen, nämlich Daten, linkem Zeiger und rechtem Zeiger. Um einen Binärbaum zu erstellen, müssen wir zunächst den Knoten erstellen. Wir erstellen den benutzerdefinierten Knoten wie unten gezeigt:

 struct node { int data, struct node *left, *right; } 

In der obigen Struktur gilt Daten ist der Wert, linker Zeiger enthält die Adresse des linken Knotens und rechter Zeiger enthält die Adresse des rechten Knotens.

CSS fett

Binärbaumprogramm in C

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

Der obige Code ruft die Funktion create() rekursiv auf und erstellt bei jedem rekursiven Aufruf einen neuen Knoten. Wenn alle Knoten erstellt sind, entsteht eine binäre Baumstruktur. Der Vorgang des Besuchs der Knoten wird als Baumdurchquerung bezeichnet. Es gibt drei Arten von Durchquerungen, die zum Besuch eines Knotens verwendet werden:

• Inorder-Durchquerung
• Durchquerung vorbestellen
• Durchquerung von Postanweisungen