HOWTO · Python

Implementieren Sie eine Baumdatenstruktur in Python

In diesem Artikel erfahren Sie, wie Sie eine Baumdatenstruktur in Python implementieren.

Auf dieser Seite

Ein Baum organisiert Daten in Knoten, die durch Kanten verbunden sind. Jede Kante verbindet einen Elternknoten mit einem Kindknoten; ein Knoten ohne Kinder ist ein Blatt. Zu den Baumtypen gehören Binärbäume, ternäre Bäume, binäre Suchbäume und AVL-Bäume. In einem Binärbaum hat jeder Knoten höchstens zwei Kinder. Diese Anleitung erstellt mit einer eigenen Klasse Node einen kleinen Binärbaum, durchläuft ihn in drei Tiefensuchreihenfolgen und stellt anytree als Bibliotheksalternative vor.

Binärbaum mit Wurzel 10, den Kindern 34 und 89 sowie den Kindern 45 und 50 unter 34

Eine Baumstruktur in Python von Grund auf implementieren

Ein einfacher Binärbaumknoten benötigt einen Platz für seinen Wert und Verweise auf seine beiden Kindknoten. Die folgende Klasse Node speichert den Wert in data; left und right sind zunächst None und können später auf Kindknoten verweisen. Durch das Verbinden dieser Objekte entsteht der Baum.

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


root = Node(10)
root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)

Hier ist root der Elternknoten von 34 und 89. Die Knoten 45 und 50 sind Kinder von 34; 89, 45 und 50 sind Blätter. Diese Struktur ist ausdrücklich ein Binärbaum, da jeder Knoten höchstens zwei Kindverweise hat. Andere Baumtypen benötigen möglicherweise eine andere Darstellung, etwa eine Sammlung von Kindern statt der festen Attribute left und right.

Einen Binärbaum in Python durchlaufen

Bei einer Traversierung wird jeder Knoten einmal verarbeitet. Die Reihenfolge hängt davon ab, an welcher Stelle relativ zu den rekursiven Aufrufen der Besuch erfolgt. Bei der Preorder-Traversierung wird zuerst der aktuelle Knoten besucht, dann der linke und der rechte Teilbaum. Bei der Inorder-Traversierung folgen zuerst der linke Teilbaum, dann der aktuelle Knoten und schließlich der rechte Teilbaum. Bei der Postorder-Traversierung werden beide Teilbäume vor dem aktuellen Knoten besucht. Das vollständige Beispiel unten erstellt denselben Baum und gibt jede Reihenfolge aus.

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


def preorder(node):
    if node:
        print(node.data)
        preorder(node.left)
        preorder(node.right)


def inorder(node):
    if node:
        inorder(node.left)
        print(node.data)
        inorder(node.right)


def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data)


root = Node(10)
root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)

print("Pre-order:")
preorder(root)
print("In-order:")
inorder(root)
print("Post-order:")
postorder(root)

Die rekursiven Aufrufe folgen denselben Verweisen left und right, die im ersten Abschnitt erstellt wurden. Für einen anderen Baum können Sie die Traversierungsfunktionen beibehalten und die Knotenerstellung ersetzen. Die gewählte Position des Besuchs bestimmt die Reihenfolge der Werte.

Einen Baum mit einer Python-Bibliothek implementieren

Für Bäume mit vielen Knoten oder Funktionen, die über dieses kleine Binärbaumbeispiel hinausgehen, bietet anytree Beziehungen zwischen Knoten und eine Möglichkeit zum Darstellen des Baums. Installieren Sie die Bibliothek in Ihrer Projektumgebung mit pip install anytree. In ihrer API erwartet Node den Knotennamen als Positionsargument. Um ein Kind anzuhängen, übergeben Sie parent=root als Schlüsselwortargument. RenderTree durchläuft die Hierarchie und liefert das Präfix, mit dem sich jede Ebene anzeigen lässt.

Für dieselbe Struktur wie oben erstellen Sie zunächst root = Node("10"), gefolgt von Node("34", parent=root) und Node("89", parent=root). Mit Node("45", parent=left_child) und Node("50", parent=left_child) platzieren Sie beide Blätter unter 34. Durchlaufen Sie anschließend for pre, fill, node in RenderTree(root) und geben Sie pre + node.name aus. Diese Ausschnitte beschreiben die Bibliotheks-API; Ausführungsnachweise dazu liegen nicht vor.