Sebuah pohon biner adalah struktur hierarki di mana setiap simpul memiliki paling banyak dua anak, disebut left dan . Pohon memiliki satu tunggal; simpul tanpa anak disebut . Pohon biner adalah dasar dari BST, heap, dan pohon ekspresi.
Sebuah pohon biner adalah struktur hierarki di mana setiap simpul memiliki paling banyak dua anak, disebut left dan . Pohon memiliki satu tunggal; simpul tanpa anak disebut . Pohon biner adalah dasar dari BST, heap, dan pohon ekspresi.
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)
Penelusuran level-order (BFS) menggunakan antrian dan mengunjungi simpul berdasarkan kedalaman.
| Penelusuran | Urutan | Penggunaan umum |
|---|---|---|
| Inorder | L, N, R | keluaran terurut dari BST |
| Preorder | N, L, R | salin/serialisasi pohon |
| Postorder | L, R, N | hapus pohon, evaluasi ekspresi |
| Level-order | menurut kedalaman | BFS, jalur terpendek pada pohon |
Setiap penelusuran mengunjungi setiap simpul sekali → waktu O(n), ruang stack O(h) di mana h adalah tinggi pohon.
Pohon biner secara alami memodelkan data hierarki (sistem file, pohon parse, pohon keputusan) dan mendasari struktur pencarian dan pengurutan yang efisien.
Menguasai keempat jenis penelusuran sangat penting — sebagian besar masalah wawancara pohon adalah variasi dari salah satunya.