Ağaç Gezinmeleri

Doğrusal bir yapıyı gezmenin tek bir doğal yolu vardır: baştan sona. Ağaçta ise her düğümde en az iki yön bulunur ve hangi sırayla ilerleneceği bir karardır.

Bu ders dört temel gezinme düzenini tanımlar. Dördü de her düğüme tam bir kez uğrar, dolayısıyla maliyetleri $O(n)$’dir; ayrıldıkları nokta ziyaret sırasıdır ve bu sıra, gezinmenin hangi problemi çözebileceğini belirler.

Üç Derinlik Gezinmesi

İkili ağaçta bir düğümde üç iş vardır: düğümün kendisini ziyaret etmek, sol alt ağacı gezmek, sağ alt ağacı gezmek. Düğümün ziyaretinin bu üçlü içindeki yeri, gezinmenin adını verir.

• Ön sıralı (preorder): Önce düğüm, sonra sol, sonra sağ.
• İç sıralı (inorder): Önce sol, sonra düğüm, sonra sağ.
• Son sıralı (postorder): Önce sol, sonra sağ, sonra düğüm.

Sol alt ağacın her zaman sağdan önce gezildiğine dikkat edin; üç düzen de bu ortak kuralı paylaşır.

            (12)
           /    \
       (18)      (7)
      /   \        \
   (25)   (14)     (30)

Gezinme	Sıra
Ön sıralı	12, 18, 25, 14, 7, 30
İç sıralı	25, 18, 14, 12, 7, 30
Son sıralı	25, 14, 18, 30, 7, 12

class IkiliDugum:
    def __init__(self, deger: int) -> None:
        self.deger = deger
        self.sol: "IkiliDugum | None" = None
        self.sag: "IkiliDugum | None" = None


def on_sirali(dugum, sonuc=None):
    sonuc = [] if sonuc is None else sonuc
    if dugum is not None:
        sonuc.append(dugum.deger)          # önce düğüm
        on_sirali(dugum.sol, sonuc)
        on_sirali(dugum.sag, sonuc)
    return sonuc


def ic_sirali(dugum, sonuc=None):
    sonuc = [] if sonuc is None else sonuc
    if dugum is not None:
        ic_sirali(dugum.sol, sonuc)
        sonuc.append(dugum.deger)          # ortada düğüm
        ic_sirali(dugum.sag, sonuc)
    return sonuc


def son_sirali(dugum, sonuc=None):
    sonuc = [] if sonuc is None else sonuc
    if dugum is not None:
        son_sirali(dugum.sol, sonuc)
        son_sirali(dugum.sag, sonuc)
        sonuc.append(dugum.deger)          # en son düğüm
    return sonuc


kok = IkiliDugum(12)
kok.sol = IkiliDugum(18); kok.sag = IkiliDugum(7)
kok.sol.sol = IkiliDugum(25); kok.sol.sag = IkiliDugum(14)
kok.sag.sag = IkiliDugum(30)

print(on_sirali(kok))       # [12, 18, 25, 14, 7, 30]
print(ic_sirali(kok))       # [25, 18, 14, 12, 7, 30]
print(son_sirali(kok))      # [25, 14, 18, 30, 7, 12]

Üç işlev arasındaki tek fark, append satırının konumudur. Bu, gezinme düzenlerinin neden aynı ailenin üyeleri sayıldığını gösterir.

Hangi Gezinme Nerede

Sıra farkı, problem uygunluğunu belirler.

Ön sıralı, düğümü çocuklarından önce işler. Bir yapıyı kopyalamak veya dizileştirmek için uygundur: üst düğüm oluşturulmadan alt düğümler bağlanamaz. Dizin ağacını yazdırırken önce dizinin adının, sonra içindekilerin gelmesi de bu düzendir.

İç sıralı, ikili arama ağaçlarında elemanları sıralı verir. Sonraki dersin ana sonucu budur; şimdilik yalnızca sıranın anlamlı olabildiği not edilir.

Son sıralı, düğümü çocuklarından sonra işler. Bir ağacı serbest bırakmak için zorunludur: çocuklar bırakılmadan üst düğüm bırakılırsa çocuklara erişim kaybolur. Aynı nedenle ifade değerlendirmede kullanılır — bir işlecin değeri, işlenenleri hesaplanmadan bulunamaz. Yığıtlar dersindeki son ek gösterimi, bir ifade ağacının son sıralı gezinmesidir.

Seviye sıralı, ağacı katman katman gezer ve sonraki bölümün konusudur.

Yığıtla Gezinme

Özyinelemeli yazım, çağrı yığıtını örtük olarak kullanır. Aynı gezinme, yığıt açıkça tutularak da yazılabilir; Programlama Temelleri kursundaki “yığıtı elle taşımak” dönüşümünün ağaçlardaki uygulamasıdır.

def on_sirali_yigitla(kok) -> list[int]:
    """Ön sıralı gezinme; özyineleme yerine açık yığıt."""
    if kok is None:
        return []
    sonuc, yigit = [], [kok]
    while yigit:
        dugum = yigit.pop()
        sonuc.append(dugum.deger)
        if dugum.sag is not None:
            yigit.append(dugum.sag)        # sağ önce itilir
        if dugum.sol is not None:
            yigit.append(dugum.sol)        # sol sonra: önce o çekilir
    return sonuc


print(on_sirali_yigitla(kok))    # [12, 18, 25, 14, 7, 30]

Sağ çocuğun önce itilmesi, yığıtın ters sırayla çalışmasındandır: son giren ilk çıkar, dolayısıyla sol çocuk önce işlenir. Bu ayrıntı atlandığında gezinme sağdan sola olur ve sonuç sessizce değişir.

Açık yığıt kullanmanın gerekçesi, önceki kursta belirtilenle aynıdır: derinlik veriyle büyüdüğünde çağrı yığıtı tükenebilir. Derin ağaçlarla çalışan üretim kodu bu nedenle sıklıkla açık yığıt kullanır.

Seviye Sıralı Gezinme

Dördüncü düzen, derinlik değil genişlik boyunca ilerler: önce kök, sonra derinlik 1’deki tüm düğümler, sonra derinlik 2’dekiler.

Yapısı, derinlik gezinmesinin aynısıdır; tek fark, yığıt yerine kuyruk kullanılmasıdır.

from collections import deque

def seviye_sirali(kok) -> list[int]:
    if kok is None:
        return []
    sonuc, kuyruk = [], deque([kok])
    while kuyruk:
        dugum = kuyruk.popleft()           # ilk giren ilk çıkar
        sonuc.append(dugum.deger)
        if dugum.sol is not None:
            kuyruk.append(dugum.sol)
        if dugum.sag is not None:
            kuyruk.append(dugum.sag)
    return sonuc


def seviyelere_gore(kok) -> list[list[int]]:
    """Her seviyeyi ayrı listede döndürür."""
    if kok is None:
        return []
    sonuc, kuyruk = [], deque([kok])
    while kuyruk:
        seviye = []
        for _ in range(len(kuyruk)):       # o anki kuyruk uzunluğu = seviye genişliği
            dugum = kuyruk.popleft()
            seviye.append(dugum.deger)
            if dugum.sol is not None:
                kuyruk.append(dugum.sol)
            if dugum.sag is not None:
                kuyruk.append(dugum.sag)
        sonuc.append(seviye)
    return sonuc


print(seviye_sirali(kok))        # [12, 18, 7, 25, 14, 30]
print(seviyelere_gore(kok))      # [[12], [18, 7], [25, 14, 30]]

Yığıt yerine kuyruk kullanmanın gezinme düzenini tümüyle değiştirmesi, bu iki soyut tipin neden ayrı ayrı tanımlandığını somutlaştırır. Aynı ikilik, çizgeler konusundaki derine ve enine arama arasında birebir tekrarlanacaktır.

seviyelere_gore işlevindeki döngü, kuyruğun o anki uzunluğunu okuyarak seviye sınırını belirler — yeni eklenenler bir sonraki tura kalır.

Maliyet

Gezinme, ağaç üzerinde tanımlı hemen her işlemin temelidir: düğüm sayma, yükseklik hesaplama, kopyalama, karşılaştırma ve serbest bırakma — hepsi bir gezinme düzeninin özelleşmiş hâlidir.

Dört gezinme de her düğüme bir kez uğrar: zaman maliyeti $O(n)$’dir.

Bellek maliyetleri ayrışır. Derinlik gezinmeleri yığıtta en fazla ağacın yüksekliği kadar düğüm tutar — dengeli ağaçta $O(\log n)$, dejenere ağaçta $O(n)$. Seviye sıralı gezinme ise kuyrukta en geniş seviyenin genişliği kadar düğüm tutar; kusursuz bir ağaçta bu, son seviyedeki düğüm sayısıdır, yani $O(n)$.

Geniş ve sığ ağaçlarda derinlik gezinmesi, derin ve dar ağaçlarda seviye gezinmesi daha az bellek kullanır.

Özet

• Ön, iç ve son sıralı gezinmeler yalnızca düğümün ziyaret anıyla ayrılır; üçü de sol alt ağacı sağdan önce gezer.
• Ön sıralı kopyalama ve dizileştirmeye, son sıralı serbest bırakma ve ifade değerlendirmeye, iç sıralı arama ağaçlarında sıralı çıktıya uygundur.
• Özyinelemeli gezinme çağrı yığıtını örtük kullanır; açık yığıtla yazılan biçim derin ağaçlarda güvenlidir.
• Yığıt yerine kuyruk kullanıldığında gezinme seviye sıralı olur.
• Dört gezinmenin de zaman maliyeti $O(n)$’dir; bellek maliyeti derinlik gezinmelerinde yüksekliğe, seviye gezinmesinde en geniş seviyeye bağlıdır.

Sonraki Adım

Gezinme, ağacın tamamını dolaşır. Oysa bir değeri aramak için tüm ağacı gezmek gerekmemelidir; her düğümde doğru dalın seçilebilmesi yeterlidir. Sonraki ders, bunu mümkün kılan sıralama kuralını — ikili arama ağacını — tanımlayacak.