fabejárás
A fabejárás (tree traversal) a fák adatszerkezetének bejárására szolgáló módszerek összessége. A fabejárási algoritmusok célja, hogy egy fa minden csomópontját meghatározott sorrendben látogassák meg. Ez lehetővé teszi a fa adatszerkezetének különböző feldolgozásait.
Először definiáljunk egy egyszerű bináris fát Pythonban:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# Példa fa:
# 1
# / \
# 2 3
# / \
# 4 5
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
def preorder(node):
if node:
print(node.value, end=" ")
preorder(node.left)
preorder(node.right)
# Példa használat
print("Preorder bejárás:")
preorder(root)
Preorder bejárás: 1 2 4 5 3
def inorder(node):
if node:
inorder(node.left)
print(node.value, end=" ")
inorder(node.right)
# Példa használat
print("\nInorder bejárás:")
inorder(root)
Inorder bejárás: 4 2 5 1 3
def postorder(node):
if node:
postorder(node.left)
postorder(node.right)
print(node.value, end=" ")
# Példa használat
print("\nPostorder bejárás:")
postorder(root)
Postorder bejárás: 4 5 2 3 1
Szélességi bejáráshoz általában egy sor (queue) használata szükséges.
from collections import deque
def breadth_first_search(root):
if not root:
return
queue = deque()
while queue:
current = queue.popleft()
print(current.value, end=" ")
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
# Példa használat
print("\nSzélességi bejárás:")
breadth_first_search(root)
Szélességi bejárás: 1 2 3 4 5
Az iteratív mélységi bejárás elkerüli a rekurziót, és verem (stack) segítségével működik.
def iterative_preorder(node):
if not node:
return
stack =
while stack:
current = stack.pop()
print(current.value, end=" ")
if current.right: # Jobb gyerek előbb, mert a bal kerül felülre
stack.append(current.right)
if current.left:
stack.append(current.left)
# Példa használat
print("\nIteratív preorder bejárás:")
iterative_preorder(root)
Iteratív preorder bejárás: 1 2 4 5 3
def iterative_inorder(node):
stack =
current = node
while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
print(current.value, end=" ")
current = current.right
# Példa használat
print("\nIteratív inorder bejárás:")
iterative_inorder(root)
Iteratív inorder bejárás: 4 2 5 1 3
| Bejárás típusa | Sorrend | Implementáció |
|---|---|---|
| Preorder | Gyökér → Bal → Jobb | Rekurzív/Iteratív |
| Inorder | Bal → Gyökér → Jobb | Rekurzív/Iteratív |
| Postorder | Bal → Jobb → Gyökér | Rekurzív |
| Szélességi bejárás | Szintenként halad | Queue alapú |
A fabejárási algoritmusok sokféle adatszerkezeti és algoritmikus problémára alkalmazhatók, mint például bináris keresőfák (BST), gráfok bejárása, és rendezési műveletek.