binary tree data structure c
In diesem ausführlichen Lernprogramm zum Binärbaum in C ++ werden Typen, Darstellung, Durchquerung, Anwendungen und Implementierung von Binärbäumen in C ++ erläutert:
Ein Binärbaum ist eine weit verbreitete Baumdatenstruktur. Wenn jeder Knoten eines Baums höchstens zwei untergeordnete Knoten hat, wird der Baum als Binärbaum bezeichnet.
Ein typischer Binärbaum besteht also aus folgenden Komponenten:
- Ein linker Teilbaum
- Ein Wurzelknoten
- Ein rechter Teilbaum
=> Sehen Sie sich die vollständige Liste der C ++ - Tutorials in dieser Reihe an.
Was du lernen wirst:
- Binärbaum in C ++
- Arten von Binärbäumen
- Binäre Baumdarstellung
- Implementierung des Binärbaums in C ++
- Binäre Baumdurchquerung
- Anwendungen von Binärbaum
- Fazit
- Literatur-Empfehlungen
Binärbaum in C ++
Eine bildliche Darstellung eines Binärbaums ist unten dargestellt:
In einem bestimmten Binärbaum beträgt die maximale Anzahl von Knoten auf einer beliebigen Ebene 2l-1Dabei ist 'l' die Ebenennummer.
Im Fall des Wurzelknotens auf Ebene 1 ist also die maximale Anzahl von Knoten = 21-1= 20= 1
Da jeder Knoten in einem Binärbaum höchstens zwei Knoten hat, beträgt die maximale Anzahl der Knoten auf der nächsten Ebene 2 * 2l-1.
Arten von Funktionen c ++
Bei einem binären Baum mit einer Tiefe oder Höhe von h ist die maximale Anzahl von Knoten in einem binären Baum mit einer Höhe von h = 2h- 1.
Daher ist in einem Binärbaum der Höhe 3 (siehe oben) die maximale Anzahl von Knoten = 23-1 = 7.
Lassen Sie uns nun die verschiedenen Arten von Binärbäumen diskutieren.
Arten von Binärbäumen
Im Folgenden sind die häufigsten Arten von Binärbäumen aufgeführt.
# 1) Vollständiger Binärbaum
Ein Binärbaum, in dem jeder Knoten 0 oder 2 Kinder hat, wird als vollständiger Binärbaum bezeichnet.
Oben ist ein vollständiger Binärbaum dargestellt, in dem wir sehen können, dass alle Knoten außer den Blattknoten zwei untergeordnete Knoten haben. Wenn L die Anzahl der Blattknoten und 'l' die Anzahl der internen oder Nicht-Blattknoten ist, ist für einen vollständigen Binärbaum L = l + 1.
# 2) Schließe den Binärbaum ab
In einem vollständigen Binärbaum sind alle Ebenen bis auf die letzte Ebene gefüllt, und auf der letzten Ebene befinden sich alle Knoten links.
Der oben gezeigte Baum ist ein vollständiger Binärbaum. Ein typisches Beispiel für einen vollständigen Binärbaum ist ein Binärheap, den wir in den späteren Tutorials diskutieren werden.
# 3) Perfekter Binärbaum
Ein Binärbaum wird als perfekt bezeichnet, wenn alle internen Knoten zwei untergeordnete Knoten haben und sich alle Blattknoten auf derselben Ebene befinden.
Ein oben gezeigtes Beispiel für einen Binärbaum ist ein perfekter Binärbaum, da jeder seiner Knoten zwei untergeordnete Knoten hat und alle Blattknoten auf derselben Ebene liegen.
Ein perfekter binärer Baum der Höhe h hat 2h- 1 Anzahl von Knoten.
# 4) Ein entarteter Baum
Ein Binärbaum, in dem jeder interne Knoten nur ein Kind hat, wird als entarteter Baum bezeichnet.
Der oben gezeigte Baum ist ein entarteter Baum. In Bezug auf die Leistung dieses Baums entsprechen die entarteten Bäume den verknüpften Listen.
# 5) Ausgeglichener Binärbaum
Ein Binärbaum, in dem sich die Tiefe der beiden Teilbäume jedes Knotens niemals um mehr als 1 unterscheidet, wird als ausgeglichener Binärbaum bezeichnet.
Der oben gezeigte Binärbaum ist ein ausgeglichener Binärbaum, da die Tiefe der beiden Teilbäume jedes Knotens nicht mehr als 1 beträgt. AVL-Bäume, die wir in unseren nachfolgenden Tutorials diskutieren werden, sind ein gemeinsamer ausgeglichener Baum.
Binäre Baumdarstellung
Einem Binärbaum wird auf zwei Arten Speicher zugewiesen.
# 1) Sequentielle Darstellung
Dies ist die einfachste Technik zum Speichern einer Baumdatenstruktur. Ein Array wird zum Speichern der Baumknoten verwendet. Die Anzahl der Knoten in einem Baum definiert die Größe des Arrays. Der Wurzelknoten des Baums wird am ersten Index im Array gespeichert.
Im Allgemeinen, wenn ein Knoten am i gespeichert istthOrt, dann wird das linke und rechte Kind an 2i bzw. 2i + 1 Ort gespeichert.
Betrachten Sie den folgenden Binärbaum.
Die sequentielle Darstellung des obigen Binärbaums ist wie folgt:
In der obigen Darstellung sehen wir, dass das linke und rechte Kind jedes Knotens an den Positionen 2 * (Knotenort) bzw. 2 * (Knotenort) +1 gespeichert sind.
Zum Beispiel, Die Position von Knoten 3 im Array ist 3. Das linke Kind wird also auf 2 * 3 = 6 gesetzt. Das rechte Kind befindet sich an der Position 2 * 3 +1 = 7. Wie wir im Array sehen können, sind Kinder von 3, die 6 und 7 sind, werden an den Stellen 6 und 7 im Array platziert.
Die sequentielle Darstellung des Baums ist ineffizient, da das Array, in dem die Baumknoten gespeichert werden, viel Speicherplatz beansprucht. Wenn der Baum wächst, wird diese Darstellung ineffizient und schwierig zu verwalten.
Dieser Nachteil wird überwunden, indem die Baumknoten in einer verknüpften Liste gespeichert werden. Beachten Sie, dass wenn der Baum leer ist, der erste Speicherort des Stammknotens auf 0 gesetzt wird.
# 2) Darstellung der verknüpften Liste
Bei dieser Art der Darstellung wird eine verknüpfte Liste zum Speichern der Baumknoten verwendet. Mehrere Knoten sind an nicht zusammenhängenden Stellen im Speicher verstreut, und die Knoten sind über die Eltern-Kind-Beziehung wie ein Baum verbunden.
Das folgende Diagramm zeigt eine verknüpfte Listendarstellung für einen Baum.
Wie in der obigen Darstellung gezeigt, besteht jeder verknüpfte Listenknoten aus drei Komponenten:
- Linker Zeiger
- Datenteil
- Rechter Zeiger
Der linke Zeiger hat einen Zeiger auf das linke untergeordnete Element des Knotens. Der rechte Zeiger hat einen Zeiger auf das rechte untergeordnete Element des Knotens, während der Datenteil die tatsächlichen Daten des Knotens enthält. Wenn für einen bestimmten Knoten (Blattknoten) keine untergeordneten Knoten vorhanden sind, werden der linke und der rechte Zeiger für diesen Knoten auf Null gesetzt, wie in der obigen Abbildung gezeigt.
Implementierung des Binärbaums in C ++
Als nächstes entwickeln wir ein Binärbaumprogramm unter Verwendung einer verknüpften Listendarstellung in C ++. Wir verwenden eine Struktur, um einen einzelnen Knoten zu deklarieren, und entwickeln dann mithilfe einer Klasse eine verknüpfte Liste von Knoten.
#include using namespace std; struct bintree_node{ bintree_node *left; bintree_node *right; int data; } ; class bst{ bintree_node *root; public: bst(){ root=NULL; } int isempty() { return(root==NULL); } void insert(int item); void displayBinTree(); void printBinTree(bintree_node *); }; void bst::insert(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL){ parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bst::displayBinTree(){ printBinTree(root); } void bst::printBinTree(bintree_node *ptr){ if(ptr!=NULL){ printBinTree(ptr->left); cout<<' '<data<<' '; printBinTree(ptr->right); } } int main(){ bst b; b.insert(20); b.insert(10); b.insert(5); b.insert(15); b.insert(40); b.insert(45); b.insert(30); cout<<'Binary tree created: '< Ausgabe:
Binärbaum erstellt:
5 10 15 20 30 40 45
Binäre Baumdurchquerung
Wir haben bereits in unserem grundlegenden Tutorial über Bäume das Durchqueren besprochen. In diesem Abschnitt implementieren wir ein Programm, das Knoten in den Binärbaum einfügt und alle drei Durchläufe, d. H. Inorder, Preorder und Postorder, für einen Binärbaum demonstriert.
#include using namespace std; //binary tree node declaration struct bintree_node{ bintree_node *left; bintree_node *right; char data; } ; class bintree_class{ bintree_node *root; public: bintree_class(){ root=NULL; } int isempty() { return(root==NULL); } void insert_node(int item); void inorder_seq(); void inorder(bintree_node *); void postorder_seq(); void postorder(bintree_node *); void preorder_seq(); void preorder(bintree_node *); }; void bintree_class::insert_node(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL) { parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bintree_class::inorder_seq() { inorder(root); } void bintree_class::inorder(bintree_node *ptr) { if(ptr!=NULL){ inorder(ptr->left); cout<<' '<data<<' '; inorder(ptr->right); } } void bintree_class::postorder_seq() { postorder(root); } void bintree_class::postorder(bintree_node *ptr) { if(ptr!=NULL){ postorder(ptr->left); postorder(ptr->right); cout<<' '<data<<' '; } } void bintree_class::preorder_seq() { preorder(root); } void bintree_class::preorder(bintree_node *ptr) { if(ptr!=NULL){ cout<<' '<data<<' '; preorder(ptr->left); preorder(ptr->right); } } int main() { bintree_class bintree; bintree.insert_node('A'); bintree.insert_node('B'); bintree.insert_node('C'); bintree.insert_node('D'); bintree.insert_node('E'); bintree.insert_node('F'); bintree.insert_node('G'); cout<<'Inorder traversal:'< Ausgabe:
Inorder Traversal:
A B C D E F G.
Versandhandelsdurchquerung:
G F E D C B A.
Vorbestellungsdurchquerung:
A B C D E F G.
Anwendungen von Binärbaum
Ein Binärbaum wird in vielen Anwendungen zum Speichern von Daten verwendet.
Einige der wichtigen Anwendungen von Binärbäumen sind nachstehend aufgeführt:
Wer ist für den Geschäftswert eines Scrum-Teams verantwortlich?
- Binäre Suchbäume: Binärbäume werden verwendet, um einen binären Suchbaum zu erstellen, der in vielen Suchanwendungen wie Mengen und Karten in vielen Sprachbibliotheken verwendet wird.
- Hash Trees: Wird verwendet, um Hashes hauptsächlich in speziellen Bildsignaturanwendungen zu überprüfen.
- Haufen: Heaps werden zum Implementieren von Prioritätswarteschlangen verwendet, die für Router, Planungsprozessoren im Betriebssystem usw. verwendet werden.
- Huffman-Codierung: Der Huffman-Codierungsbaum wird sowohl in Komprimierungsalgorithmen (wie der Bildkomprimierung) als auch in kryptografischen Anwendungen verwendet.
- Syntaxbaum: Compiler erstellen häufig Syntaxbäume, die nichts anderes als Binärbäume sind, um die im Programm verwendeten Ausdrücke zu analysieren.
Fazit
Binäre Bäume sind in der gesamten Softwareindustrie weit verbreitete Datenstrukturen. Binäre Bäume sind die Bäume, deren Knoten höchstens zwei untergeordnete Knoten haben. Wir haben verschiedene Arten von Binärbäumen gesehen, wie einen vollständigen Binärbaum, einen vollständigen Binärbaum, einen perfekten Binärbaum, einen entarteten Binärbaum, einen ausgeglichenen Binärbaum usw.
Binärbaumdaten können auch mit Inorder-, Preorder- und Postorder-Traversal-Techniken durchlaufen werden, die wir in unserem vorherigen Tutorial gesehen haben. Im Speicher kann ein Binärbaum mithilfe einer verknüpften Liste (nicht zusammenhängender Speicher) oder Arrays (sequentielle Darstellung) dargestellt werden.
Die Darstellung verknüpfter Listen ist im Vergleich zu Arrays effizienter, da Arrays viel Platz beanspruchen.
=> Schauen Sie sich hier die besten C ++ - Schulungsanleitungen an.
Literatur-Empfehlungen
- AVL-Baum- und Heap-Datenstruktur in C ++
- B-Baum- und B + -Baum-Datenstruktur in C ++
- Warteschlangendatenstruktur in C ++ mit Illustration
- Stapeldatenstruktur in C ++ mit Illustration
- Datenstruktur für zirkuläre verknüpfte Listen in C ++ mit Abbildung
- Datenstruktur der verknüpften Liste in C ++ mit Abbildung
- Einführung in Datenstrukturen in C ++
- Datenstruktur der Prioritätswarteschlange in C ++ mit Abbildung