Ağacın Tüm Elemanlarını Ziyaret Etme Yöntemleri
Ağaç üzerinde dolaşma (traversal), tüm düğümleri belirli bir sırayla ziyaret etme işlemidir. Dört temel yöntem vardır:
Sol → Kök → Sağ
Kök → Sol → Sağ
Sol → Sağ → Kök
Seviye seviye (BFS)
Bir ağaçtaki tüm düğümleri belirli bir sırayla ziyaret etmeye traversal (dolaşma) denir. Peki neden birden fazla yöntem var?
Her traversal yöntemi farklı bir problemi çözmek için optimize edilmiştir:
Tüm traversal örneklerinde bu ağacı kullanacağız:
Her traversal yöntemi aynı kalıbı izler. Recursive fonksiyon şu yapıya sahiptir:
Tek fark: "print" (kökü işle) satırının nerede olduğu!
Recursion'u anlamak için inorder traversal'ı adım adım takip edelim:
BST'de sol alt ağaçtaki tüm değerler kökten küçük, sağ alt ağaçtaki tüm değerler kökten büyük. Inorder ile önce sol (küçükler), sonra kök, sonra sağ (büyükler) ziyaret edilir → Sonuç sıralı!
LNR: Left → Node → Right
"Önce solumu bitireyim, sonra kendimi söyleyeyim, en son sağımı halledeyim."
Sonuç:
✨ BST için inorder = SIRALI çıktı! (Küçükten büyüğe)
BST → Array
Sıralı mı kontrol
Sırada k. eleman
NLR: Node → Left → Right
"Önce kendimi söyleyeyim, sonra sol tarafa gideyim, en son sağ tarafa bakayım."
Sonuç:
✨ Kök her zaman İLK! Ağacı kopyalamak/serialize etmek için ideal.
Clone işlemleri
Klasör yapısı
JSON, XML export
LRN: Left → Right → Node
"Önce solumu hallettim, sonra sağımı hallettim, artık kendimi söyleyebilirim."
Sonuç:
✨ Kök her zaman SON! Ağacı silmek için ideal (önce çocukları sil).
Çocuklar önce silinir
Postfix hesaplama
Alt ağaç boyutları
Seviye seviye, soldan sağa
"Yukarıdan aşağıya, soldan sağa, seviye seviye gidiyorum."
Bu yöntem recursive değil, iteratif! Queue (FIFO) veri yapısı kullanır.
Sonuç:
✨ Her seviye sırayla! En kısa yol bulma, seviye sayma için ideal.
BFS garantisi
Seviye sayısı
Katman katman
Bir traversal yöntemi seçin ve adım adım izleyin. Her adımda hangi düğümün ziyaret edildiğini ve call stack'in durumunu görün.
from collections import deque
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, data):
if not self.root:
self.root = Node(data)
return
c = self.root
while True:
if data < c.data:
if not c.left: c.left = Node(data); return
c = c.left
else:
if not c.right: c.right = Node(data); return
c = c.right
# ===== TRAVERSAL METODLARI =====
def inorder(self, node=None, result=None):
"""Sol → Kök → Sağ (Sıralı çıktı)"""
if result is None: result = []
if node is None: node = self.root
if node:
self.inorder(node.left, result) # Sol
result.append(node.data) # Kök
self.inorder(node.right, result) # Sağ
return result
def preorder(self, node=None, result=None):
"""Kök → Sol → Sağ"""
if result is None: result = []
if node is None: node = self.root
if node:
result.append(node.data) # Kök
self.preorder(node.left, result) # Sol
self.preorder(node.right, result) # Sağ
return result
def postorder(self, node=None, result=None):
"""Sol → Sağ → Kök"""
if result is None: result = []
if node is None: node = self.root
if node:
self.postorder(node.left, result) # Sol
self.postorder(node.right, result) # Sağ
result.append(node.data) # Kök
return result
def level_order(self):
"""BFS ile seviye seviye dolaşma"""
if not self.root:
return []
result = []
queue = deque([self.root])
while queue:
node = queue.popleft() # FIFO
result.append(node.data)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# Test
bst = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
bst.insert(v)
print("🌳 Ağaç: 50 → (30, 70) → (20, 40, 60, 80)")
print()
print("=" * 50)
print("📋 TRAVERSAL SONUÇLARI")
print("=" * 50)
print()
print(f"📋 Inorder (LNR): {bst.inorder()}")
print(f" → Sıralı çıktı verir!")
print()
print(f"📦 Preorder (NLR): {bst.preorder()}")
print(f" → Kök başta, kopyalama için")
print()
print(f"🗑️ Postorder(LRN): {bst.postorder()}")
print(f" → Kök sonda, silme için")
print()
print(f"📊 Level Order: {bst.level_order()}")
print(f" → Seviye seviye, BFS")Traversal kodlarını anlamadan önce, recursion'ın nasıl çalıştığını anlamak çok önemli. Hadi adım adım bakalım!
Bir fonksiyonun kendini çağırmasına recursion denir. Ama nasıl çalışıyor?
Düşün ki bir aynaya bakıyorsun ve arkanda da bir ayna var. Sonsuz yansıma görürsün, değil mi? Recursion da böyle - ama bir durma noktası (base case) olmalı!
Bilgisayar, fonksiyon çağrılarını takip etmek için call stack (çağrı yığını) adlı bir yapı kullanır. Bu, tam olarak bir tabak yığını gibi çalışır:
Önce çok basit bir örnekle başlayalım:
Recursion'ın durma noktası. Olmazsa sonsuz döngü → Stack Overflow!
Fonksiyonun kendini çağırdığı kısım. Her çağrıda problem küçülmeli!
Bekleyen fonksiyonların tutulduğu yer. Her çağrı stack'e eklenir.
Şimdi basit bir ağaçla inorder traversal'ı adım adım takip edelim:
Sadece 3 düğüm: 2, 1, 3
Bir algoritmanın space complexity'si, çalışırken ne kadar ek bellek kullandığını gösterir.
Traversal'da space complexity O(h)'dir. Burada:
Neden O(n) değil? Çünkü call stack'te aynı anda en fazla h tane fonksiyon bekler!
7 düğüm var ama stack derinliği sadece 3!
7 düğüm ve stack derinliği de 7!
Her programın kullanabileceği stack belleği sınırlıdır:
Eğer ağaç çok derin olursa ve bu limiti aşarsak → Stack Overflow Error!
Recursive kod yazmak kolay ve okunabilir. Ama arka planda neler oluyor?
Bir fonksiyon çağrıldığında, bilgisayar şu bilgileri stack'e kaydeder:
Fonksiyon bitince nereye dönecek?
Fonksiyona gönderilen değerler (node, vb.)
Fonksiyon içindeki tüm değişkenler
Önceki fonksiyonun durumu
Her fonksiyon çağrısı yaklaşık 50-100 byte bellek kullanır. 1000 düğümlü dengesiz ağaçta:
Bu çok fazla değil gibi görünebilir, ama Python'un varsayılan limiti 1000 çağrı! Ve her çağrıda ek işlem süresi de harcanır.
Python varsayılan olarak ~1000 recursive çağrıya izin verir:
# Limiti görmek için: import sys print(sys.getrecursionlimit()) # Çıktı: 1000 # Limiti artırmak için (DİKKATLİ!): sys.setrecursionlimit(10000) # Tehlikeli olabilir!
⚠️ Uyarı: Limiti artırmak Stack Overflow yerine programın çökmesine neden olabilir. Derin ağaçlar için iterative çözüm daha güvenli!
Recursive traversal'lar sistem stack'ini kullanır. Peki ya kendi stack'imizi oluştursak? İşte iterative traversal'ın mantığı bu!
Recursive çağrı yerine:
append() ile stack'e ekliyoruz (push)pop() ile stack'ten çıkarıyoruzDerin ağaçlarda bile güvenli
Fonksiyon çağrı maliyeti yok
İstediğimiz yerde durabiliriz
Stack boyutunu biz kontrol ederiz
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, data):
if not self.root:
self.root = Node(data)
return
c = self.root
while True:
if data < c.data:
if not c.left: c.left = Node(data); return
c = c.left
else:
if not c.right: c.right = Node(data); return
c = c.right
# ========== ITERATIVE TRAVERSAL ==========
def inorder_iterative(self):
"""
Iterative Inorder: Stack kullanarak Sol → Kök → Sağ
Mantık:
1. Mümkün olduğunca sola git, yolda herkesi stack'e at
2. Stack'ten çıkar, değerini al
3. Sağ çocuğa geç, tekrarla
"""
result = []
stack = []
current = self.root
while stack or current:
# Sol tarafa git, yolda herkesi stack'e at
while current:
stack.append(current)
current = current.left
# Stack'ten çıkar (en soldaki)
current = stack.pop()
result.append(current.data) # ZİYARET
# Sağ tarafa geç
current = current.right
return result
def preorder_iterative(self):
"""
Iterative Preorder: Stack kullanarak Kök → Sol → Sağ
Mantık:
1. Kökü stack'e at
2. Stack'ten çıkar, ziyaret et
3. ÖNCE sağı, SONRA solu stack'e at (LIFO olduğu için sol önce çıkar)
"""
if not self.root:
return []
result = []
stack = [self.root]
while stack:
node = stack.pop()
result.append(node.data) # ZİYARET
# Sağı önce at (sonra çıksın)
if node.right:
stack.append(node.right)
# Solu sonra at (önce çıksın)
if node.left:
stack.append(node.left)
return result
def postorder_iterative(self):
"""
Iterative Postorder: İki stack veya ters preorder
Mantık (Ters Preorder yöntemi):
1. Preorder: Kök → Sol → Sağ
2. Değiştirilmiş: Kök → Sağ → Sol
3. Sonucu ters çevir: Sol → Sağ → Kök = Postorder!
"""
if not self.root:
return []
result = []
stack = [self.root]
while stack:
node = stack.pop()
result.append(node.data)
# Solu önce at (sonra çıksın)
if node.left:
stack.append(node.left)
# Sağı sonra at (önce çıksın)
if node.right:
stack.append(node.right)
# Ters çevir: Kök→Sağ→Sol --> Sol→Sağ→Kök
return result[::-1]
def postorder_iterative_2stack(self):
"""
İki Stack ile Postorder (daha anlaşılır versiyon)
"""
if not self.root:
return []
stack1 = [self.root]
stack2 = []
while stack1:
node = stack1.pop()
stack2.append(node.data)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
# stack2'yi ters çevir
return stack2[::-1]
# ========== TEST ==========
bst = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
bst.insert(v)
print("🌳 Ağaç: 50 → (30, 70) → (20, 40, 60, 80)")
print()
print("=" * 55)
print("🔄 ITERATIVE TRAVERSAL SONUÇLARI")
print("=" * 55)
print()
print(f"📋 Inorder Iterative: {bst.inorder_iterative()}")
print(f"📦 Preorder Iterative: {bst.preorder_iterative()}")
print(f"🗑️ Postorder Iterative: {bst.postorder_iterative()}")
print(f"🗑️ Postorder 2-Stack: {bst.postorder_iterative_2stack()}")
print()
print("💡 Tüm sonuçlar recursive versiyonlarla aynı!")Anahtar: "Sola git, çıkarken ziyaret et, sağa dön"
Anahtar: "Çıkarınca ziyaret et, sağı önce at (LIFO)"
Anahtar: "Ters preorder + reverse = postorder"