Binärbaum in C
In C, a binärer Baum ist eine Instanz einer Baumdatenstruktur mit einem Elternknoten, der eine maximale Anzahl von zwei Kindknoten besitzen kann; 0, 1 oder 2 Nachkommenknoten. Jeder einzelne Knoten in a binärer Baum hat einen eigenen Wert und zwei Zeiger auf seine Kinder, einen Zeiger für das linke Kind und den anderen für das rechte Kind.
Deklaration des Binärbaums
A binärer Baum kann in C mit einem Objekt namens deklariert werden Struktur das einen der Knoten im Baum darstellt.
Struktur Knoten {
Datentyp var_name ;
Struktur Knoten * links ;
Struktur Knoten * Rechts ;
} ;
Oben ist eine Erklärung von einem binärer Baum Knotenname als Knoten. Es enthält drei Werte; eine ist die datenspeichernde Variable und die anderen beiden sind die Zeiger auf das Kind. (linkes und rechtes Kind des Elternknotens).
Fakten zum Binärbaum
Selbst für große Datenmengen kann die Verwendung von a binärer Baum macht die Suche einfacher und schneller. Die Anzahl der Äste ist nicht begrenzt. Im Gegensatz zu einem Array können Bäume jeder Art hergestellt und vermehrt werden, je nachdem, was von einer Person benötigt wird.
Binärbaum-Implementierung in C
Im Folgenden finden Sie eine Schritt-für-Schritt-Anleitung zur Implementierung von a Binärer Baum in C.
Schritt 1: Deklarieren Sie einen binären Suchbaum
Erstellen Sie einen Strukturknoten mit drei Datentypen, z. B. Daten, *left_child und *right_child, wobei Daten ganzzahlig sein können und sowohl *left_child- als auch *right_child-Knoten als NULL deklariert werden können oder nicht.
Struktur Knoten{
int Daten ;
Struktur Knoten * rechtes_kind ;
Struktur Knoten * left_child ;
} ;
Schritt 2: Erstellen Sie neue Knoten im binären Suchbaum
Erstellen Sie einen neuen Knoten, indem Sie eine Funktion erstellen, die eine Ganzzahl als Argument akzeptiert und den Zeiger auf den neuen Knoten bereitstellt, der mit diesem Wert erstellt wurde. Verwenden Sie die Funktion malloc() in C für die dynamische Speicherzuweisung für den erstellten Knoten. Initialisieren Sie das linke und rechte untergeordnete Element mit NULL und geben Sie den Knotennamen zurück.
Struktur Knoten * erstellen ( Datentyp Daten )
{
Struktur Knoten * Knotenname = malloc ( Größe von ( Struktur Knoten ) ) ;
Knotenname -> Daten = Wert ;
Knotenname -> left_child = Knotenname -> rechtes_kind = NULL ;
zurückkehren Knotenname ;
}
Schritt 3: Fügen Sie rechte und linke untergeordnete Elemente in den Binärbaum ein
Erstellen Sie die Funktionen insert_left und insert_right, die zwei Eingaben akzeptieren, nämlich den einzufügenden Wert und den Zeiger auf den Knoten, mit dem beide Kinder verbunden werden. Rufen Sie die Funktion create auf, um einen neuen Knoten zu erstellen, und weisen Sie den zurückgegebenen Zeiger dem linken Zeiger des linken untergeordneten Knotens oder dem rechten Zeiger des rechten untergeordneten Knotens des Stammelternteils zu.
Struktur Knoten * einfügen_links ( Struktur Knoten * Wurzel , Datentyp Daten ) {Wurzel -> links = erstellen ( Daten ) ;
zurückkehren Wurzel -> links ;
}
Struktur Knoten * einfügen_rechts ( Struktur Knoten * Wurzel , Datentyp Daten ) {
Wurzel -> Rechts = erstellen ( Daten ) ;
zurückkehren Wurzel -> Rechts ;
}
Schritt 4: Zeigen Sie Knoten des Binärbaums mit Traversal-Methoden an
Wir können Bäume anzeigen, indem wir drei Traversierungsmethoden in C verwenden. Diese Traversierungsmethoden sind:
1: Vorbestellungsdurchquerung
Bei dieser Traversierungsmethode werden wir die Knoten in einer Richtung von durchlaufen parent_node->left_child->right_child .
Leere Vorbestellung ( Knoten * Wurzel ) {Wenn ( Wurzel ) {
Druckf ( '%D \N ' , Wurzel -> Daten ) ;
display_pre_order ( Wurzel -> links ) ;
display_pre_order ( Wurzel -> Rechts ) ;
}
}
2: Post-Order-Traversal
Bei dieser Traversierungsmethode werden wir die Knoten in einer Richtung von durchlaufen left_child->right_child->parent_node-> .
Leere display_post_order ( Knoten * Wurzel ) {Wenn ( binär_baum ) {
display_post_order ( Wurzel -> links ) ;
display_post_order ( Wurzel -> Rechts ) ;
Druckf ( '%D \N ' , Wurzel -> Daten ) ;
}
}
3: In-Order-Traversal
Bei dieser Traversierungsmethode werden wir die Knoten in einer Richtung von durchlaufen left_node->root_child->right_child .
Leere display_in_order ( Knoten * Wurzel ) {Wenn ( binär_baum ) {
display_in_order ( Wurzel -> links ) ;
Druckf ( '%D \N ' , Wurzel -> Daten ) ;
display_in_order ( Wurzel -> Rechts ) ;
}
}
Schritt 5: Löschen im Binärbaum durchführen
Wir können die erstellten löschen Binärer Baum indem beide Kinder mit der Elternknotenfunktion in C wie folgt gelöscht werden.
Leere löschen_t ( Knoten * Wurzel ) {Wenn ( Wurzel ) {
löschen_t ( Wurzel -> links ) ;
löschen_t ( Wurzel -> Rechts ) ;
frei ( Wurzel ) ;
}
}
C Programm des binären Suchbaums
Das Folgende ist die vollständige Implementierung des binären Suchbaums in der C-Programmierung:
#include#include
Struktur Knoten {
int Wert ;
Struktur Knoten * links , * Rechts ;
} ;
Struktur Knoten * Knoten1 ( int Daten ) {
Struktur Knoten * temp = ( Struktur Knoten * ) malloc ( Größe von ( Struktur Knoten ) ) ;
temp -> Wert = Daten ;
temp -> links = temp -> Rechts = NULL ;
zurückkehren temp ;
}
Leere drucken ( Struktur Knoten * Wurzelknoten ) // Anzeigen der Knoten!
{
Wenn ( Wurzelknoten != NULL ) {
drucken ( Wurzelknoten -> links ) ;
Druckf ( '%D \N ' , Wurzelknoten -> Wert ) ;
drucken ( Wurzelknoten -> Rechts ) ;
}
}
Struktur Knoten * insert_node ( Struktur Knoten * Knoten , int Daten ) // Knoten einfügen!
{
Wenn ( Knoten == NULL ) zurückkehren Knoten1 ( Daten ) ;
Wenn ( Daten < Knoten -> Wert ) {
Knoten -> links = insert_node ( Knoten -> links , Daten ) ;
} anders Wenn ( Daten > Knoten -> Wert ) {
Knoten -> Rechts = insert_node ( Knoten -> Rechts , Daten ) ;
}
zurückkehren Knoten ;
}
int hauptsächlich ( ) {
Druckf ( 'C-Implementierung des binären Suchbaums! \N \N ' ) ;
Struktur Knoten * Elternteil = NULL ;
Elternteil = insert_node ( Elternteil , 10 ) ;
insert_node ( Elternteil , 4 ) ;
insert_node ( Elternteil , 66 ) ;
insert_node ( Elternteil , Vier fünf ) ;
insert_node ( Elternteil , 9 ) ;
insert_node ( Elternteil , 7 ) ;
drucken ( Elternteil ) ;
zurückkehren 0 ;
}
Im obigen Code deklarieren wir zuerst a Knoten verwenden Struktur . Dann initialisieren wir einen neuen Knoten als „ Knoten1 ” und Speicher dynamisch zuweisen mit malloc() in C mit Daten und zwei Zeigern Typkinder unter Verwendung des deklarierten Knotens. Danach zeigen wir den Knoten durch an printf() Funktion und rufen Sie sie in der auf hauptsächlich() Funktion. Dann ist die Einfügungsknoten () Die Funktion wird erstellt, wobei die Knotendaten NULL sind Knoten1 zurückgezogen wird, ansonsten werden Daten in die platziert Knoten (Elternteil) des linken und rechten Kindes. Das Programm startet die Ausführung von der hauptsächlich() -Funktion, die einen Knoten mit einigen Beispielknoten als untergeordnete Elemente generiert und dann In-Order-Traversal-Methoden verwendet, um die Knoteninhalte zu drucken.
Ausgang
Abschluss
Bäume werden häufig verwendet, um Daten in einer nichtlinearen Form zu halten. Binäre Bäume sind Arten von Bäumen, bei denen jeder Knoten (Elternteil) zwei Nachkommen hat, das linke Kind und das rechte Kind. A binärer Baum ist eine vielseitige Methode zum Übertragen und Speichern von Daten. Es ist effizienter im Vergleich zu Linked-List in C. Im obigen Artikel haben wir das Konzept von a gesehen Binärer Baum mit der schrittweisen Umsetzung von a Binärer Suchbaum in C.