Implementieren Sie eine Baumdatenstruktur in Python

1. Einen Baum von Grund auf in Python implementieren
2. Durchlaufen Sie einen Binärbaum in Python
3. Implementieren Sie einen Baum mithilfe einer Python-Bibliothek

Ein Baum ist eine der Datenstrukturen. Eine Datenstruktur ist nichts anderes als die Art und Weise, wie wir die Daten im Speicher organisieren. Ein Baum ist eine Kombination aus Knoten (auch als Eckpunkte bezeichnet) und Kanten. Ein Baum kann eine beliebige Anzahl von Knoten und Kanten haben. In einem Knoten speichern wir die Daten, und eine Kante ist ein Pfad zwischen 2 Knoten. Es gibt verschiedene Arten von Bäumen wie einen Binärbaum, einen ternären Baum, einen Binärer Suchbaum, einen AVL-Baum usw.

Knotentypen in einem Baum:

1. Übergeordneter Knoten: Ein Knoten mit einem oder mehreren untergeordneten Knoten.
2. Untergeordneter Knoten: Ein Knoten mit einem übergeordneten Knoten.
3. Blattknoten: Ein Knoten, der keine untergeordneten Knoten hat.

In diesem Artikel erfahren Sie zunächst, wie Sie einen Baum von Grund auf ohne Verwendung einer Bibliothek implementieren. Später erfahren Sie, wie Sie einen Baum mithilfe einer Python-Bibliothek implementieren.

Einen Baum von Grund auf in Python implementieren

Um einen Baum in Python zu erstellen, müssen wir zunächst eine Node-Klasse erstellen, die einen einzelnen Knoten darstellt. Diese Node-Klasse enthält 3 Variablen. Die erste ist die left, die auf das linke Kind zeigt, die zweite Variable data, die den Wert für diesen Knoten enthält, und die right Variable, die auf das rechte Kind zeigt.

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

Lassen Sie uns einen Baum initialisieren.

root = Node(10)

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

Der Baum sieht aus wie unten.

          10
        /    \
       34      89
     /    \ 
    45    50 

Wenn Sie ein Objekt der Klasse Node erstellen, wird der Konstruktor __init__ aufgerufen und alle Variablen in diesem Konstruktor werden initialisiert. Die root enthält den Wurzelknoten des Baumes mit dem Wert 10 sowie root.left und root.right, mit denen wir das linke Kind mit dem Wert 34 und das rechte einfügen Kind zum Wurzelknoten mit dem Wert 89. Da es sich um einen Binärbaum handelt, enthält jeder Knoten höchstens zwei Knoten.

Am Ende fügen wir zwei weitere Knoten in den Baum ein, nämlich 45 und 50, als untergeordnete Knoten für den Knoten 34. Sie können eine beliebige Anzahl von Knoten in einen Baum einfügen, abhängig von der Art des Baums, den Sie erstellen.

Durchlaufen Sie einen Binärbaum in Python

Jetzt haben wir einen Baum erstellt. Überqueren wir also den Baum, um die Baumelemente zu drucken. Eine Durchquerung besucht jeden Knoten in einem Baum. Jeder Knoten in einem Baum wird beim Durchlaufen dreimal besucht. Wir durchqueren einen Baum von oben nach unten und von links nach rechts.

Traversal vorbestellen

Wenn wir beim Durchlaufen eines Baums den Knoten zum ersten Mal sehen, drucken wir diesen Knoten aus und führen dann eine Rekursion auf dem linken Knoten und dann auf dem rechten Knoten durch.

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

Ausgabe:

10 
34 
45 
50 
89

In-Order-Traversal

Während des Durchlaufs in der Reihenfolge führen wir zuerst eine Rekursion auf dem linken Knoten durch. Wenn wir dann denselben Knoten zum zweiten Mal besuchen, drucken wir diesen Knoten. Dann führen wir eine Rekursion auf dem rechten Knoten durch.

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

Ausgabe:

45 
34 
50 
10 
89

Nachbestellungsdurchquerung

Bei der Nachbestellungsdurchquerung führen wir eine Rekursion für den linken und den rechten Knoten durch. Wenn wir dann zum dritten Mal denselben Knoten besuchen, drucken wir diesen Knoten.

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

Ausgabe:

45
50
34
89
10

Implementieren Sie einen Baum mithilfe einer Python-Bibliothek

Wie wir gesehen haben, dauert die Implementierung eines Baums von Grund auf einige Zeit und erfordert viel Code. Eine einfachere Möglichkeit, einen Baum in Python zu implementieren, ist die Verwendung einer Bibliothek namens anytree. Mit der Bibliothek anytree können Sie einen Baum erstellen, ohne eine Menge Code zu schreiben.

Um die Bibliothek anytree zu verwenden, müssen wir sie zuerst mit der Hilfe des folgenden Befehls installieren.

pip install anytree

Auch hier erstellen wir denselben Baum, den wir zuvor erstellt haben. Jetzt können wir Node und RenderTree aus der Bibliothek anytree importieren.

from anytree import Node, RenderTree

root = Node(10)

level_1_child_1 = Node(34, parent=root)
level_1_child_2 = Node(89, parent=root)
level_2_child_1 = Node(45, parent=level_1_child_1)
level_2_child_2 = Node(50, parent=level_1_child_2)

for pre, fill, node in RenderTree(root):
    print("%s%s" % (pre, node.name))

# Tree Structure
#          10
#        /    \
#       34      89
#     /    \
#    45    50

Ausgabe:

10
├── 34
│   └── 45
└── 89
    └── 50

Hier wird Node einen Knoten für uns, der zwei Parameter akzeptiert. Der erste ist der Wert des Knotens und der zweite ist der Name des übergeordneten Knotens (dies ist ein optionaler Parameter). Da in unserem Baum der Knoten root der einzige Knoten ist, der kein übergeordnetes Element hat, übergeben wir beim Erstellen des Knotens root nur den ersten Parameter: den Wert des Knotens und nicht den zweiten Parameter. Die Methode RenderTree hilft uns, den gesamten Baum wie in der Ausgabe gezeigt zu drucken.