Un arbore binar este o structură ierarhică în care fiecare nod are cel mult doi copii, numiți left și . Are o singură ; nodurile fără copii sunt . Este baza pentru BSTs, heaps și arbori de expresii.
Un arbore binar este o structură ierarhică în care fiecare nod are cel mult doi copii, numiți left și . Are o singură ; nodurile fără copii sunt . Este baza pentru BSTs, heaps și arbori de expresii.
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)
O parcurgere level-order (BFS) folosește o coadă și vizitează în profunzime după profunzime.
| Parcurgere | Ordine | Utilizare comună |
|---|---|---|
| Inorder | L, N, R | ieșire sortată a unui BST |
| Preorder | N, L, R | copiere/serializare arbore |
| Postorder | L, R, N | ștergere arbore, evaluare expresie |
| Level-order | după profunzime | BFS, cea mai scurtă cale în arbore |
Fiecare parcurgere vizitează fiecare nod o singură dată → O(n) timp, O(h) spațiu stack unde h este înălțimea arborelui.
Arbori binari modelează în mod natural date ierarhice (sisteme de fișiere, arbori de analiză, arbori decizionali) și sunt baza structurilor eficiente de căutare și sortare.
Stapânirea celor patru parcurgeri este esențială — majoritatea problemelor de interviu cu arbori sunt o variație a uneia dintre ele.