Python - Tree Traversal Algorithmen
Beim Durchlaufen werden alle Knoten eines Baums besucht und möglicherweise auch deren Werte gedruckt. Da alle Knoten über Kanten (Links) verbunden sind, beginnen wir immer am Wurzelknoten (Kopfknoten). Das heißt, wir können nicht zufällig auf einen Knoten in einem Baum zugreifen. Es gibt drei Möglichkeiten, wie wir einen Baum durchqueren können:
- In-Order-Traversal
- Traversal vorbestellen
- Nachbestellungsdurchquerung
In-Order-Traversal
Bei dieser Traversal-Methode wird zuerst der linke Teilbaum, dann die Wurzel und später der rechte Teilbaum besucht. Wir sollten immer daran denken, dass jeder Knoten selbst einen Teilbaum darstellen kann.
Im folgenden Python-Programm verwenden wir die Node-Klasse, um Platzhalter für den Stammknoten sowie den linken und rechten Knoten zu erstellen. Dann erstellen wir eine Einfügefunktion, um dem Baum Daten hinzuzufügen. Schließlich wird die Inorder-Traversal-Logik implementiert, indem eine leere Liste erstellt und zuerst der linke Knoten gefolgt vom Stamm- oder Elternknoten hinzugefügt wird. Zuletzt wird der linke Knoten hinzugefügt, um die Inorder-Durchquerung abzuschließen. Bitte beachten Sie, dass dieser Vorgang für jeden Unterbaum wiederholt wird, bis alle Knoten durchlaufen sind.
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Inorder traversal
# Left -> Root -> Right
def inorderTraversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left)
res.append(root.data)
res = res + self.inorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:
[10, 14, 19, 27, 31, 35, 42]Traversal vorbestellen
Bei dieser Traversal-Methode wird zuerst der Wurzelknoten, dann der linke Teilbaum und schließlich der rechte Teilbaum besucht.
Im folgenden Python-Programm verwenden wir die Node-Klasse, um Platzhalter für den Stammknoten sowie den linken und rechten Knoten zu erstellen. Dann erstellen wir eine Einfügefunktion, um dem Baum Daten hinzuzufügen. Schließlich wird die Durchlauflogik vor der Bestellung implementiert, indem eine leere Liste erstellt und zuerst der Stammknoten und dann der linke Knoten hinzugefügt werden. Zuletzt wird der rechte Knoten hinzugefügt, um den Vorbestellungsdurchlauf abzuschließen. Bitte beachten Sie, dass dieser Vorgang für jeden Unterbaum wiederholt wird, bis alle Knoten durchlaufen sind.
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Preorder traversal
# Root -> Left ->Right
def PreorderTraversal(self, root):
res = []
if root:
res.append(root.data)
res = res + self.PreorderTraversal(root.left)
res = res + self.PreorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:
[27, 14, 10, 19, 35, 31, 42]Nachbestellungsdurchquerung
Bei dieser Traversal-Methode wird der Stammknoten zuletzt besucht, daher der Name. Zuerst durchlaufen wir den linken Teilbaum, dann den rechten Teilbaum und schließlich den Wurzelknoten.
Im folgenden Python-Programm verwenden wir die Node-Klasse, um Platzhalter für den Stammknoten sowie den linken und rechten Knoten zu erstellen. Dann erstellen wir eine Einfügefunktion, um dem Baum Daten hinzuzufügen. Schließlich wird die Durchlauflogik nach der Bestellung implementiert, indem eine leere Liste erstellt und zuerst der linke Knoten und dann der rechte Knoten hinzugefügt werden. Zuletzt wird der Stamm- oder übergeordnete Knoten hinzugefügt, um den Durchlauf nach der Bestellung abzuschließen. Bitte beachten Sie, dass dieser Vorgang für jeden Unterbaum wiederholt wird, bis alle Knoten durchlaufen sind.
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal(self, root):
res = []
if root:
res = self.PostorderTraversal(root.left)
res = res + self.PostorderTraversal(root.right)
res.append(root.data)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:
[10, 19, 14, 31, 42, 35, 27]