Inorder Traversal eines Baums in Python

1. Inorder Traversal eines Baumes
2. Inorder-Tree-Traversal-Implementierung in Python

Ein Baum ist eine hierarchische Datenstruktur, die aus Knoten besteht, die durch Kanten verbunden sind. Einen Baum zu durchqueren bedeutet, jeden Knoten des Baums genau einmal zu besuchen.

Wir durchlaufen den Baum für verschiedene Zwecke, wie z. B. Anzeigen der Knoten, Finden des größten und kleinsten Knotens, Suchen, Sortieren usw. In diesem Artikel lernen und implementieren wir die inorder-Traversierung eines Baums in Python.

Inorder Traversal eines Baumes

Die Inorder-Traversierung ist eine Art Tiefendurchquerung. Angenommen, wir haben den folgenden Baum.

Wenn wir inorder Traversal anwenden, werden wir die folgenden Schritte für jeden Knoten ausführen.

1. Zuerst sollten wir alle Knoten des linken Teilbaums besuchen.
2. Dann besuchen wir den übergeordneten Knoten.
3. Dann besuchen wir alle Knoten im rechten Teilbaum.

Wir erhalten die Knoten in der Reihenfolge 4, 2, 5, 1, 6, 3, 7.

Inorder-Tree-Traversal-Implementierung in Python

Es gibt zwei Möglichkeiten, die inorder-Traversierung in Python zu implementieren. Der rekursive und der iterative Ansatz.

Rekursiver Ansatz

Der rekursive Ansatz ist einfach zu implementieren und zu verstehen. Im folgenden Code haben wir eine Klasse Node als Datenstruktur erstellt, um den Baum zu speichern.

Jeder Knoten besteht aus einem Wert, seinem linken und rechten Kind. Die inorder-Traversierung funktioniert rekursiv für die linken und rechten Teilbäume.

Für jeden Knoten wird die inorder-Traversierung durchgeführt, indem sein linker Knoten, der Elternknoten und der rechte Knoten besucht werden.

Beispielcode:

class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.val = value


def inorder(root):
    if root:
        inorder(root.left)
        print(str(root.val))
        inorder(root.right)


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Inorder traversal of the Tree")
inorder(root)

Ausgabe:

Inorder traversal of the Tree
4
2
5
1
6
3
7

Iterativer Ansatz

In einem iterativen Ansatz müssen wir einen Stapel unterhalten, um die Knoten zu speichern, die wir später besuchen werden. Wir haben die Klasse Node im folgenden Code erstellt, genau wie zuvor.

Wir haben einen leeren Stapel erstellt und vom Wurzelknoten aus begonnen, indem wir ihn zum aktuellen Knoten gemacht haben. Wenn der aktuelle Knoten existiert, schieben wir ihn auf den Stapel und gehen zu seinem linken Knoten.

Andernfalls, wenn der Knoten nicht existiert, werden wir ein Element aus dem Stapel ziehen und es drucken. Wenn kein linker Knoten existiert, gehen wir zum rechten Knoten, indem wir ihn zum aktuellen Knoten machen.

Wir werden dieselbe Prozedur iterativ wiederholen, bis sowohl der Stapel als auch das aktuelle Element leer sind.

Beispielcode:

from collections import deque


class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.val = value


def inorder(root):
    stack = deque()
    curr = root
    while stack or curr:
        if curr:
            stack.append(curr)
            curr = curr.left
        else:
            curr = stack.pop()
            print(curr.val)
            curr = curr.right


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Inorder traversal of the Tree")
inorder(root)

Ausgabe:

Inorder traversal of the Tree
4
2
5
1
6
3
7