Darstellung binärer Bäume
Binäre Bäume sind eine grundlegende Datenstruktur, die in der Informatik häufig zum Einsatz kommt. Sie eignen sich besonders gut, um effiziente Algorithmen für Aufgaben wie Suchen, Sortieren und das Durchlaufen von Daten zu entwickeln.
Binäre Bäume bestehen aus Knoten (Nodes), von denen jeder Knoten höchstens zwei Kinder haben kann – ein linkes Kind und ein rechtes Kind. Jedes dieser Kinder kann wiederum eigene linke und rechte Kinder besitzen, und so setzt sich die Struktur fort, bis keine weiteren Knoten mehr vorhanden sind.
Der oberste Knoten in einem binären Baum heißt Wurzel (Root), während die untersten Knoten, die keine Kinder mehr besitzen, als Blätter des Baums bezeichnet werden.
Diese einfache Idee ermöglicht eine sehr effiziente Darstellung vieler verschiedener Datentypen und ist in unterschiedlichen Programmiersprachen leicht umzusetzen:
class Node: # Node-Objekt mit den Daten für jeden Knoten
def __init__(self, value): # Der Wert, den jeder Knoten speichern soll (kann beliebig sein)
self.left = None # Anfänglich sind sowohl left als auch right None
self.right = None
self.value = value
# Erstelle alle Knoten manuell
root = Node(1)
root.left, root.right = Node(2), Node(3)
root.left.left, root.left.right = Node(4), Node(5)
root.left.right.left, root.left.right.right = Node(7), Node(8)
root.right.right = Node(6)
# Anschließend können wir den gesamten Binärbaum rekursiv durchlaufen
# Lass uns die Summe aller Knoten berechnen
def treesum(node: Node | None) -> int:
if node is None:
return 0
# Gib die Summe des linken Teilbaums, des rechten Teilbaums und des aktuellen Knotens zurück
return treesum(node.left) + treesum(node.right) + node.value
print(treesum(root)) # Gibt 36 ausIn diesem Beispiel durchlaufen wir alle Knoten ausgehend von der
root. Ist der aktuelle Knoten None, bedeutet dies, dass wir das Ende des Teilbaums auf diesem Pfad erreicht haben und wir können 0 als Summe zurückgeben. Andernfalls berechnen wir die Summe des linken Teilbaums, des rechten Teilbaums und des aktuellen Knotens und addieren alles zusammen.Aufgabe: Einen Binärbaum manuell erstellen
Angenommen, Sie möchten den im Bild gezeigten binären Baum manuell erstellen.
Schreiben Sie Code, der diesen Binärbaum erzeugt. Sie müssen nichts ausgeben. Dieser Teil wird automatisch übernommen.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB