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]