© NicoElNino/Shutterstock.com
In der Informatik können Daten auf vielfältige Weise strukturiert und durchlaufen werden. Binäre Bäume sind eine Form der hierarchischen Datenspeicherung, die Baumtraversen als primäre Methode zum Besuchen aller konstituierenden Knoten zum Suchen, Sortieren und für andere Zwecke verwendet. Das Verständnis der verschiedenen Methoden, die zum Durchlaufen von Bäumen verwendet werden, kann Ihnen dabei helfen, grundlegende Operationen an einem Binärbaum durchzuführen. In diesem Artikel erklären wir, was Baumdurchläufe sind, einschließlich Inorder-, Preorder-und Postorder-Durchläufe, mit Beispielen, um Ihnen den Einstieg zu erleichtern.
Was sind Baumdurchläufe?
Baumdurchläufe sind die Methoden, die Informatiker, Entwickler und Softwareingenieure verwenden, um einen binären Baum zu durchlaufen. Es ist auch bekannt als:
Durch den Baum gehen Baumsuche
Bei diesen Methoden werden nacheinander alle Knoten innerhalb des Binärbaums besucht. Im Gegensatz zu einer linearen Datenstruktur wie einer verknüpften Liste oder einer Warteschlange können diese Traversationen auf verschiedene Weise abgeschlossen werden. Die unten erläuterten Hauptmethoden werden zum effizienten Aktualisieren, Löschen, Suchen, Sortieren und Abrufen von Daten verwendet.
Über Binärbäume
Binärbäume sind die am häufigsten verwendete Baumform, die eine hierarchische Datenstruktur ist, die aus miteinander verbundenen Knoten besteht. Jeder Knoten besteht aus linken und rechten Referenzen und einem Datenelement. Jeder Knoten in einem Binärbaum ist mit einem Elternknoten verbunden, aber jeder Elternknoten kann nur maximal 2 Kinder haben. Knoten ohne Kinder heißen Blätter. Knoten, die sich einen übergeordneten Knoten teilen, werden als Geschwister bezeichnet. Der Knoten an der Spitze eines Binärbaums wird Wurzel genannt.
Wenn ein Binärbaum vollständig gefüllt ist, spricht man von einem vollständigen Baum. Bäume werden von links nach rechts mit Knoten gefüllt. Sie können Knoten nach ihrer Höhe positionieren, die die Anzahl der Kanten zwischen dem Stamm-und dem Indexknoten ist, oder nach ihrer Tiefe, die die Anzahl der Kanten zwischen dem Knoten und dem am weitesten entfernten Blattknoten ist.
Benutzen Sie Baumdurchläufe, um jeden Knoten in einem Baum zu besuchen
Ein wichtiges Merkmal dieser Durchläufe ist, dass jeder Knoten im Baum besucht wird. Da Bäume nichtlineare Datenstrukturen sind, gibt es viele Möglichkeiten und Reihenfolgen, in denen Sie sicherstellen können, dass jeder Knoten der Reihe nach besucht wird. Es gibt keine einzelne Traversierung, sondern mehrere Traversierungsalgorithmen, mit denen Sie arbeiten können.
Tree Traversals sind wichtig
Die Beherrschung von Tree Traversals ist eine Schlüsselkompetenz für die Organisation und Arbeit mit Daten. Denn Bäume sind eine sehr verbreitete Datenstruktur und wegen ihrer übersichtlichen Darstellung von Datenbeziehungen und Hierarchien weit verbreitet.
Sie können diese Traversierungsmethoden und Beispiele für effizientere Datensuchen oder-einfügungen verwenden. Werfen wir einen Blick auf die folgenden Schlüsselmethoden:
Hier ist ein Beispielbaum:
Eine Illustration einer Baumstruktur.
©”TNGD”.com
1. Vorbestellungsdurchlauf
Dies ist eine Art Tiefendurchlauf, bei dem zuerst der übergeordnete Knoten besucht wird, dann der linke untergeordnete Knoten und dann der rechte untergeordnete Knoten. Wenn ein Baum unter Verwendung der preOrder-Methode durchlaufen wird, wird zuerst der Wurzelknoten besucht, dann die sequentiellen linken und rechten Unterbäume zuerst, bis der gesamte Baum durchlaufen ist. PreOrder Traversal bietet eine effiziente Methode zum Kopieren eines Baums.
Hier ist das Beispiel für PreOrder Traversal für den obigen Baum: A > B > D > E > C > F > G
Und Hier ist der PreOrder-Algorithmus:
Algorithmus zur PreOrder-Traversierung einer Baumstruktur.
©”TNGD”.com
2. InOrder Traversal
Dies ist eine Art Tiefendurchlauf, bei dem der linke Kindknoten besucht wird, dann der Elternknoten und dann der rechte Kindknoten. InOrder-Durchläufe verlaufen über den am weitesten links liegenden Teilbaum und enden am am weitesten rechts liegenden Teilbaum. Diese Art der Traversierung erzeugt Daten, die in aufsteigender Reihenfolge organisiert sind.
Hier ist das Beispiel für den inOrder-Durchlauf für den obigen Baum: D > B > E > A > F > C > G
Und hier ist der inOrder-Algorithmus:
Algorithmus zum InOrder Traversal einer Baumstruktur.
©”TNGD”.com
3. PostOrder-Traversierung
Diese dritte Art der Tiefendurchquerung besucht den linken untergeordneten Knoten, dann den rechten untergeordneten Knoten und dann den übergeordneten Knoten. Bei der PostOrder-Baumdurchquerung werden alle Teilbäume zuerst (von unten links) besucht, wobei die Wurzel zuletzt besucht wird. PostOrder Traversal ist eine effiziente Möglichkeit, einen Baum zu löschen.
Hier ist das Beispiel für den postOrder-Durchlauf für den obigen Baum: D > E > B > F > G > C > A
Und hier ist der postOrder-Algorithmus:
Algorithmus für die postOrder-Traversierung einer Baumstruktur.
©”TNGD”.com
Es gibt auch eine Breitendurchquerung, die Knoten von oben nach unten und von links nach rechts besucht. Dies ist die einzige Form des Breitendurchlaufs.
Aufrunden
Wie Sie sehen können, machen Baumdurchläufe die Verwaltung von hierarchische Daten sehr einfach. Die Algorithmen sind einfach und wenn Sie sich verirren, können Sie einen einfachen Baum zeichnen, um sich zu orientieren. Diese Methoden sind so effizient, dass Sie vollständige Binärbäume aus bereitgestellten Pre-und Post-Order-Traversals konstruieren können. Üben Sie diese Methoden, um sie zu beherrschen und Ihr Wissen zu erweitern.
Was sind Tree Traversals (Inorder, Preorder und Postorder) – mit Beispielen FAQs (häufig gestellte Fragen)
Was ist eine Datenstruktur?
Datenstrukturen sind die spezifischen Formate, die zum Organisieren von Daten verwendet werden, damit sie sicher gespeichert und effizient verwaltet und abgerufen werden können.
Was sind die Haupttypen von Bäumen?
Neben Binärbäumen gehören zu den Haupttypen von Bäumen:
Heap-Bäume Syntaxbäume Versuche B-Bäume T-Bäume
Was ist ein perfekter Binärbaum?
Ein perfekter Binärbaum hat alle Blattknoten in der gleichen Tiefe und alle Elternknoten haben zwei Kinder. Dies ist eine andere Art, einen vollständig gefüllten, lückenlosen Baum zu beschreiben.
Was sind Beispiele für Nicht-Baum-Datenstrukturen?
Nicht-Baum-Datenstrukturen sind hauptsächlich lineare Datenstrukturen, die Folgendes umfassen:
Arrays A Bitmap Matrix Paralleles Array Doppelt verknüpfte Liste Selbstorganisierende Liste
Was sind abstrakte Datentypen?
Abstrakte Datentypen (ADT) sind mathematische Modelle, die zum Strukturieren von Daten verwendet werden können und erleichtern groß angelegte Programmierung. In der Informatik können ADTs verwendet werden, um Daten für eine Vielzahl von Computeranwendungen zu verpacken und zu verwalten.