Drucken Sie den Binärbaum in Python

Stellen Sie jeden Knoten mit einem Wert und Verweisen auf sein linkes und rechtes Kind dar. Geben Sie diese Verknüpfungen anschließend rekursiv mit Verzweigungszeichen aus. Diese Anleitung erstellt einen kleinen Baum, erläutert gängige Traversierungsreihenfolgen und zeigt, wie sich ein größerer binärer Suchbaum (BST) ausgeben lässt.

Was ist ein binärer Baum?

Ein binärer Baum ist eine Struktur, in der jeder Knoten höchstens zwei Kinder hat, die üblicherweise linkes und rechtes Kind heißen. Der oberste Knoten ist die Wurzel. Ein Knoten ohne Kinder ist ein Blatt. Anders als eine Liste kann sich ein Baum verzweigen. Eine Textausgabe macht daher die Beziehungen zwischen Eltern- und Kindknoten leichter erkennbar.

Ein binärer Baum muss nicht sortiert sein. Ein binärer Suchbaum ist eine besondere Art binärer Baum: Werte, die kleiner als der Wert eines Knotens sind, kommen in dessen linken Teilbaum; größere Werte kommen in den rechten. Sind alle Werte verschieden, gibt eine In-Order-Traversierung sie dadurch in sortierter Reihenfolge aus.

Einen binären Baum mit Python erstellen

Eine Knotenklasse kann den Wert speichern und beide Kindverweise zunächst auf None setzen. Erstellen Sie Knoten und verknüpfen Sie sie, indem Sie diesen Verweisen Werte zuweisen. Die Verknüpfungen sollten nach unten zeigen: Verweist ein Kind zurück auf seinen Elternknoten, entsteht ein Zyklus, den eine rekursive Traversierung immer wieder durchlaufen würde.

Eine Traversierungsreihenfolge wählen

Eine Traversierung legt fest, wann ein Knoten im Verhältnis zu seinen Kindern besucht wird. Bei In-Order werden zuerst das linke Kind, dann der Knoten und anschließend das rechte Kind besucht; bei Pre-Order zuerst der Knoten, dann das linke und schließlich das rechte Kind; bei Post-Order zuerst das linke und das rechte Kind und zuletzt der Knoten. Jede dieser Reihenfolgen besucht jeden erreichbaren Knoten genau einmal. Für diese Aufgabe ist keine Reihenfolge grundsätzlich effizienter als eine andere. Die Reihenfolge ändert die Folge der Werte, nicht den Baum selbst. In-Order eignet sich, um einen BST sortiert auszulesen; bei Pre-Order wird die Wurzel zuerst besucht, bei Post-Order zuletzt.

Einen binären Baum mit Python ausgeben

Die folgende Funktion gibt die Wurzel aus und kennzeichnet rekursiv jeden Kindzweig. Das Präfix übernimmt die senkrechten Verzweigungszeichen aus den vorherigen Ebenen. Führen Sie dieses Beispiel aus:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

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


def print_tree(node, prefix="", is_last=True, position=None):
    if node is None:
        return
    connector = "└── " if is_last else "├── "
    position_label = f"{position} child: " if position else ""
    print(prefix + connector + position_label + str(node.value))
    children = [("left", node.left), ("right", node.right)]
    children = [(side, child) for side, child in children if child is not None]
    for index, (side, child) in enumerate(children):
        next_prefix = prefix + ("    " if is_last else "│   ")
        child_position = side if len(children) == 1 else None
        print_tree(child, next_prefix, index == len(children) - 1, child_position)


root = Node(1)
root.left = Node(2)
root.right = Node(3)
print_tree(root)

└── 1
    ├── 2
    └── 3

Die Ausgabe zeigt die Wurzel 1 mit dem linken Kind 2 und dem rechten Kind 3. Hat ein Knoten nur ein Kind, kennzeichnet die Beschriftung dieses Zweigs mit left child oder right child, ob es das linke oder rechte Kind ist. Das fehlende Kind wird zwar vor der Nummerierung der Zweige herausgefiltert, doch dadurch kann ein rechtes Kind nicht als linkes erscheinen. Wenn Sie die Funktion anpassen, behalten Sie das Präfix für jede Ebene bei, damit die Verbindungszeichen an den Knoten ausgerichtet bleiben.

Einen binären Suchbaum ausgeben

Durch Einfügen von Werten lässt sich ein größerer BST aufbauen. Dieses Beispiel ignoriert doppelte Werte und verwendet zufällige Ganzzahlen. Daher können die Baumform und die Textausgabe bei jedem Durchlauf anders ausfallen. Die Einfügeregel ordnet kleinere Werte links und größere Werte rechts ein. Eine zufällige Einfügereihenfolge kann außerdem einen unausgeglichenen Baum ergeben; dieses einfache Beispiel gleicht ihn nicht aus.

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

import random


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

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

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

    def _display_aux(self):
        """Return the printable lines, width, height, and root position."""
        if self.left is None and self.right is None:
            line = str(self.key)
            width = len(line)
            return [line], width, 1, width // 2
        if self.right is None:
            lines, width, height, x = self.left._display_aux()
            label = str(self.key)
            label_width = len(label)
            first = (x + 1) * " " + (width - x - 1) * "_" + label
            second = x * " " + "/" + (width - x - 1 + label_width) * " "
            shifted = [line + label_width * " " for line in lines]
            return [first, second] + shifted, width + label_width, height + 2, width + label_width // 2
        if self.left is None:
            lines, width, height, x = self.right._display_aux()
            label = str(self.key)
            label_width = len(label)
            first = label + x * "_" + (width - x) * " "
            second = (label_width + x) * " " + "\\" + (width - x - 1) * " "
            shifted = [label_width * " " + line for line in lines]
            return [first, second] + shifted, width + label_width, height + 2, label_width // 2
        left, left_width, left_height, x = self.left._display_aux()
        right, right_width, right_height, y = self.right._display_aux()
        label = str(self.key)
        label_width = len(label)
        first = (
            (x + 1) * " " + (left_width - x - 1) * "_" + label
            + y * "_" + (right_width - y) * " "
        )
        second = (
            x * " " + "/" + (left_width - x - 1 + label_width + y) * " "
            + "\\" + (right_width - y - 1) * " "
        )
        if left_height < right_height:
            left += [left_width * " "] * (right_height - left_height)
        elif right_height < left_height:
            right += [right_width * " "] * (left_height - right_height)
        lines = [first, second] + [a + label_width * " " + b for a, b in zip(left, right)]
        return (
            lines,
            left_width + right_width + label_width,
            max(left_height, right_height) + 2,
            left_width + label_width // 2,
        )


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

Die bereitgestellte Abbildung zeigt einen möglichen ausgegebenen Baum mit Werten aus diesem Bereich: Die Wurzel ist 100, und die Zweige veranschaulichen die Beziehungen zwischen den eingefügten Werten. Sie zeigt eine mögliche Form des Beispiels mit zufälliger Einfügereihenfolge, nicht eine feste Ausgabe für jeden Durchlauf.