So durchqueren Sie einen binären Suchbaum
Es gibt mehr als eine Möglichkeit, alle Knoten in einem BST zu besuchen.
Binärbäume gehören zu den am häufigsten verwendeten Datenstrukturen in der Programmierung. Ein binärer Suchbaum (BST) ermöglicht die Speicherung von Daten in Form von Knoten (übergeordneter Knoten und untergeordneter Knoten), sodass der linke untergeordnete Knoten kleiner als der übergeordnete Knoten und der rechte untergeordnete Knoten größer ist.
Binäre Suchbäume ermöglichen effiziente Durchlauf-, Such-, Lösch- und Einfügevorgänge. In diesem Artikel erfahren Sie mehr über die drei Möglichkeiten, einen binären Suchbaum zu durchlaufen: Preorder-Traversal, Inorder-Traversal und Postorder-Traversal.
Inorder-Durchquerung
Bei der Inorder-Traversierung werden Knoten eines binären Suchbaums durch rekursive Verarbeitung des linken Teilbaums, dann Verarbeitung des Wurzelknotens und schließlich rekursive Verarbeitung des rechten Teilbaums durchlaufen. Da Knoten in aufsteigender Reihenfolge verarbeitet werden, wird die Technik als Inorder-Traversal bezeichnet.
Beim Traversieren wird jeder Knoten in einer Baumdatenstruktur genau einmal besucht.
Algorithmus der Inorder-Traversierung
Wiederholen Sie diesen Vorgang, um alle Knoten des BST zu durchlaufen:
- Durchlaufen Sie rekursiv den linken Teilbaum.
- Besuchen Sie den Wurzelknoten.
- Durchlaufen Sie rekursiv den rechten Teilbaum.
Visualisierung der Inorder-Traversierung
Ein visuelles Beispiel kann helfen, die Durchquerung des binären Suchbaums zu erklären. Diese Abbildung zeigt die Inorder-Traversierung eines beispielhaften binären Suchbaums:
In diesem binären Suchbaum ist 56 der Wurzelknoten. Zuerst müssen Sie den linken Teilbaum 32, dann den Wurzelknoten 56 und dann den rechten Teilbaum 62 durchlaufen.
Für den Teilbaum 32 durchqueren Sie zunächst den linken Teilbaum 28. Dieser Teilbaum hat keine Kinder, also durchqueren Sie als nächstes den 32. Knoten. Als nächstes durchqueren Sie den rechten Teilbaum 44, der ebenfalls keine Kinder hat. Daher ist die Durchlaufreihenfolge für den Teilbaum mit der Wurzel 32 28 -> 32 -> 44.
Besuchen Sie als Nächstes den Wurzelknoten 56.
Dann durchqueren Sie den rechten Teilbaum mit der Wurzel 62. Beginnen Sie mit der Durchquerung seines linken Teilbaums mit der Wurzel 58. Er hat keine Kinder, also besuchen Sie als Nächstes den Knoten 62. Durchlaufen Sie abschließend den rechten Teilbaum 88, der ebenfalls keine untergeordneten Elemente hat.
Der Algorithmus besucht also die Knoten des Baums in der folgenden Reihenfolge:
28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88
Anwendung von Inorder Traversal
Sie können Inorder-Traversal verwenden, um die Werte von Knotenelementen in aufsteigender Reihenfolge abzurufen. Um die Werte in absteigender Reihenfolge zu erhalten, kehren Sie einfach den Vorgang um: Besuchen Sie den rechten Teilbaum, dann den Wurzelknoten und dann den linken Teilbaum. Sie können den Algorithmus verwenden, um den Präfixausdruck eines Ausdrucksbaums zu finden.
Traversal vorbestellen
Die Vorbestellungsdurchquerung ähnelt inorder, verarbeitet jedoch den Wurzelknoten, bevor rekursiv der linke Teilbaum und dann der rechte Teilbaum verarbeitet werden.
Algorithmus der Vorbestellungsdurchquerung
Wiederholen Sie diesen Vorgang, um alle Knoten des BST zu durchlaufen:
- Besuchen Sie den Wurzelknoten.
- Durchlaufen Sie rekursiv den linken Teilbaum.
- Durchlaufen Sie rekursiv den rechten Teilbaum.
Visualisierung der Vorbestellungsdurchquerung
Die folgende Abbildung zeigt die Vorbestellungsdurchquerung des binären Suchbaums:
Beginnen Sie in diesem binären Suchbaum mit der Verarbeitung des Wurzelknotens 56. Durchlaufen Sie dann den linken Teilbaum 32 und anschließend den rechten Teilbaum 62.
Verarbeiten Sie für den linken Teilbaum den Wert am Wurzelknoten 32. Als nächstes durchlaufen Sie den linken Teilbaum 28 und schließlich den rechten Teilbaum 44. Damit ist die Durchquerung des linken Teilbaums mit der Wurzel 32 abgeschlossen. Die Durchquerung erfolgt in der folgenden Reihenfolge : 56 -> 32 -> 28 -> 44.
Verarbeiten Sie für den rechten Teilbaum den Wert am Wurzelknoten (62). Als nächstes durchlaufen Sie den linken Teilbaum (58) und schließlich den rechten Teilbaum (88). Auch hier hat keiner der Knoten untergeordnete Knoten, sodass die Durchquerung an diesem Punkt abgeschlossen ist.
Sie haben den gesamten Baum in der folgenden Reihenfolge durchlaufen:
56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88
Anwendung von Preorder Traversal
Sie können Preorder Traversal verwenden, um am einfachsten eine Kopie des Baums zu erstellen.
Postorder-Traversal
Postorder-Traversal ist der Prozess des Durchlaufens von Knoten eines binären Suchbaums durch rekursive Verarbeitung des linken Teilbaums, dann rekursive Verarbeitung des rechten Teilbaums und schließlich Verarbeitung des Wurzelknotens. Da der Wurzelknoten nach beiden Teilbäumen verarbeitet wird, wird diese Methode als Postorder-Traversal bezeichnet.
Algorithmus der Postorder-Traversierung
Wiederholen Sie diesen Vorgang, um alle Knoten des BST zu durchlaufen:
- Durchlaufen Sie rekursiv den linken Teilbaum.
- Durchlaufen Sie rekursiv den rechten Teilbaum.
- Besuchen Sie den Wurzelknoten.
Visualisierung des Postorder Traversal
Die folgende Abbildung zeigt die Postorder-Durchquerung des binären Suchbaums:
Beginnen Sie mit dem Durchlaufen des linken Teilbaums 32 und dann des rechten Teilbaums 62. Schließen Sie mit der Verarbeitung des Wurzelknotens 56 ab.
Um den Teilbaum mit der Wurzel 32 zu verarbeiten, durchqueren Sie seinen linken Teilbaum 28. Da 28 keine Kinder hat, wechseln Sie zum rechten Teilbaum 44. Verarbeiten Sie 44, da er auch keine Kinder hat. Verarbeiten Sie abschließend den Wurzelknoten 32. Sie haben diesen Teilbaum in der Reihenfolge 28 -> 44 -> 32 durchlaufen.
Verarbeiten Sie den rechten Teilbaum mit demselben Ansatz, um Knoten in der Reihenfolge 58 -> 88 → 62 zu besuchen.
Verarbeiten Sie abschließend den Wurzelknoten 56. Sie durchlaufen den gesamten Baum in dieser Reihenfolge:
28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56
Anwendung von Postorder Traversal
Sie können Postorder-Traversal verwenden, um einen Baum vom Blatt bis zur Wurzel zu löschen. Sie können es auch verwenden, um den Postfix-Ausdruck einer Ausdrucksbaumstruktur zu finden.
Um alle Blattknoten eines bestimmten Knotens zu besuchen, bevor Sie den Knoten selbst besuchen, können Sie die Postorder-Traversal-Technik verwenden.
Zeitliche und räumliche Komplexität binärer Suchbaumdurchquerungen
Die zeitliche Komplexität aller drei Traversierungstechniken beträgt O(n), wobei n die Größe des Binärbaums ist. Die räumliche Komplexität aller Traversierungstechniken beträgt O(h), wobei h die Höhe des Binärbaums ist.
Die Größe des Binärbaums entspricht der Anzahl der Knoten in diesem Baum. Die Höhe des Binärbaums ist die Anzahl der Kanten zwischen dem Wurzelknoten des Baums und seinem am weitesten entfernten Blattknoten.
Python-Code für die Durchquerung binärer Suchbäume
Nachfolgend finden Sie ein Python-Programm zur Durchführung aller drei Durchläufe im binären Suchbaum:
# Node class is used to create individual nodes
# of the Binary Search Tree (BST)
class Node:
def __init__(self, element):
self.left = None
self.right = None
self.value = element
# Function to perform the inorder tree traversal
def inorder(root):
if root:
# Traverse left subtree
inorder(root.left)
# Traverse root
print(str(root.value) + ", ", end='')
# Traverse right subtree
inorder(root.right)
# Function to perform the postorder tree traversal
def postorder(root):
if root:
# Traverse left subtree
postorder(root.left)
# Traverse right subtree
postorder(root.right)
# Traverse root
print(str(root.value) + ", ", end='')
# Function to perform the preorder tree traversal
def preorder(root):
if root:
# Traverse root
print(str(root.value) + ", ", end='')
# Traverse left subtree
preorder(root.left)
# Traverse right subtree
preorder(root.right)
# Creating nodes of the tree
root = Node(56)
root.left = Node(32)
root.right = Node(62)
root.left.left = Node(28)
root.left.right = Node(44)
root.right.left = Node(58)
root.right.right = Node(88)
print("Inorder Traversal of BST: ")
inorder(root)
print()
print("Preorder Traversal of BST: ")
preorder(root)
print()
print("Postorder Traversal of BST: ")
postorder(root)
Dieses Programm sollte die folgende Ausgabe erzeugen:
Wichtige Algorithmen für Programmierer
Algorithmen sind ein wesentlicher Teil der Reise eines jeden Programmierers. Für einen Programmierer ist es von entscheidender Bedeutung, sich mit Algorithmen gut auszukennen. Sie sollten mit einigen Algorithmen wie Zusammenführungssortierung, Schnellsortierung, binäre Suche, lineare Suche, Tiefensuche usw. vertraut sein.