Drzewo binarne to hierarchiczna struktura, w której każdy węzeł ma co najwyżej dwoje dzieci, zwanych left i right. Ma jeden pojedynczy ; węzły bez dzieci to . Jest podstawą BST, kopców i drzew wyrażeń.
Drzewo binarne to hierarchiczna struktura, w której każdy węzeł ma co najwyżej dwoje dzieci, zwanych left i right. Ma jeden pojedynczy ; węzły bez dzieci to . Jest podstawą BST, kopców i drzew wyrażeń.
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)
Przechodzenie level-order (BFS) używa kolejki i odwiedza wierzchołki głębokość po głębokości.
| Przechodzenie | Porządek | Zastosowanie |
|---|---|---|
| Inorder | L, N, R | posortowane wyjście BST |
| Preorder | N, L, R | kopiowanie/serializacja drzewa |
| Postorder | L, R, N | usuwanie drzewa, ewaluacja wyrażenia |
| Level-order | według głębokości | BFS, najkrótsza ścieżka w drzewie |
Każde przechodzenie odwiedza każdy węzeł jeden raz → O(n) czasu, O(h) pamięci stosu gdzie h to wysokość drzewa.
Drzewa binarne modelują naturalnie dane hierarchiczne (systemy plików, parse trees, drzewa decyzyjne) i stanowią podstawę efektywnych struktur wyszukiwania i sortowania.
Opanowanie czterech przechodzień jest niezbędne — większość zadań z rozmów o drzewach to warianty jednego z nich.