A bináris fa egy hierarchikus struktúra, ahol minden csomópontnak legfeljebb két gyermeke van, amelyeket left és néven hívunk. Egyetlen van; a gyermek nélküli csomópontok a . Ez az alapja a BST-eknek, a kupacoknak és a kifejezésfáknak.
A bináris fa egy hierarchikus struktúra, ahol minden csomópontnak legfeljebb két gyermeke van, amelyeket left és néven hívunk. Egyetlen van; a gyermek nélküli csomópontok a . Ez az alapja a BST-eknek, a kupacoknak és a kifejezésfáknak.
right 1 depth 0 (root)
/ \
2 3 depth 1
/ \
4 5 depth 2 (leaves: 4,5,3)
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def inorder(n): # left, node, right -> 4 2 5 1 3
if n:
inorder(n.left); print(n.val); inorder(n.right)
def preorder(n): # node, left, right -> 1 2 4 5 3
if n:
print(n.val); preorder(n.left); preorder(n.right)
def postorder(n): # left, right, node -> 4 5 2 3 1
if n:
postorder(n.left); postorder(n.right); print(n.val)
A szintenkénti (BFS) bejárás egy sort használ és mélységenként látogatja meg a csomópontokat.
| Bejárás | Sorrend | Gyakori felhasználás |
|---|---|---|
| Inorder | L, N, R | BST rendezett kimenete |
| Preorder | N, L, R | fa másolása/szerializálása |
| Postorder | L, R, N | fa törlése, kifejezés kiértékelése |
| Level-order | mélység szerint | BFS, legrövidebb út a fában |
Minden bejárás minden csomópontot egyszer látogat meg → O(n) idő, O(h) verem hely, ahol h a fa magassága.
A bináris fák természetesen hierarchikus adatokat modelleznek (fájlrendszerek, elemzési fák, döntési fák), és hatékony kereső és rendezési struktúrák alapjául szolgálnak.
A négy bejárás elsajátítása elengedhetetlen — a legtöbb fafejlesztési interjúkérdés az egyik variációja.
IT interjúkérdések gyűjteménye részletes válaszokkal — Juniortól Seniorig.
Adományozás