Et binært tre er en hierarkisk struktur der hver node har maksimalt to barn, kalt left og . Det har én enkelt ; noder uten barn er . Det er grunnlaget for BSTs, heaps og uttrykkstre.
Et binært tre er en hierarkisk struktur der hver node har maksimalt to barn, kalt left og . Det har én enkelt ; noder uten barn er . Det er grunnlaget for BSTs, heaps og uttrykkstre.
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)
En level-order (BFS) traversering bruker en kø og besøker dybde for dybde.
| Traversering | Rekkefølge | Vanlig bruk |
|---|---|---|
| Inorder | L, N, R | sortert utgang fra et BST |
| Preorder | N, L, R | kopiere/serialisere et tre |
| Postorder | L, R, N | slette et tre, evaluere uttrykk |
| Level-order | etter dybde | BFS, korteste vei i tre |
Hver traversering besøker hver node én gang → O(n) tid, O(h) stack-plass der h er høyden på treet.
Binære trær modellerer naturlig hierarkiske data (filsystemer, parse-trær, beslutningstrær) og er grunnlaget for effektive søk- og sorteringsstrukturer.
Å beherske de fire traverseringene er essensielt — de fleste trær-intervjuspørsmål er en variant av en av dem.