Menü

Bäume in C ++: Grundlegende Terminologie, Traversal-Techniken und C ++ - Baumtypen

  • Haupt
  • Andere
  • Bäume in C ++: Grundlegende Terminologie, Traversal-Techniken und C ++ - Baumtypen

trees c basic terminology

Versuchen Sie Unser Instrument, Um Probleme Zu Beseitigen

In diesem ausführlichen Tutorial zu C ++ - Bäumen werden Baumtypen, Baumdurchquerungstechniken und grundlegende Terminologie mit Bildern und Beispielprogrammen erläutert:

In dieser C ++ - Serie haben wir bisher die lineare Datenstruktur sowohl statischer als auch dynamischer Natur gesehen. Nun werden wir mit der nichtlinearen Datenstruktur fortfahren. Die erste Datenstruktur in dieser Kategorie ist 'Bäume'.

Bäume sind nichtlineare hierarchische Datenstrukturen. Ein Baum ist eine Sammlung von Knoten, die über „Kanten“ miteinander verbunden sind, die entweder gerichtet oder ungerichtet sind. Einer der Knoten wird als 'Wurzelknoten' bezeichnet, und die verbleibenden Knoten werden als untergeordnete Knoten oder als Blattknoten des Wurzelknotens bezeichnet.

Im Allgemeinen kann jeder Knoten so viele untergeordnete Knoten haben, aber nur einen übergeordneten Knoten.

=> Schauen Sie sich die gesamte C ++ - Schulungsserie an

Baum in C ++

Knoten eines Baums befinden sich entweder auf derselben Ebene, die als Schwesterknoten bezeichnet wird, oder sie können eine Eltern-Kind-Beziehung haben. Knoten mit demselben übergeordneten Knoten sind Geschwisterknoten.

Was du lernen wirst:

Bäume in C ++

Unten ist ein Beispielbaum mit seinen verschiedenen Teilen angegeben.

Baum in C ++ mit seinen verschiedenen Teilen

Lassen Sie uns die Definitionen einiger grundlegender Begriffe durchgehen, die wir für Bäume verwenden.

  • Wurzelknoten: Dies ist der oberste Knoten in der Baumhierarchie. Im obigen Diagramm ist Knoten A der Wurzelknoten. Beachten Sie, dass der Stammknoten kein übergeordnetes Element hat.
  • Blattknoten: Es ist der unterste Knoten in einer Baumhierarchie. Blattknoten sind die Knoten, die keine untergeordneten Knoten haben. Sie werden auch als externe Knoten bezeichnet. Die Knoten E, F, G, H und C im obigen Baum sind alle Blattknoten.
  • Teilbaum: Der Teilbaum repräsentiert verschiedene Nachkommen eines Knotens, wenn die Wurzel nicht null ist. Ein Baum besteht normalerweise aus einem Wurzelknoten und einem oder mehreren Teilbäumen. Im obigen Diagramm sind (B-E, B-F) und (D-G, D-H) Teilbäume.
  • Elternknoten: Jeder Knoten außer dem Wurzelknoten, der einen untergeordneten Knoten und eine Kante nach oben zum übergeordneten Knoten hat.
  • Ahnenknoten: Es ist ein beliebiger Vorgängerknoten auf einem Pfad von der Wurzel zu diesem Knoten. Beachten Sie, dass die Wurzel keine Vorfahren hat. Im obigen Diagramm sind A und B die Vorfahren von E.
  • Schlüssel: Es repräsentiert den Wert eines Knotens.
  • Niveau: Repräsentiert die Generierung eines Knotens. Ein Wurzelknoten befindet sich immer auf Stufe 1. Untergeordnete Knoten der Wurzel befinden sich auf Stufe 2, Enkelkinder der Wurzel befinden sich auf Stufe 3 und so weiter. Im Allgemeinen befindet sich jeder Knoten auf einer höheren Ebene als sein übergeordneter Knoten.
  • Pfad: Der Pfad ist eine Folge aufeinanderfolgender Kanten. Im obigen Diagramm ist der Pfad zu E A => B-> E.
  • Grad: Der Grad eines Knotens gibt die Anzahl der untergeordneten Knoten an. In dem obigen Diagramm beträgt der Grad von B und D jeweils 2, während der Grad von C 0 ist.

Arten von C ++ - Bäumen

Die Baumdatenstruktur kann wie im folgenden Diagramm dargestellt in die folgenden Untertypen eingeteilt werden.

Baumarten in C ++

# 1) Allgemeiner Baum

Der allgemeine Baum ist die grundlegende Darstellung eines Baumes. Es hat einen Knoten und einen oder mehrere untergeordnete Knoten. Der Knoten der obersten Ebene, d. H. Der Wurzelknoten, ist auf Ebene 1 vorhanden, und alle anderen Knoten können auf verschiedenen Ebenen vorhanden sein.

Ein allgemeiner Baum ist in der folgenden Abbildung dargestellt.

Allgemeiner Baum

Wie in der obigen Abbildung gezeigt, kann ein allgemeiner Baum eine beliebige Anzahl von Teilbäumen enthalten. Die Knoten B, C und D sind auf Ebene 2 vorhanden und sind Geschwisterknoten. In ähnlicher Weise sind auch die Knoten E, F, G und H Geschwisterknoten.

Die auf verschiedenen Ebenen vorhandenen Knoten können eine Eltern-Kind-Beziehung aufweisen. In der obigen Figur sind die Knoten B, C und D Kinder von A. Die Knoten E und F sind Kinder von B, während die Knoten G und H Kinder von D sind.

Der allgemeine Baum wird unten anhand der C ++ - Implementierung demonstriert:

#include using namespace std; //declaration for new tree node struct node { int data; struct node *left; struct node *right; }; //allocates new node struct node* newNode(int data) { // declare and allocate new node struct node* node = new struct node(); node->data = data; // Assign data to this node // Initialize left and right children as NULL node->left = NULL; node->right = NULL; return(node); } int main() { /*create root node*/ struct node *rootNode = newNode(10); cout<<'General tree created is as follows:'<data<left = newNode(20); rootNode->right = newNode(30); cout<<' '<left->data<<' '<right->data; cout<left->left = newNode(40); cout<<' '<<'/'<left->left->data; return 0; }

Ausgabe:

Der allgemeine Baum wird wie folgt erstellt:

10

/ .

20 30

/.

40

# 2) Wälder

Immer wenn wir den Wurzelknoten aus dem Baum und den Kanten löschen, die die Elemente der nächsten Ebene und die Wurzel verbinden, erhalten wir disjunkte Baumgruppen, wie unten gezeigt.

Wälder

In der obigen Abbildung haben wir zwei Gesamtstrukturen erhalten, indem wir den Wurzelknoten A und die drei Kanten gelöscht haben, die den Wurzelknoten mit den Knoten B, C und D verbunden haben.

# 3) Binärer Baum

Eine Baumdatenstruktur, in der jeder Knoten höchstens zwei untergeordnete Knoten hat, wird als Binärbaum bezeichnet. Ein Binärbaum ist die beliebteste Baumdatenstruktur und wird in einer Reihe von Anwendungen wie Ausdrucksauswertung, Datenbanken usw. verwendet.

Die folgende Abbildung zeigt einen Binärbaum.

Binärer Baum

In der obigen Abbildung sehen wir, dass die Knoten A, B und D jeweils zwei Kinder haben. Ein Binärbaum, in dem jeder Knoten genau null oder zwei Kinder hat, wird als vollständiger Binärbaum bezeichnet. In diesem Baum gibt es keine Knoten mit einem Kind.

Ein vollständiger Binärbaum hat einen Binärbaum, der vollständig gefüllt ist, mit Ausnahme der niedrigsten Ebene, die von links nach rechts gefüllt wird. Der oben gezeigte Binärbaum ist ein vollständiger Binärbaum.

Es folgt ein einfaches Programm zur Demonstration eines Binärbaums. Beachten Sie, dass die Ausgabe des Baums die Inorder-Traversal-Sequenz des Eingabebaums ist.

#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

# 4) Binärer Suchbaum

Der geordnete Binärbaum wird als binärer Suchbaum bezeichnet. In einem binären Suchbaum sind die Knoten links kleiner als der Wurzelknoten, während die Knoten rechts größer oder gleich dem Wurzelknoten sind.

Ein Beispiel für einen binären Suchbaum ist unten dargestellt.

Binärer Suchbaum

In der obigen Abbildung sehen wir, dass die linken Knoten alle kleiner als 20 sind, was das Wurzelelement ist. Die rechten Knoten sind dagegen größer als der Wurzelknoten. Der binäre Suchbaum wird in Such- und Sortiertechniken verwendet.

# 5) Ausdrucksbaum

Ein Binärbaum, der zum Auswerten einfacher arithmetischer Ausdrücke verwendet wird, wird als Ausdrucksbaum bezeichnet.

Ein einfacher Ausdrucksbaum ist unten dargestellt.

Ausdrucksbaum

Im obigen Beispielausdrucksbaum stellen wir den Ausdruck (a + b) / (a-b) dar. Wie in der obigen Abbildung gezeigt, repräsentieren die Nicht-Blattknoten des Baums die Operatoren des Ausdrucks, während die Blattknoten die Operanden repräsentieren.

Ausdrucksbäume werden hauptsächlich zum Lösen algebraischer Ausdrücke verwendet.

Baumdurchquerungstechniken

Wir haben lineare Datenstrukturen wie Arrays, verknüpfte Listen, Stapel, Warteschlangen usw. gesehen. Alle diese Datenstrukturen haben eine gemeinsame Verfahrtechnik, die die Struktur nur auf eine Weise durchläuft, d. H. Linear.

Bei Bäumen haben wir jedoch verschiedene Durchquerungstechniken, wie unten aufgeführt:

# 1) In der Reihenfolge: Bei dieser Durchquerungstechnik durchlaufen wir zuerst den linken Teilbaum, bis sich im linken Teilbaum keine Knoten mehr befinden. Danach besuchen wir den Wurzelknoten und fahren dann fort, den rechten Teilbaum zu durchlaufen, bis im rechten Teilbaum keine Knoten mehr zu durchlaufen sind. Somit ist die Reihenfolge der InOrder-Durchquerung links-> root-> rechts.

# 2) Vorbestellung: Bei der Vorbestellungs-Traversal-Technik verarbeiten wir zuerst den Wurzelknoten, dann den gesamten linken Teilbaum und schließlich den rechten Teilbaum. Daher ist die Reihenfolge der Vorbestellungsdurchquerung root-> left-> right.

# 3) Nachbestellung: Bei der Traversal-Technik nach der Bestellung durchlaufen wir den linken Teilbaum, dann den rechten Teilbaum und schließlich den Wurzelknoten. Die Reihenfolge der Durchquerung für die Nachbestellungstechnik lautet left-> right-> root.

Wenn n der Wurzelknoten ist und 'l' und 'r' linke bzw. rechte Knoten des Baums sind, lauten die Baumdurchquerungsalgorithmen wie folgt:

In der Reihenfolge (lnr) Algorithmus:

  1. Durchqueren Sie den linken Teilbaum mit inOrder (linker Teilbaum).
  2. Besuchen Sie den Stammknoten (n).
  3. Durchqueren Sie den rechten Teilbaum mit inOrder (rechter Teilbaum).

Vorbestellungsalgorithmus (nlr):

  1. Besuchen Sie den Stammknoten (n).
  2. Durchqueren Sie den linken Teilbaum mit der Vorbestellung (linker Teilbaum).
  3. Durchqueren Sie den rechten Teilbaum mit der Vorbestellung (rechter Teilbaum).

Postorder (lrn) Algorithmus:

  1. Durchqueren Sie den linken Teilbaum mit postOrder (linker Teilbaum).
  2. Durchqueren Sie den rechten Teilbaum mit postOrder (rechter Teilbaum).
  3. Besuchen Sie den Stammknoten (n).

Aus den obigen Algorithmen der Durchquerungstechniken sehen wir, dass die Techniken rekursiv auf einen bestimmten Baum angewendet werden können, um das gewünschte Ergebnis zu erhalten.

Betrachten Sie den folgenden Baum.

Wo finden Sie den Netzwerksicherheitsschlüssel?

Postorder (lrn) Algorithmus

Unter Verwendung der obigen Traversal-Techniken wird die Traversal-Sequenz für den obigen Baum unten angegeben:

  1. InOrder Traversal: 2 3 5 6 10
  2. PreOrder Traversal: 6 3 2 5 10
  3. PostOrder-Durchquerung: 2 5 3 10 6

Fazit

Bäume sind eine nichtlineare hierarchische Datenstruktur, die in vielen Anwendungen im Softwarebereich verwendet wird.

Im Gegensatz zu linearen Datenstrukturen, bei denen es nur eine Möglichkeit gibt, die Liste zu durchlaufen, können wir Bäume auf verschiedene Arten durchlaufen. In diesem Tutorial haben wir uns eingehend mit den Traversiertechniken und den verschiedenen Baumarten befasst.

=> Schauen Sie sich hier das C ++ Anfängerhandbuch an

Literatur-Empfehlungen

^