Un albero binario è una struttura gerarchica dove ogni nodo ha al massimo due figli, chiamati left e . Ha una singola ; i nodi senza figli sono . È la base per BST, heap e alberi di espressione.
Un albero binario è una struttura gerarchica dove ogni nodo ha al massimo due figli, chiamati left e . Ha una singola ; i nodi senza figli sono . È la base per BST, heap e alberi di espressione.
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)
Un attraversamento level-order (BFS) utilizza una coda e visita profondità per profondità.
| Attraversamento | Ordine | Uso comune |
|---|---|---|
| Inorder | L, N, R | output ordinato di un BST |
| Preorder | N, L, R | copia/serializzazione di un albero |
| Postorder | L, R, N | eliminazione di un albero, valutazione expr |
| Level-order | per profondità | BFS, cammino più breve in albero |
Ogni attraversamento visita ogni nodo una volta → tempo O(n), spazio stack O(h) dove h è l'altezza.
Gli alberi binari modellano naturalmente dati gerarchici (file system, alberi di parse, alberi decisionali) e sono alla base di strutture di ricerca e ordinamento efficienti.
Padroneggiare i quattro attraversamenti è essenziale — la maggior parte dei problemi di intervista su alberi è una variazione di uno di essi.