fabejárás
Kiejtés
- IPA: [ ˈfɒbɛjaːraːʃ]
Főnév
fabejárás
Fabejárás és algoritmusok
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.
Típusai
- Mélységi bejárás (Depth-First Traversal):
- Preorder: Gyökér → Bal → Jobb
- Inorder: Bal → Gyökér → Jobb
- Postorder: Bal → Jobb → Gyökér
- Szélességi bejárás (Breadth-First Traversal):
- Szintenként halad a fa csomópontjain.
Példák Pythonban
1. Fa szerkezete
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)
2. Mélységi bejárás (DFS)
Preorder (Gyökér → Bal → Jobb)
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)
Kimenet:
Preorder bejárás: 1 2 4 5 3
Inorder (Bal → Gyökér → Jobb)
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)
Kimenet:
Inorder bejárás: 4 2 5 1 3
Postorder (Bal → Jobb → Gyökér)
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)
Kimenet:
Postorder bejárás: 4 5 2 3 1
3. Szélességi bejárás (BFS)
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([root])
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)
Kimenet:
Szélességi bejárás: 1 2 3 4 5
Optimalizált algoritmusok
1. Iteratív mélységi bejárás
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 = [node]
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)
Kimenet:
Iteratív preorder bejárás: 1 2 4 5 3
2. Rekurzió nélküli inorder
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)
Kimenet:
Iteratív inorder bejárás: 4 2 5 1 3
Összegzés
| 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.
Fordítások
Tartalom