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). Knoten), sodass der linke untergeordnete Knoten kleiner als der übergeordnete Knoten ist und der rechte untergeordnete Knoten kleiner ist als der übergeordnete Knoten größer.
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
Beim Inorder-Traversal handelt es sich um den Prozess des Traversierens von Knoten von a binärer Suchbaum durch rekursive Verarbeitung des linken Teilbaums, dann Verarbeitung des Wurzelknotens und schließlich rekursive Verarbeitung des rechten Teilbaums. 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 untergeordneten Elemente, 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.
Durchqueren Sie dann den rechten Teilbaum mit der Wurzel 62. Beginnen Sie mit dem Durchlaufen seines linken Teilbaums, dessen Wurzel bei 58 liegt. Es hat keine untergeordneten Knoten, 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 durchqueren Sie den linken Teilbaum 28 und schließlich den rechten Teilbaum 44. Damit ist die Durchquerung des linken Teilbaums mit der Wurzel 32 abgeschlossen. Der Durchlauf erfolgt in der folgenden Reihenfolge: 56 -> 32 -> 28 -> 44.
Verarbeiten Sie für den rechten Teilbaum den Wert am Wurzelknoten, 62. Als nächstes durchqueren 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 rekursiven Durchlaufens von Knoten eines binären Suchbaums Verarbeiten Sie den linken Teilbaum, verarbeiten Sie dann rekursiv den rechten Teilbaum und verarbeiten Sie schließlich den Wurzelknoten. 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. Zum Abschluss bearbeiten Sie den Wurzelknoten 56.
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. Prozess 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 An), Wo N ist die Größe der Binärbaum. Die räumliche Komplexität aller Durchquerungstechniken beträgt Oh), Wo H ist die Höhe des Binärbaums.
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)
classNode:
def__init__(self, element):
self.left = None
self.right = None
self.value = element# Function to perform the inorder tree traversal
definorder(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
defpostorder(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
defpreorder(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.