61 lines
3.0 KiB
Python
61 lines
3.0 KiB
Python
import sys
|
||
import os
|
||
sys.path.insert(0, os.path.join(os.path.dirname(os.path.abspath(__file__)), '..', '..'))
|
||
|
||
from utils.algo_context import AlgoContext
|
||
from utils.algo_array import Array
|
||
from vorlesung.L05_binaere_baeume.bin_tree import BinaryTree
|
||
|
||
ctx = AlgoContext()
|
||
values = Array.from_file('data/seq0.txt', ctx)
|
||
tree = BinaryTree(ctx)
|
||
for cell in values:
|
||
tree.insert(cell.value)
|
||
|
||
# ── in_order_traversal ───────────────────────────────────────────────────────
|
||
print("In-Order:")
|
||
tree.in_order_traversal(lambda node: print(node.value, end=" "))
|
||
print()
|
||
# Ausgabe: -87 -77 -59 -50 14 15 34 46 47 48 50 51 52 58
|
||
#
|
||
# Warum sortiert?
|
||
# Die BST-Eigenschaft garantiert: linker Teilbaum < Wurzel < rechter Teilbaum.
|
||
# In-Order besucht genau in dieser Reihenfolge (links → Wurzel → rechts),
|
||
# was rekursiv angewendet eine aufsteigende Sortierung ergibt.
|
||
# In-Order-Traversal eines BST entspricht damit einer Sortierung der Schlüssel.
|
||
|
||
# ── level_order_traversal ────────────────────────────────────────────────────
|
||
print("\nLevel-Order:")
|
||
tree.level_order_traversal(lambda node, level: print(f"Ebene {level}: {node.value}"))
|
||
# Ausgabe: Wurzel zuerst, dann alle Knoten der Ebene 1, dann Ebene 2, …
|
||
#
|
||
# Was zeigt level_order, was in_order nicht zeigt?
|
||
# level_order_traversal entspricht einer Breitensuche (BFS). Sie zeigt,
|
||
# auf welcher Tiefenebene sich jeder Knoten befindet, und damit die
|
||
# tatsächliche Struktur des Baums – nicht nur die sortierte Schlüsselfolge.
|
||
# Zwei BSTs mit denselben Schlüsseln liefern identische in_order-Ausgaben,
|
||
# aber unterschiedliche level_order-Ausgaben, wenn ihre Struktur verschieden ist.
|
||
|
||
# ── graph_traversal ──────────────────────────────────────────────────────────
|
||
# Relevante Stelle in bin_tree.py:
|
||
#
|
||
# def graph_traversal(self):
|
||
# def define_node(node, level, line):
|
||
# node.graphviz_rep(level, line, dot) ← Knoten positionieren
|
||
# ...
|
||
# self.tree_structure_traversal(define_node) ← Traversierung
|
||
# _rec(self.root) ← Kanten eintragen
|
||
#
|
||
# graph_traversal nutzt intern tree_structure_traversal – eine In-Order-
|
||
# Traversal, die zusätzlich zu jedem Knoten seine Tiefe (level) und seine
|
||
# In-Order-Position (line) mitliefert.
|
||
#
|
||
# level → y-Koordinate im Graphviz-Layout: je tiefer im Baum, desto weiter
|
||
# unten in der Abbildung (negiert: pos=f"{col},{-row}!")
|
||
# line → x-Koordinate: die In-Order-Position ergibt automatisch eine
|
||
# kollisionsfreie horizontale Anordnung ohne überlappende Knoten.
|
||
#
|
||
# tree_structure_traversal existiert also nicht als eigenständige Ausgabe-
|
||
# Traversal, sondern als Hilfsmittel für die Positionsberechnung in graph_traversal.
|
||
# Die Traversierungsreihenfolge ist identisch mit in_order_traversal.
|