A Reingold-Tilford-algoritmus egy bináris fák rajzolására szolgáló hatékony algoritmus, amely a fa csomópontjait úgy helyezi el egy kétdimenziós síkon, hogy a fa szerkezete vizuálisan tiszta és jól áttekinthető legyen. Az algoritmus fő célja:
Adott egy bináris fa:
A
/ \
B C
/ \
D E
Az algoritmus az alábbi módon rendezi el a csomópontokat:
Az alábbi implementáció egy egyszerű bináris fa elhelyezését mutatja be Reingold-Tilford módszerrel:
class Node:
"""Bináris fa csomópont osztálya."""
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.x = 0 # X koordináta
self.y = 0 # Y koordináta
def add_offsets(left, right, offset):
"""A jobb részfát eltolja a megadott távolságra."""
while left and right:
left.x += offset
if left.right:
left = left.right
if right.left:
right = right.left
offset += 1
def reingold_tilford(root, depth=0):
"""
Reingold-Tilford algoritmus a fa elrendezésére.
:param root: A bináris fa gyökere.
:param depth: Az aktuális mélység.
"""
if root is None:
return
# Rekurzív elrendezés a részfákra
reingold_tilford(root.left, depth + 1)
reingold_tilford(root.right, depth + 1)
# Szomszédos részfák közötti távolság
if root.left:
root.left.x = root.x - 1
if root.right:
root.right.x = root.x + 1
# Középre helyezés
if root.left and root.right:
root.x = (root.left.x + root.right.x) // 2
add_offsets(root.left, root.right, 1)
root.y = depth
def print_tree(root):
"""A fa csomópontjainak koordinátáit kiírja."""
if root is not None:
print(f"{root.key}: ({root.x}, {root.y})")
print_tree(root.left)
print_tree(root.right)
# Bináris fa létrehozása
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.right.right = Node('E')
# Algoritmus futtatása
reingold_tilford(root)
# Eredmények kiírása
print("Csomópontok koordinátái:")
print_tree(root)
Az elhelyezés a következőképpen fog kinézni:
Csomópontok koordinátái: A: (0, 0) B: (-1, 1) C: (1, 1) D: (-2, 2) E: (2, 2)
Ez azt jelenti, hogy: - A gyökér csomópont (A) az origónál ((0, 0)) helyezkedik el. - A bal részfa csomópontjai balra, a jobb részfa csomópontjai pedig jobbra kerülnek, a szintek szerint függőlegesen elrendezve.
Az algoritmus által generált vizuális ábra:
A(0,0)
/ \
B(-1,1) C(1,1)
/ \
D(-2,2) E(2,2)
A Reingold-Tilford algoritmus tehát ideális választás a bináris keresőfák tiszta és szimmetrikus megjelenítésére.