Drucken Sie den Binärbaum in Python

1. Binärer Baum in Python
2. Durchlaufreihenfolge eines Baums
3. Implementierung von Binary Tree in Python
4. Drucken Sie den gesamten Binärbaum mit Python

Dieser Artikel wird einen binären Baum besprechen und wie wir ihn verwenden können. Wir werden auch sehen, wie wir es mit Python drucken können.

Wir lernen die Terminologien kennen, die bei der Arbeit an Binärbäumen verwendet werden. Wir werden uns auch ein Beispiel für einen binären Baum mit Python-Code ansehen.

Binärer Baum in Python

Die Binärbäume von Python sind eine der effizientesten verfügbaren Datenstrukturen, und sie sind auch relativ einfach zu implementieren. Ein Binärbaum ist eine baumartige Datenstruktur mit einem Wurzelknoten und zwei untergeordneten Knoten, einem linken und einem rechten.

Jeder Knoten kann eine beliebige Anzahl von untergeordneten Knoten haben. In diesem Artikel wird beschrieben, wie Sie einen Binärbaum in Python erstellen und durchlaufen.

Lassen Sie uns die mit dem Baum verbundene Terminologie besser verstehen.

1. Wurzel: Der oberste Knoten eines Baums ohne Eltern. Jeder Baum hat eine Wurzel.
2. Edge: Edge ist eine Eltern-Kind-Verbindung.
3. Blatt: Ein Knoten ohne Kinder. Der letzte Knoten des Baums. Bäume haben mehrere Blattknoten.
4. Teilbaum: Der Baum verwendet einen Knoten als Wurzel.
5. Tiefe: Die Tiefe ist der Abstand des Knotens von der Wurzel.
6. Höhe: Die Höhe des Knotens ist der Abstand zum tiefsten Knoten des Teilbaums.
7. Höhe des Baums: Die Höhe des Baums ist der höchste Knoten und entspricht der gleichen Höhe wie der Wurzelknoten.

Durchlaufreihenfolge eines Baums

Der Baum wird durchlaufen, indem am Wurzelknoten begonnen wird und die linken und rechten untergeordneten Knoten besucht werden. Die Reihenfolge, in der die Knoten besucht werden, wird Traversierungsreihenfolge genannt.

In-Order Traversal Tree

Es gibt verschiedene Möglichkeiten, einen Binärbaum zu durchlaufen. Am gebräuchlichsten ist die In-Order-Traversierung, die den linken, den Stamm- und den rechten untergeordneten Knoten besucht.

Traversal Tree vorbestellen

Ein weiterer Standarddurchlauf ist der Vorbestellungsdurchlauf, der zuerst den Stammknoten besucht, dann das linke Kind und schließlich das rechte Kind.

Das In-Order-Traversal ist der effizienteste Weg, alle Knoten in einem Binärbaum zu besuchen, da es jeden Knoten nur einmal besucht. Die Vorbestellungsdurchquerung ist etwas weniger effizient, da sie den Wurzelknoten zweimal aufruft.

Die Traversierung vor der Bestellung wird jedoch häufig verwendet, wenn wir den Baum während der Traversierung ändern möchten, da es einfach ist, zuerst den Stammknoten und dann die linken und rechten untergeordneten Knoten zu ändern.

Hier ist eine Syntax und einfache Implementierung von the in-order traversal in Python.

def inorder(node):
    if node is not None:
        inorder(node.left)
        print(node.val)
        inorder(node.right)

So codieren wir also, wenn wir die In-Order-Traversal-Methode verwenden möchten.

Und hier ist die Vorbestellungsdurchquerung:

def preorder(node):
    if node is not None:
        print(node.val)
        preorder(node.left)
        preorder(node.right)

Traversal nach der Bestellung

Wir können den Baum auch in der Post-Order durchlaufen, die das linke Kind, das rechte Kind und dann den Wurzelknoten besucht. Das Traversieren nach der Bestellung ist jedoch weniger verbreitet, da es weniger effizient ist als die beiden anderen Traversen.

Es gibt andere Möglichkeiten, einen binären Baum zu durchlaufen, wie z. B. das Traversieren in der Ebenenreihenfolge, bei dem die Knoten im Baum Ebene für Ebene besucht werden. Wir werden diese Traversierung jedoch in diesem Artikel nicht behandeln.

Nachdem wir nun gesehen haben, wie man einen Binärbaum durchläuft, schauen wir uns an, wie man einen Binärbaum erstellt und ihn mit Python druckt.

Implementierung von Binary Tree in Python

Wir wissen, was ein binärer Baum ist und welche Terminologie damit verbunden ist. Wir werden den Binärbaum mit Python implementieren, um besser zu verstehen, wie der Binärbaum funktioniert.

Alles, was wir tun müssen, ist, diesen Code hierher zu kopieren und neuen Code hineinzuschreiben. Da es Teil des Binärbaums ist, müssen wir den neuen Code mit den bereits geschriebenen Codes schreiben.

Beispielcode:

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

    def printTree(root):
        print(root.data)
        print("L", root.left.data, end=": ")
        print("R", root.right.data, end=": ")


bnt1 = binaryTreeNode(1)
bnt2 = binaryTreeNode(2)
bnt3 = binaryTreeNode(3)
bnt1.left = bnt2
bnt1.right = bnt3
bnt2.left = bnt1
bnt2.right = bnt3
bnt3.left = bnt1
bnt3.right = bnt2

Die Methode def printTree(root) liefert uns die Wurzel. Denn wenn wir die Wurzel des Baums haben, können wir mit den Knoten auf den gesamten Baum zugreifen.

Nachdem wir die Methode deklariert haben, prüfen wir einige Bedingungen. Wir können die Methode def PrintTree(root) im obigen Code sehen.

Lassen Sie uns versuchen, Root 1, bnt1, zu drucken, um zu sehen, was wir bekommen.

Beispielcode:

print(bnt1.printTree())

Ausgang:

1
L 2: R 3: None

Die Ausgabe zeigt, dass der Baum zwei Knoten enthält (den linken Knoten und den rechten Knoten). Die Daten im linken Knoten sind 2 und im rechten Knoten sind 3.

Wir können auch bnt2 und bnt3 drucken, um zu sehen, welche Datenpunkte sie enthalten.

Drucken Sie den gesamten Binärbaum mit Python

Hier ist der gesamte Binärbaum. Wir können es ausführen und mehr darüber erfahren, wie ein Binärbaum mit Python mit der random-Bibliothek von Python gedruckt wird.

import random


class BinaryTree:
    def __init__(self, key):
        self.key = key
        self.right = None
        self.left = None

    def insert(self, key):
        if self.key == key:
            return
        elif self.key < key:
            if self.right is None:
                self.right = BinaryTree(key)
            else:
                self.right.insert(key)
        else:  # self.key > key
            if self.left is None:
                self.left = BinaryTree(key)
            else:
                self.left.insert(key)

    def display(self):
        lines, *_ = self._display_aux()
        for line in lines:
            print(line)

    def _display_aux(self):
        """Returns list of strings, width, height, and horizontal coordinate of the root."""
        # No child.
        if self.right is None and self.left is None:
            line = "%s" % self.key
            width = len(line)
            height = 1
            middle = width // 2
            return [line], width, height, middle
        # Only left child.
        if self.right is None:
            lines, n, p, x = self.left._display_aux()
            s = "%s" % self.key
            u = len(s)
            first_line = (x + 1) * " " + (n - x - 1) * "_" + s
            second_line = x * " " + "/" + (n - x - 1 + u) * " "
            shifted_lines = [line + u * " " for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2
        # Only right child.
        if self.left is None:
            lines, n, p, x = self.right._display_aux()
            s = "%s" % self.key
            u = len(s)
            first_line = s + x * "_" + (n - x) * " "
            second_line = (u + x) * " " + "\\" + (n - x - 1) * " "
            shifted_lines = [u * " " + line for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2
        # Two children.
        left, n, p, x = self.left._display_aux()
        right, m, q, y = self.right._display_aux()
        s = "%s" % self.key
        u = len(s)
        first_line = (x + 1) * " " + (n - x - 1) * "_" + s + y * "_" + (m - y) * " "
        second_line = (
            x * " " + "/" + (n - x - 1 + u + y) * " " + "\\" + (m - y - 1) * " "
        )
        if p < q:
            left += [n * " "] * (q - p)
        elif q < p:
            right += [m * " "] * (p - q)
        zipped_lines = zip(left, right)
        lines = [first_line, second_line] + [a + u * " " + b for a, b in zipped_lines]
        return lines, n + m + u, max(p, q) + 2, n + u // 2


b = BinaryTree(100)
for _ in range(100):
    b.insert(random.randint(50, 150))
b.display()

Ausgang:

Die Ausgabe des Codes ändert sich jedes Mal, wenn wir ihn ausführen. Dies liegt daran, dass wir das random-Modul von Python verwenden.

Wir hoffen, dass Sie diesen Artikel hilfreich finden, um zu verstehen, wie man einen Binärbaum mit Python druckt.