Bölüm 10: Ağaçlar

10.1Ağaç veri yapısı

Bağlı listede her düğüm bir sonraki düğümü gösterir. Düğüm bir yerine birden çok sonraki düğüm gösterebilseydi ne olurdu? Liste dallanır ve ortaya ağaç çıkar. Bu kesim ağacı tanımlar, kullanıldığı yerleri sayar ve ağacı daha genel bir yapı olan çizgeden ayıran özelliği gösterir.

10.1.1Tanım ve kullanım alanları

Günlük hayatta ağaç biçimli pek çok düzen vardır. Soy ağacında her kişinin altında çocukları yer alır. Bir kurumun yönetim şemasında genel müdürün altında müdürler, onların altında şefler bulunur. Bilgisayardaki dosya sistemi de bir ağaçtır: kök klasörün içinde klasörler, onların içinde başka klasörler ve dosyalar vardır. Her dosyanın tek bir üst klasörü olur. Bu düzenlerin ortak yanı, en üstte tek bir başlangıç noktasının bulunması ve her öğenin tam olarak bir üst öğeye bağlanmasıdır.

Bilgisayar biliminde ağaç, arama ve sıralama yapılarının, veri sıkıştırmanın ve derleyicilerin temelidir. Derleyici bir programı okurken önce söz dizimini çözümler (syntax analysis) ve programın yapısını bir ağaç olarak kurar. Kod iyileştirme ve ara kod üretimi bu ağaç üzerinde çalışır. Aritmetik ifadeler, karar süreçleri, oyunlardaki hamle seçenekleri ve veri tabanı dizinleri de ağaçla tutulur.

Tanım özyinelemelidir: ağacı, yine ağaç olan parçalar cinsinden tanımlar. Kökü çıkarınca geriye birkaç küçük ağaç kalır; onların kökleri çıkarılınca daha küçük ağaçlar kalır. Bu süreç tek düğümlü ağaçlara kadar iner. Tanımın bu biçimi, ağaç üzerinde çalışan yordamların neden doğal olarak özyinelemeli yazıldığını açıklar. Bir yordam kökte küçük bir iş yapar, sonra aynı yordamı alt ağaçların her biri için çağırır. Alt ağaçlar ayrık olduğu için hiçbir düğüm iki kez işlenmez. Bu nottaki bütün gezinme, kopyalama ve karşılaştırma yordamları bu kalıba uyar.

10.1.2Ağaç ile çizge

Düğümler ve onları bağlayan kenarlardan oluşan en genel yapı çizgedir (graph). Ağaç, çizgenin özel bir türüdür. Ağaçta kök dışındaki her düğümün tek bir ebeveyni vardır. Çizgede ise bir düğüme birden çok düğümden kenar gelebilir. Şekil 10.1 iki yapıyı yan yana gösterir. Soldaki yapıda A'nın altında B ve C, C'nin altında D ve E vardır; her düğüme yukarıdan tek bir kenar iner. Sağdaki yapıda D'ye hem B'den hem C'den kenar gelir. D'nin iki ebeveyni olduğu için bu yapı ağaç değildir.

Tek ebeveyn koşulu iki önemli sonuç doğurur. Birincisi, kökten herhangi bir düğüme giden yol tektir. İkincisi, ağaçta döngü yoktur: bir düğümden başlayıp kenarları izleyerek aynı düğüme geri dönülemez. n düğümlü bir ağaçta kök dışındaki her düğüme tam bir kenar girdiği için kenar sayısı n − 1'dir. İkili ağaçların düğüm sayısı ilişkileri de bu sayıya dayanır.

10.2Terminoloji

Ağaçlarla ilgili terimlerin çoğu soy ağacından gelir: ebeveyn, çocuk, kardeş, ata, torun. Kalan terimler (derece, düzey, derinlik) düğümleri ve ağacı sayısal olarak betimler. Bu kesim bütün terimleri tek bir örnek ağaç üzerinde tanımlar. Şekil 10.2 bu ağacı gösterir: on üç düğüm, dört düzey. Düğümlerin sağ üstündeki küçük sayılar o düğümün derecesidir.

10.2.1Ebeveyn, çocuk, kardeş, ata ve soy

Ağacın en üstündeki, ebeveyni olmayan düğüm köktür. Örnek ağaçta kök A'dır. Alt ağaçları olan bir düğüm, o alt ağaçların köklerinin ebeveynidir (parent). Alt ağaçların kökleri de o düğümün çocuklarıdır (child). B, E ve F'nin ebeveynidir; E ve F, B'nin çocuklarıdır. Aynı ebeveynin çocukları birbirinin kardeşidir (sibling): E ile F kardeştir, H, I ve J de kardeştir. Terminoloji soy ağacındaki gibi büyükbaba ve toruna kadar genişler. D, M'nin büyükbabasıdır, çünkü M'nin ebeveyni H'nin ebeveyni D'dir.

Bir düğümün ataları (ancestor), kökten o düğüme giden yol (path) üzerindeki bütün düğümlerdir. M'nin ataları A, D ve H'dir. Kök hiçbir düğümün soyundan değildir; kökün atası yoktur. Bir düğümün alt ağacındaki bütün düğümler onun soyudur (descendant). B'nin soyu E, F, K ve L'dir. Çocukların çocukları torundur: E, F, G, H, I ve J, A'nın torunlarıdır. İki tanım birbirinin tersidir: X, Y'nin atasıysa Y de X'in soyundandır. Bu ilişki gezinme yordamlarında önemlidir. Bir düğümü işleyen özyinelemeli yordam, o düğümün bütün soyunu da işler, atalarına ise hiç dokunmaz.

10.2.2Derece, yaprak, düzey ve derinlik

Bir düğümün derecesi (degree), o düğümün alt ağaç sayısıdır, yani çocuk sayısıdır. A'nın derecesi 3, B'nin 2, C'nin 1, F'nin 0'dır. Derecesi 0 olan düğüme yaprak (leaf) ya da uç düğüm (terminal node) denir. Örnek ağacın yaprakları K, L, F, G, M, I ve J'dir. En az bir çocuğu olan düğümler iç düğümdür (internal node): A, B, C, D, E ve H.

Düğümlerin düzeyi (level) kökten başlayarak numaralanır. Bu derste kök 1. düzeydedir; bir düğümün düzeyi ebeveyninin düzeyinden bir fazladır. B, C ve D 2. düzeyde, E, F, G, H, I ve J 3. düzeyde, K, L ve M 4. düzeydedir. Ağacın kendisi için de iki sayı tanımlanır. Ağacın derecesi, düğüm derecelerinin en büyüğüdür; örnek ağaçta 3'tür (A ve D). Ağacın derinliği (depth), düğümlerin en büyük düzey numarasıdır; örnek ağaçta 4'tür. Şekil 10.3 iki sayıyı aynı çizimde gösterir.

Derece ve derinlik farklı soruların cevabıdır. Derece ağacın ne kadar geniş dallandığını, derinlik ne kadar aşağı indiğini ölçer. Bir zincir gibi uzanan ağacın derecesi 1, derinliği düğüm sayısı kadardır. Kökün altına doğrudan yüz yaprak bağlanmış bir ağacın derecesi 100, derinliği 2'dir. Gezinme yordamlarının bellek maliyeti derinliğe bağlıdır; ikili ağaçlarda derece zaten en çok 2'dir.

10.2.3Derinlik tanımları: kitaplar farklı sayar

Düzey ve derinlik kavramları kaynaktan kaynağa bir kayma gösterir. Bu dersin ana kaynağı Horowitz, Sahni ve Anderson-Freed'in kitabıdır. Bu kitapta kök 1. düzeydedir ve ağacın derinliği en büyük düzeydir, yani kökten en uzak yaprağa giden yoldaki düğüm sayısıdır. Cormen ve arkadaşlarının kitabı (CLRS) ile Sedgewick'in kitabı ise kökün derinliğini 0 kabul eder. Bu kitaplarda ağacın yüksekliği (height) kökten en uzak yaprağa giden yoldaki kenar sayısıdır. Aynı ağaç için iki tanım bir farkla ayrılır. Tablo 10.1 örnek ağaçtaki değerleri karşılaştırır.

İki tanımdan biri doğru, öteki yanlış değildir; yalnız ölçülen şey farklıdır. Biri düğüm, öteki kenar sayar. Bir yoldaki kenar sayısı her zaman düğüm sayısından bir eksiktir. Bu yüzden formüller de bir kayar: bu derste k derinlikli ikili ağaçta en çok 2^k − 1 düğüm vardır; yükseklikle yazıldığında aynı sınır 2^h+1 − 1 olur. Sınavda ya da bir kaynakta formül kullanılırken önce hangi tanımın geçerli olduğuna bakılmalıdır.

Bu notta derinlik bir fonksiyon olarak da kullanılır: derinlik(NULL) = 0, tek düğümlü ağacın derinliği 1'dir. Boş olmayan bir ağacın derinliği, iki alt ağacın derinliklerinden büyük olanın bir fazlasıdır. Bu tanım doğrudan bir C fonksiyonuna dönüşür:

int derinlik(agac_gost L) {      /* boş ağaç 0, tek düğüm 1 */
  if (!L) return 0;
  int s = derinlik(L->solcocuk);
  int r = derinlik(L->sagcocuk);
  return 1 + (s > r ? s : r);
}

Fonksiyon önce boş ağacı yakalar ve 0 döndürür. Boş olmayan ağaçta iki alt ağacın derinliğini özyinelemeli olarak hesaplar ve büyük olana 1 ekler. Eklenen 1 kökün kendisidir. Bütün düğümlere bir kez uğradığı için zamanı O(n)'dir. Sunumdaki ikili ağaçlarla yapılan denemelerde fonksiyon el hesabıyla aynı değerleri verdi; boş ağaç için 0 döndürdü.

10.3İkili ağaç

Genel ağaçta bir düğümün çocuk sayısı sınırsızdır. Bu esneklik bellekte bir sorun yaratır: her düğüme kaç işaretçi alanı ayrılacağı önceden bilinmez. Çocuk sayısı en çok iki ile sınırlanınca hem bellek düzeni sabitlenir hem de yordamlar yalınlaşır. Bu kesim ikili ağacı tanımlar ve onun düğüm sayısıyla derinliği arasındaki ilişkileri kanıtlar.

10.3.1Tanım

Tanımın iki ayrıntısı genel ağaçtan farklıdır. Birincisi, ikili ağaç boş olabilir; genel ağaç tanımında en az bir düğüm vardır. Boş ağaç sayesinde “sol alt ağaç yok” durumu “sol alt ağaç boş” diye ifade edilir. Bütün yordamlar da tek bir taban durumla, boş ağaçla, biter. İkincisi, sol ile sağ ayrıdır. Tek çocuklu bir düğümde çocuğun solda mı sağda mı olduğu önemlidir. Kökü A, tek çocuğu B olan iki ağaç düşünelim: birinde B soldadır, ötekinde sağdadır. Genel ağaç olarak ikisi aynı ağaçtır; ikili ağaç olarak iki farklı ağaçtır. Bu yüzden düğüm dereceleri 0, 1 ya da 2 olabilir, ama 1 dereceli bir düğümün çocuğunun yönü de bilgi taşır.

Kümeler arasında bir içerme ilişkisi vardır: her ikili ağaç (boş olanı dışında) bir ağaçtır, her ağaç da bir çizgedir. Şekil 10.4 iki ikili ağaç gösterir. Soldaki ağaçta her düğümün yalnız sol çocuğu vardır; bu tür ağaca çarpık ağaç (skewed tree) denir. Sağdaki ağaç dört düzeylidir ve düğümler düzeylere dengeli dağılmıştır.

Şekildeki iki ağacın derinliği aynıdır; düğüm sayıları ise 4 ve 11'dir. Aynı derinliğe çok farklı sayıda düğüm sığabilir. Derinlik, gezinme yordamlarının bellek maliyetini belirlediği için “n düğümlü bir ağacın derinliği en az ve en çok ne olabilir?” sorusu önemlidir. Sonraki iki alt kesim bu sorunun cevabını verir.

10.3.2Bir düzeyde ve bir ağaçta en fazla kaç düğüm

İkili ağaçta her düğümün en çok iki çocuğu olduğu için her düzeydeki düğüm sayısı bir öncekinin en çok iki katıdır. Bu gözlem iki sınır verir.

Kanıt. (i) i üzerinde tümevarımla kanıtlanır. Taban durum i = 1'dir: 1. düzeyde yalnız kök vardır ve 2⁰ = 1'dir. Tümevarım adımı için (i − 1). düzeyde en çok 2ⁱ⁻² düğüm bulunduğunu varsayalım. i. düzeydeki her düğüm, (i − 1). düzeydeki bir düğümün çocuğudur ve her düğümün en çok iki çocuğu vardır. Bu yüzden i. düzeyde en çok 2 · 2ⁱ⁻² = 2ⁱ⁻¹ düğüm bulunur.

(ii) Derinliği k olan ağaçta düğümler 1'den k'ya kadar olan düzeylere dağılmıştır. (i) her düzeyin sınırını verir. Toplam düğüm sayısı en çok

Σ_i=1..k 2ⁱ⁻¹ = 2⁰ + 2¹ + … + 2^k−1 = 2^k − 1

olur. Son eşitlik geometrik toplamdır: toplam S ile gösterilirse 2S − S = 2^k − 2⁰ bulunur. ∎

Ders kitabı bu sonucu “lemma” olarak adlandırır. Lemma, doğruluğu kolayca görülen ve daha büyük bir teoremin kanıtında basamak olarak kullanılan küçük bir önermedir. Şekil 10.5 dört düzeyli ağaçta düzey düzey sayıları gösterir: 1, 2, 4 ve 8 düğüm, toplam 15. Derinlik 5 olsaydı beşinci düzeye 16 düğüm daha eklenir, toplam 31 olurdu.

10.3.3Tam dolu ve tam ikili ağaç

Teorem 10.1'in sınırına ulaşan ağaçlar özel bir ad alır. Bir de bu sınıra en çok yaklaşan, son düzeyi eksik olabilen ağaçlar vardır. İki kavram adlarının benzerliği yüzünden sık karıştırılır.

Numaralandırmanın kuralı basittir: bir düğümün numarası i ise sol çocuğunun numarası 2i, sağ çocuğunun numarası 2i + 1'dir. Kök 1'dir; kökün çocukları 2 ve 3'tür; 2'nin çocukları 4 ve 5'tir, 3'ün çocukları 6 ve 7'dir. Tam ağaç, bu numaralar 1'den n'ye kadar atlamasız kullanıldığında elde edilen ağaçtır. Tanımın gündelik dildeki karşılığı şudur: son düzey dışındaki bütün düzeyler doludur ve son düzeydeki düğümler soldan sağa, arada boşluk bırakmadan dizilmiştir.

Şekil 10.6'daki sağdaki ağaç on düğümlüdür, ama tam değildir. 5 numaralı düğümün sol çocuğu yoktur, sağ çocuğu vardır. Bu yüzden numaralar 1–9 ve 11'dir; 10 atlanmıştır. Ortadaki ağaçta ise 5'in yalnız sol çocuğu vardır ve numaralar 1'den 10'a kesintisizdir. Her tam dolu ağaç aynı zamanda tamdır; tersi doğru değildir.

Tam ağacın önemi iki noktadan gelir. Birincisi, tam ağaç bir diziye boşluksuz yerleşir: i numaralı düğüm dizinin i. gözüne konur ve hiçbir göz boş kalmaz. İkincisi, n düğümlü ikili ağaçlar arasında derinliği en küçük olan tam ağaçtır. Heap yapısı bu iki özelliğin üzerine kurulur.

10.3.4Derinlik ve düğüm sayısı ilişkileri

k derinlikli bir ikili ağaçta her düzeyde en az bir düğüm vardır; yoksa derinlik k olmazdı. Bu yüzden düğüm sayısı en az k'dır. Teorem 10.1'den en çok 2^k − 1'dir. Birlikte yazılınca

k ≤ n ≤ 2^k − 1

elde edilir. Bu eşitsizlik derinlik cinsinden de yazılabilir. Sağ taraftan n + 1 ≤ 2^k, yani lg(n + 1) ≤ k çıkar; k tamsayı olduğu için ⌈lg(n + 1)⌉ ≤ k olur. Sol taraf ise k ≤ n'dir. Sonuç olarak

⌈lg(n + 1)⌉ ≤ k ≤ n

bulunur. Alt sınıra tam ağaç ulaşır: tam ağacın derinliği ⌈lg(n + 1)⌉ = ⌊lg n⌋ + 1'dir. Üst sınıra çarpık ağaç ulaşır: her düzeyde tek düğüm vardır ve derinlik n'dir. Örneğin 20 düğümlü bir ikili ağacın derinliği 5 ile 20 arasında olabilir; 20 düğümlü tam ağacın derinliği ⌈lg 21⌉ = 5'tir. Bu iki uç, “dengeli ağaçta O(lg n), çarpık ağaçta O(n)” biçimindeki bütün maliyet sonuçlarının kaynağıdır.

Düğüm sayısıyla ilgili ikinci ilişki yaprakları ve iki çocuklu düğümleri bağlar. İkili ağaçta derecesi 0, 1 ve 2 olan düğümlerin sayıları sırasıyla n₀, n₁ ve n₂ ile gösterilsin.

Kanıt. Düğüm sayısı iki yoldan sayılır. Her düğümün derecesi 0, 1 ya da 2 olduğu için n = n₀ + n₁ + n₂'dir. Kök dışındaki her düğüme yukarıdan tam bir kenar girer; kenar sayısı n − 1'dir. Kenarlar düğümlerden çıkarak da sayılabilir: 1 dereceli düğümden bir, 2 dereceli düğümden iki kenar çıkar. Bu yüzden n − 1 = n₁ + 2n₂'dir. İlk eşitlikten ikincisi çıkarılırsa 1 = n₀ − n₂, yani n₀ = n₂ + 1 bulunur. ∎

Şekil 10.7 eşitliği bir örnekle doğrular. Tek çocuklu iki düğüm (F ve G) sonucu etkilemez: bir zincire tek çocuklu düğüm eklemek yaprak sayısını da iki çocuklu düğüm sayısını da değiştirmez. Yeni bir yaprak ancak var olan bir düğüme ikinci çocuk eklenerek kazanılır; bu işlem n₂'yi de bir artırır.

Teoremin C gerçeklemesi için önemli bir sonucu vardır. Bağlı gösterimde her düğüm iki işaretçi alanı taşır; n düğümde toplam 2n alan vardır. Bunların n − 1'i bir kenarı, yani bir çocuğu gösterir. Geriye kalan 2n − (n − 1) = n + 1 alan NULL'dır. On bir düğümlü örnekte 22 alanın 10'u dolu, 12'si boştur. Boş işaretçilerin sayısı dolu olanlardan fazladır. Bu boş alanlar, kök ortada sıradaki önceki ve sonraki düğümü gösterecek biçimde kullanılırsa kılavuzlu ikili ağaç (threaded binary tree) elde edilir. Aynı sayı, özyinelemeli gezinmelerin NULL ile kaç kez çağrıldığını da verir.

10.4İkili ağacın bellekte gösterimi

Bir ikili ağaç bellekte iki biçimde tutulabilir. Birincisinde düğümler bir diziye, numaralarına göre yerleştirilir; ebeveyn ve çocuklar indis hesabıyla bulunur. İkincisinde her düğüm ayrı bir struct'tır ve çocuklarına işaretçilerle bağlanır. Bu kesim iki gösterimi C koduyla kurar ve hangisinin ne zaman seçileceğini tartışır.

10.4.1Dizi ile gösterim

Tam ağacın numaralandırması doğrudan bir dizi düzeni verir: i numaralı düğüm dizinin i indisli gözüne konur. Formüllerin yalın kalması için indisler 1'den başlar; C dizisinin 0. gözü kullanılmaz. Ebeveyn ve çocuk indisleri şöyle hesaplanır:

• baba(i) = ⌊i/2⌋. i = 1 ise düğüm köktür ve ebeveyni yoktur.
• solcocuk(i) = 2i. 2i > n ise sol çocuk yoktur.
• sagcocuk(i) = 2i + 1. 2i + 1 > n ise sağ çocuk yoktur.

#define MAX_DUGUM 63   /* 2^k - 1 */
char agac[MAX_DUGUM + 1];  /* [0] kullanılmaz */
int  n;                    /* düğüm sayısı */

int baba(int i)     { return i / 2; }
int solcocuk(int i) { return 2 * i; }
int sagcocuk(int i) { return 2 * i + 1; }
/* çocuk var mı?  solcocuk(i) <= n */

MAX_DUGUM, dizinin tutabileceği en büyük düğüm sayısıdır. Derinliği k olan bir ağacı her biçimde tutabilmek için 2^k − 1 gözlük yer açılmalıdır; burada k = 6 için 63 seçilmiştir. Dizinin boyu MAX_DUGUM + 1'dir, çünkü 0. göz boş bırakılır. n o anki düğüm sayısını tutar. Üç fonksiyon tek bir aritmetik işlemle sonuç verir: C'de iki pozitif tamsayının bölümü aşağı yuvarlandığı için i / 2 zaten ⌊i/2⌋'dir. Bir çocuğun var olup olmadığı indisin n ile karşılaştırılmasıyla anlaşılır: solcocuk(i) <= n ise sol çocuk vardır.

Formüllerin doğruluğu numaralandırmadan görülür. i. düğümün düzeyi 2^j'den başlasın. Sonraki düzey 2^j+1'den başlar ve i'nin solundaki her düğüm oraya iki çocuk verir. Sol çocuğun numarası 2^j+1 + 2(i − 2^j) = 2i, sağ çocuğunki 2i + 1 olur. 2i de 2i + 1 de ikiye bölünüp aşağı yuvarlanınca i verir.

Tablo 10.2'deki değerler kodun küçük bir test programıyla üretildi. 5 numaralı E'nin sol çocuğu 10 numaralı J'dir; sağ çocuğu olacak 11 numaralı göz n = 10'u aştığı için yoktur. 6 numaralı ve sonraki düğümler yapraktır. Bir düğümün yaprak olup olmadığı da yalnız indisle anlaşılır: 2i > n ise i yapraktır. On düğümlü ağaçta yapraklar 6'dan 10'a kadar olan düğümlerdir; genel olarak tam ağaçta ⌊n/2⌋ + 1'den n'ye kadar olan düğümler yapraktır.

10.4.2Dizide bellek kaybı

Dizi gösterimi her ikili ağaç için kullanılabilir: ağaç, aynı derinlikteki tam dolu ağacın içine yerleştirilmiş gibi düşünülür ve var olmayan düğümlerin gözleri boş bırakılır. Ancak bu boş gözler belleği boşa harcar. Şekil 10.8 iki uç durumu karşılaştırır.

Tam ağaçta bellek kaybı ya hiç yoktur ya da son düzeydeki birkaç gözle sınırlıdır. Ağaç tam olmaktan uzaklaştıkça boş göz sayısı artar. En kötü durum çarpık ağaçtır. Sola çarpık ağaçta her düğüm bir öncekinin sol çocuğudur; numaralar 1, 2, 4, 8, … diye iki katına çıkar. k düğümlü sola çarpık ağaç 2^k − 1 göz ister ve bunların yalnız k'sını kullanır. k = 5 için 31 gözden 26'sı boştur. k = 30 olsaydı bir milyardan fazla göz gerekirdi; otuz düğümlü bir liste için bu kabul edilemez. Dizi gösteriminde ağaç değişirken de sorun çıkar: bir düğümün ortaya eklenmesi ya da silinmesi, altındaki bütün alt ağacın başka indislere taşınmasını gerektirir.

Dersin hocası bu durumu şöyle özetler: depolama ve erişim bilgisayar biliminin iki ana konusudur; ağaç tam ikili ağaçsa ve ağaca ekleme ya da çıkarma yapılmayacaksa diziyle gerçeklemek uygundur. Başka her durumda ağaç bağlı gösterimle tutulur.

10.4.3Bağlı gösterim

Bağlı gösterimde her düğüm, verisiyle birlikte iki işaretçi taşıyan bir struct'tır. Sol işaretçi sol alt ağacın kökünü, sağ işaretçi sağ alt ağacın kökünü gösterir. Alt ağaç boşsa işaretçi NULL'dır. Bu derste kullanılan tanım şudur:

typedef struct agac *agac_gost;
struct agac {
    agac_gost solcocuk;   /* sol alt ağaç */
    char      veri;
    agac_gost sagcocuk;   /* sağ alt ağaç */
};

İlk satır, struct agac'ı gösteren işaretçi tipine agac_gost adını verir. Bu satır struct agac tanımlanmadan önce yazılabilir, çünkü C bir yapının içeriğini bilmeden ona işaretçi tanımlamaya izin verir. Yapının içinde agac_gost tipinde iki alan vardır; yapı kendisiyle aynı türden nesneleri gösterir. Bu tür yapılara kendine dayanan yapı denir. Bağlı listedeki düğüm yapısının tek bağ alanı vardı; burada iki bağ alanı vardır. Ağacın kendisi kök düğümün adresiyle temsil edilir: agac_gost kok; bildirimi bir ağaç değişkenidir. kok == NULL boş ağaç demektir.

Düğümler malloc ile heap bellekten ayrı ayrı ayrılır ve bellekte herhangi bir yere düşer. Ağaç yapısı yalnız işaretçilerle kurulur. Tablo 10.3 Şekil 10.9'daki ağacın bellekteki olası bir görünümünü verir. Adresler örnek olarak seçilmiştir; gerçek adresler her çalıştırmada değişir. Burada önemli olan, düğümlerin sırasının ağacın şekliyle hiçbir ilgisinin olmamasıdır.

Bir düğümün bellekte kapladığı yer derleyiciye ve makineye bağlıdır. 64 bitlik bir makinede her işaretçi 8 bayttır ve veri 1 bayttır. Derleyici ikinci işaretçiyi 8'in katı olan bir adrese hizalamak için veri'den sonra 7 bayt dolgu ekler. Testte kullanılan Windows x86-64 derlemesinde sizeof(struct agac) 24 bayt çıktı: 16 baytlık iki işaretçi, 1 baytlık veri ve 7 baytlık dolgu. Alanların sırası veri, solcocuk, sagcocuk olsaydı dolgu sona kayardı ve boyut yine 24 olurdu. n düğümlü ağaç n düğüm kadar yer kaplar; ağacın şekli belleği etkilemez. Dizi gösteriminin aksine çarpık ağaç da dengeli ağaç kadar yer tutar.

10.4.4Düğüm ayırma ve ağacı bırakma

Her yeni düğüm için aynı üç iş yapılır: bellek ayrılır, ayırmanın başarılı olduğu denetlenir ve çocuk işaretçileri NULL yapılır. Bu işleri tek bir fonksiyonda toplamak hem kodu kısaltır hem de unutulan bir denetimin yol açacağı hataları önler. Sunumdaki ogeal ve onun tersi olan agac_sil şunlardır:

agac_gost ogeal(void) {          /* yeni düğüm */
    agac_gost p = malloc(sizeof *p);
    if (p == NULL) {
        fprintf(stderr, "Bellek yok!\n");
        exit(EXIT_FAILURE);
    }
    p->solcocuk = p->sagcocuk = NULL;
    return p;
}

void agac_sil(agac_gost L) {     /* kök sonda */
    if (!L) return;
    agac_sil(L->solcocuk);
    agac_sil(L->sagcocuk);
    free(L);
}

ogeal'ın ilk satırı malloc(sizeof *p) ile bir düğümlük yer ister. sizeof *p yazımı, p'nin gösterdiği tipin boyutunu verir; tip adı değişse bile ifade doğru kalır. malloc yer bulamazsa NULL döner. Bu durumda fonksiyon stderr'e bir ileti yazar ve programı exit(EXIT_FAILURE) ile sonlandırır. Ödev ve sınav programları için bu yeterlidir; büyük bir programda NULL çağırana döndürülür ve karar orada verilir. malloc'un verdiği bellek temizlenmemiştir, alanlar rastgele değerler taşır. Bu yüzden iki çocuk işaretçisi açıkça NULL yapılır. p->solcocuk = p->sagcocuk = NULL; ifadesi sağdan sola çalışır: önce sagcocuk'a NULL atanır, atamanın değeri de solcocuk'a atanır. Veri alanını çağıran doldurur.

agac_sil ağacın bütün düğümlerini heap'e geri verir. Sıra önemlidir: önce sol alt ağaç, sonra sağ alt ağaç silinir, kök en sonda iade edilir. Kök önce free edilseydi L->solcocuk ve L->sagcocuk alanlarını okumak, iade edilmiş belleğe erişmek olurdu. Bu tanımsız davranıştır. Okuma bazen “çalışır”, bazen çöp değer verir; iki durumda da alt ağaçlar ya sızar ya da program çöker. Kökü sona bırakan bu sıra, kök sonda gezinmenin ta kendisidir. Fonksiyon her düğüme bir kez uğradığı için O(n) zamanda çalışır. Boş ağaçla çağrılınca hiçbir şey yapmaz; agac_sil(NULL) güvenlidir.

Bu nottaki bütün C kodları sayaçlı bir malloc/free sarmalayıcısıyla da çalıştırıldı. Her testin sonunda ayrılan ve iade edilen düğüm sayıları eşit çıktı; hiçbir testte sızıntı kalmadı. Örneğin gezinme testlerinde 53 düğüm ayrıldı ve agac_sil çağrılarıyla 53 düğüm geri verildi.

10.4.5Dizi mi, bağlı gösterim mi?

İki gösterimin üstün ve zayıf yanları birbirini tamamlar. Tablo 10.4 karşılaştırmayı özetler.

Kural kısaca şudur: ağaç tam ve sabitse dizi, şekli değişen ağaç için bağlı gösterim seçilir. Örneğin bir ağdaki bilgisayarlar sabitse ve sonradan eklenip çıkarılmayacaksa bağlantı ağacı diziyle tutulabilir. Heap, her zaman tam kalacak biçimde ekleme ve silme yaptığı için dizinin hızından tam olarak yararlanır. Arama ağaçları ise eklemeyle her yöne büyüyebilir; onlar bağlı gösterimle tutulur. Bağlı gösterimin tek zayıflığı ebeveyne erişimdir. Bir düğümden yukarı çıkmak gerekiyorsa düğüme üçüncü bir işaretçi, ebeveyn alanı eklenir; bunun bedeli her düğümde 8 bayt daha ve her eklemede bir atama daha demektir.

10.4.6Genel ağacı ikili ağaca çevirme

Genel ağaçta bir düğümün çocuk sayısı değişkendir. A'nın üç çocuğu varken F'nin hiç çocuğu yoktur. Sabit alanlı bir struct ile her düğüme “en çok kaç çocuk olabilir” kadar işaretçi ayırmak çoğu işaretçiyi boş bırakır. Derecesi d olan n düğümlü bir ağaçta nd alanın yalnız n − 1'i dolu olur. Çözüm, sol çocuk – sağ kardeş gösterimidir: her düğüm yalnız iki bağ taşır. Birincisi düğümün ilk (en soldaki) çocuğunu, ikincisi düğümün bir sağındaki kardeşini gösterir.

struct gdugum {
    char veri;
    struct gdugum *ilk_cocuk;  /* = sol */
    struct gdugum *kardes;     /* = sağ */
};

Bu yapı biçim olarak ikili ağaç düğümüyle aynıdır: ilk_cocuk sol işaretçinin, kardes sağ işaretçinin yerine geçer. Dolayısıyla her genel ağaç bir ikili ağaç olarak saklanabilir ve ikili ağaç için yazılmış bütün yordamlar ona uygulanabilir. Şekil 10.10 dönüşümü iki adımda gösterir.

Dönüşüm şöyle yapılır. Her düğüm için ilk çocuğa giden bağ tutulur, öteki çocuklara giden bağlar silinir. Sonra aynı ebeveynin çocukları soldan sağa bir zincir hâlinde birbirine bağlanır. B'nin ilk çocuğu E'dir; E'nin kardeşi F'dir. A'nın ilk çocuğu B'dir; B'nin kardeşi C, C'nin kardeşi D'dir. İkili ağaçta B, A'nın sol çocuğu olur; C, B'nin sağ çocuğu olur; D, C'nin sağ çocuğu olur. Kökün kardeşi olmadığı için kökün sağ bağı her zaman NULL'dır.

Dönüşümün gezinmelerle ilgili iki sonucu vardır. İkili ağacın kök önde sırası, genel ağacın kök önde sırasıyla aynıdır: ikisinde de A B E K L F C G D H M I J çıkar. İkili ağacın kök ortada sırası ise genel ağacın kök sonda sırasına eşittir: K L E F B G C M H I J D A. İkinci sonucun nedeni şudur: ikili ağaçta bir düğümün sol alt ağacı, genel ağaçtaki bütün soyudur. Kök ortada gezinme önce sol alt ağacı, yani bütün soyu yazar; düğümün kendisini ondan sonra yazar. Sağ alt ağaç ise kardeşlerdir ve onlar düğümden sonra gelir. Bu, genel ağaçta “önce çocukları, sonra kendini” kuralıdır. İki eşitlik bir Python betiğiyle de denetlendi.

10.5Özyinelemeli gezinmeler

Bir veri yapısının bütün öğelerine belirli bir sırayla birer kez uğramaya gezinme (traversal) denir. Dizide ve bağlı listede gezinme sırası doğaldır: baştan sona. İkili ağaçta ise her düğümden iki yöne gidilebilir ve “önce hangisi?” sorusunun birden çok cevabı vardır. Bu kesim olası sıraları sayar, bunların üçünü C ile yazar, kodu adım adım izler ve maliyetini çıkarır.

10.5.1Altı gezinme sırası

Bir düğümde ele alınacak üç şey vardır: düğümün verisi (V), sol alt ağaç (L) ve sağ alt ağaç (R). Gezinme, bu üçünü hangi sırayla işleyeceğine karar verir ve aynı kararı her alt ağaçta yineler. Üç öğenin 3! = 6 farklı sırası vardır. Tablo 10.5 hepsini listeler.

Solun sağdan önce gezildiği üç sıra standarttır ve adlarını kökün konumundan alır. Kök, alt ağaçlardan önce işleniyorsa kök önde, iki alt ağacın arasında işleniyorsa kök ortada, ikisinden sonra işleniyorsa kök sonda gezinmedir. Sunumlarda kök önde gezinme için “kök önde” sözü de kullanılır; C kodundaki kok_onde_dolas adı buradan gelir. Kalan üç sıra, standart sıraların sağdan sola gezilen aynalarıdır. Uygulama gerektirirse onlar da kullanılır.

10.5.2İfade ağacı ve üç gösterim

Gezinme sıralarının adları aritmetik ifadelerden tanıdıktır. İfade ağacı (expression tree), iç düğümleri işleç, yaprakları işlenen olan ikili ağaçtır. Her işleç düğümü, iki alt ağacının değerlerine uygulanır. Şekil 10.11 ((((A / B) * C) * D) + E) ifadesinin ağacını gösterir. En son uygulanan işleç + olduğu için kök odur; sol alt ağacı ((A / B) * C) * D, sağ alt ağacı E'dir.

Bu ağaç üç standart sırayla gezilince ifadenin üç bilinen gösterimi çıkar:

• Kök ortada: A / B * C * D + E. Bu, ara-işleç (infix) gösterimidir. Ağaçta parantez yoktur; ara-işleç yazarken her alt ağacın etrafına parantez eklenerek ((((A/B)*C)*D)+E) geri elde edilir.
• Kök önde: + * * / A B C D E. Bu, ön-işleç (prefix) gösterimidir.
• Kök sonda: A B / C * D * E +. Bu, son-işleç (postfix) gösterimidir.

Ön-işleç ve son-işleç gösterimleri parantez gerektirmez: işleçlerin sırası hesaplama sırasını tek anlamlı belirler. Derleyiciler kaynak koddaki ifadeleri önce böyle bir ağaca çevirir. Son-işleç gösterimi bir yığınla soldan sağa tek geçişte değerlendirilir: işlenen gelince yığına itilir; işleç gelince yığından iki değer alınır, işlem yapılır ve sonuç yığına itilir. Ağacın kök sonda gezinmesi tam olarak bu sırayı üretir.

10.5.3Aynı ağaçta üç gezinme

Gezinme çıktısını elle bulmak için kural her alt ağaçta yinelenir. On iki düğümlü A…L ağacı üzerinde üç gezinme şöyle bulunur. Ağaçta A'nın sol çocuğu B, sağ çocuğu F'dir. B'nin sol çocuğu yoktur, sağ çocuğu C'dir. C'nin çocukları D ve E'dir; D'nin çocukları G ve H'dir. E'nin yalnız sağ çocuğu I vardır; I'nın çocukları J ve K'dir. F'nin yalnız sol çocuğu L vardır. Şekil 10.12 ağacı kök ortada sırasıyla numaralanmış olarak gösterir.

• Kök önde (V-L-R). Önce kök A yazılır. Sonra sol alt ağacın tamamı: B, ardından B'nin sağı olan C alt ağacı (C, D, G, H, E, I, J, K). En son sağ alt ağaç: F, L. Çıktı: ABCDGHEIJKFL.
• Kök ortada (L-V-R). A'nın sol alt ağacı B'den başlar. B'nin solu boş olduğu için ilk B yazılır. Sonra B'nin sağ alt ağacı kök ortada gezilir: G, D, H, C, E, J, I, K. Ardından A yazılır, en son F'nin alt ağacı: L, F. Çıktı: BGDHCEJIKALF.
• Kök sonda (L-R-V). Kök her alt ağaçta en sondadır. G, H, D; sonra J, K, I, E; sonra C, B; sonra L, F; en son A. Çıktı: GHDJKIECBLFA.

Üç çıktıda yaprakların (G, H, J, K, L) birbirine göre sırası aynıdır. Gezinmeler yalnız iç düğümlerin yaprakların arasına nereye yerleştiğinde ayrılır. Bu gözlem, el ile bulunan bir çıktının denetlenmesinde işe yarar. Kök önde çıktının ilk harfi ve kök sonda çıktının son harfi her zaman köktür.

10.5.4Gezinme yordamları

Gezinmenin özyinelemeli tanımı neredeyse kelimesi kelimesine C koduna dönüşür. Kök önde gezinme için “ağaç boş değilse kökü yaz, sol alt ağacı kök önde gez, sağ alt ağacı kök önde gez” denir:

void kok_onde_dolas(agac_gost L) {
  if (L) {
    printf("%c", L->veri);
    kok_onde_dolas(L->solcocuk);
    kok_onde_dolas(L->sagcocuk);
  }
}

Kök ortada ve kök sonda yordamları aynı iskelettir; yalnız printf satırının yeri değişir:

void kok_ortada_dolas(agac_gost L) {
  if (L) {
    kok_ortada_dolas(L->solcocuk);
    printf("%c", L->veri);
    kok_ortada_dolas(L->sagcocuk);
  }
}

void kok_sonda_dolas(agac_gost L) {
  if (L) {
    kok_sonda_dolas(L->solcocuk);
    kok_sonda_dolas(L->sagcocuk);
    printf("%c", L->veri);
  }
}

Üç yordam satır satır şöyle okunur. if (L) sınaması, L boş olmayan bir ağacı gösteriyorsa doğrudur. Bu tek sınama iki işi birden görür. Birincisi, boş ağaçla çağrılan yordam hiçbir şey yapmadan döner; kok_ortada_dolas(NULL) güvenlidir. İkincisi, özyinelemenin durma koşuludur: her çağrı bir alt ağaca iner, yapraktan sonraki çağrı NULL ile yapılır ve orada zincir durur. printf("%c", L->veri) düğümün verisini yazar; L->veri, (*L).veri'nin kısaltmasıdır. İki özyinelemeli çağrı sol ve sağ alt ağaçları aynı kuralla gezer. printf çağrılardan önceyse kök önde, arasındaysa kök ortada, sonraysa kök sonda gezinme elde edilir.

Dersin hocasının bu kodlar üzerine sık yaptığı bir uyarı vardır: ağaç işaretçisi NULL gelebilir ve öğrencilerin çoğu buna dikkat etmez. Gezinme yordamlarında if (L) sınaması bu yüzden zorunludur. Sınama unutulursa yordam ilk yaprağın boş çocuğuna inince NULL->veri'ye erişir ve program çöker. Boş ağaçla çağrılan bir yordam ise daha ilk satırda çöker.

10.5.5Kod izleme: kök ortada gezinme

Özyinelemeli bir yordamın nasıl çalıştığı, çağrı yığınındaki çerçeveler izlenerek anlaşılır. Her çağrı yığına bir çerçeve ekler; çerçeve o çağrının L parametresini ve dönüş adresini tutar. Çağrı bitince çerçeve yığından kalkar ve çalışma, çağıranın kaldığı yerden sürer. Aşağıdaki izleme dört düğümlü A(B(D), C) ağacı üzerindedir: A'nın sol çocuğu B, sağ çocuğu C; B'nin yalnız sol çocuğu D vardır.

İzlemeden üç sonuç çıkar. Birincisi, ilk yazılan düğüm D'dir: kök ortada gezinme önce en soldaki düğüme kadar iner. İkincisi, çağrı yığınında aynı anda en çok dört çerçeve bulunur: A, B, D ve D'nin boş çocuğu için açılan çerçeve. Bu sayı ağacın derinliğinin (3) bir fazlasıdır. Üçüncüsü, her düğüme bir kez girilir ve bir kez çıkılır; dört düğümlü ağaçta düğüm çağrılarına ek olarak beş NULL çağrısı yapılır. Aynı ağaçta kök önde gezinme ABDC, kök sonda gezinme DBCA verir. İzlemenin adımları ve çağrı sayıları aynıdır; yalnız yazdırmanın yapıldığı an değişir. Kök önde gezinmede düğüm çerçeve açılır açılmaz, kök sonda gezinmede çerçeve kapanmadan hemen önce yazılır.

10.5.6Maliyet ve NULL çağrıları

Zaman. Gezinme yordamı her düğüm için bir kez çağrılır ve o çağrıda sabit iş yapar: bir sınama, bir printf, iki çağrı. Bunlara ek olarak boş alt ağaçlar için NULL çağrıları vardır. Bu çağrıların sayısı tam olarak bilinir.

Kanıt. Yordam her düğüm için bir kez çağrılır: ilk çağrı kökle, diğerleri ebeveynin çocuk işaretçileriyle yapılır. Her düğüm çağrısı iki çağrı daha yapar; bu yüzden ilk çağrı dışındaki çağrı sayısı 2n'dir ve ilkiyle birlikte 2n + 1 eder. Çocuk işaretçilerinin n − 1'i bir düğümü gösterir, n + 1'i NULL'dır (n₀ = n₂ + 1'in sonucu). Dolayısıyla n + 1 çağrı NULL ile yapılır. ∎

Toplam iş 2n + 1 çağrıyla orantılıdır; zaman Θ(n)'dir. Ağacın şekli zamanı değiştirmez: dengeli ağaç da çarpık ağaç da aynı sayıda çağrı yapar. A…L ağacıyla yapılan testte 12 düğüm için 25 çağrı sayıldı; bunların 13'ü NULL çağrısıydı.

Bellek. Çağrı yığınında aynı anda bulunan çerçeve sayısı, kökten o anki düğüme giden yolun uzunluğuna eşittir (artı en fazla bir NULL çerçevesi). Bu sayı en çok ağacın derinliği h kadardır. Bellek maliyeti bu yüzden O(h)'dir. Dengeli ağaçta h = O(lg n), çarpık ağaçta h = n'dir. Bir milyon düğümlü dengeli ağaç yirmi civarında çerçeveyle gezilir; aynı sayıda düğümlü çarpık ağaç bir milyon çerçeve ister. Testte, Windows'ta zig cc ile derlenen programda sola çarpık 100 000 düğümlü zincir özyinelemeyle gezilebildi; 300 000 düğümlü zincirde çağrı yığını taştı ve program çöktü. Aynı zincir yığınla yazılan döngüsel yordamla sorunsuz gezildi. Bu sınırlar makineye, derleyiciye ve yığın boyutuna göre değişir.

NULL çağrıları, çağrıdan önce denetim yapılarak kaldırılabilir:

/* önce: n+1 NULL çağrısı */
kok_onde_dolas(L->solcocuk);
kok_onde_dolas(L->sagcocuk);
/* sonra: çağırmadan denetle */
if (L->solcocuk) kok_onde_dolas(L->solcocuk);
if (L->sagcocuk) kok_onde_dolas(L->sagcocuk);

İkinci biçimde yordam yalnız var olan çocuklar için çağrılır ve toplam çağrı sayısı 2n + 1'den n'ye iner. A…L ağacında 25 çağrı 12'ye düştü. Ancak bu biçimde de yordamın en başındaki if (L) kalmalıdır, çünkü ağacın kendisi boş gelebilir. Kazanç bir sabit çarpandır; asimptotik zaman yine Θ(n)'dir. Kod biraz uzadığı için çoğu durumda ilk, kısa biçim tercih edilir.

Dersin hocası bu noktada iki şeyin altını çizer. Birincisi, “özyinelemeli algoritmalar çok bellek yer” iddiası çoğu zaman özyinelemeli kod yazmamak için bir kaçamaktır: dengeli bir ağaçta yığın derinliği lg n ile sınırlıdır ve bu çok küçük bir sayıdır. İkincisi, algoritmayı yazmak işin yarısıdır; bilgisayar biliminde her algoritmanın analizi yapılmak zorundadır. Bellek için O(lg n) sınırının yalnız dengeli ağaçta geçerli olduğu, genel sınırın O(h) olduğu da bu analizin bir parçasıdır.

10.5.7Çağrı ağacı

Özyinelemeli kod okuyarak değil, yazarak öğrenilir. Dersin hocasının benzetmesiyle, bir halterciyi yüz kez izlemek o halteri kaldırmayı öğretmez. Bir yordam anlaşılmadıysa çağrıların oluşturduğu ağaç kâğıda çizilir.

Çağrı ağacında her çağrı bir düğümdür; bir çağrının yaptığı alt çağrılar onun çocuklarıdır. Gezinme yordamının çağrı ağacı, gezilen ağacın kendisidir: her düğüm için bir çağrı vardır ve o çağrının iki çocuğu, sol ve sağ alt ağaç için yapılan çağrılardır. Tek fark, NULL çağrılarının yaprak olarak eklenmesidir. Böylece çağrı ağacında n iç düğüm ve n + 1 yaprak bulunur. Bu, her iç düğümün tam iki çocuğu olduğu bir ikili ağaçtır ve n₀ = n₂ + 1 eşitliğine bir kez daha uyar. Çağrı yığınının herhangi bir andaki içeriği, çağrı ağacında kökten o anki çağrıya giden yoldur.

10.5.8İfade ağacını hesaplamak

İfade ağacının değerini bulmak bir kök sonda gezinmedir. Bir işlecin değeri, iki alt ifadenin değerleri bilinmeden hesaplanamaz. Önce sol alt ağaç, sonra sağ alt ağaç hesaplanır, en son kökteki işleç uygulanır. Ağacı tutmak için düğüm yapısı biraz değişir: yapraklarda bir sayı, iç düğümlerde bir işleç saklanır.

typedef struct ifade *ifade_gost;
struct ifade {
    char      islec;   /* '+', '-', '*', '/' */
    int       deger;   /* yalnız yapraklarda */
    ifade_gost sol, sag;
};

islec alanı '+', '-', '*' ya da '/' karakterini tutar. deger alanı yalnız yapraklarda anlamlıdır. sol ve sag alt ifadeleri gösterir. Her iç düğümün tam iki çocuğu vardır, çünkü dört işleç de ikilidir; yaprakların hiç çocuğu yoktur. Tekli eksi (−x) gibi tek işlenenli bir işleç eklenseydi tek çocuklu düğümler de gerekirdi. Hesaplama yordamı şudur:

int hesapla(ifade_gost t) {
  if (!t->sol && !t->sag)        /* yaprak: sayı */
    return t->deger;
  int a = hesapla(t->sol);
  int b = hesapla(t->sag);
  switch (t->islec) {
    case '+': return a + b;
    case '-': return a - b;
    case '*': return a * b;
    default:  return a / b;
  }
}

İlk sınama düğümün yaprak olup olmadığına bakar: iki çocuk da NULL ise düğüm bir sayıdır ve deger döndürülür. Değilse sol alt ifadenin değeri a'ya, sağ alt ifadenin değeri b'ye hesaplanır. switch, işlece göre a + b, a - b, a * b ya da a / b döndürür. default dalı bölmeyi karşılar. Yordam boş ağaçla çağrılmamalıdır: t NULL ise ilk satır çöker. Bölmede sıfıra bölme denetlenmez; tamsayı bölmesi de kesirli kısmı atar. Yordam her düğüme bir kez uğradığı için zamanı O(n), çağrı yığını nedeniyle belleği O(h)'dir.

Tablo 10.7 (8 / 4) * 3 + 5 ifadesinin hesaplanmasını izler. Ağacın kökü +'dır; sol alt ağacı (8/4) * 3, sağ alt ağacı 5'tir.

Değerlerin oluşma sırası 8, 4, 2, 3, 6, 5, 11'dir. Bu, ağacın kök sonda gezinmesidir: 8 4 / 3 * 5 +. Sunumdaki ifade ağacı bir test programıyla kurulup hesapla çağrıldı ve 11 sonucu alındı. Aynı programla (A + B) * (C − D) ağacı A = 7, B = 3, C = 9, D = 4 değerleriyle hesaplandı: 10 · 5 = 50 bulundu.

10.6Yığınla gezinme

Özyinelemeli gezinme kısa ve okunaklıdır, ama iki durumda yetersiz kalır. Çok derin ağaçlarda çağrı yığını taşabilir. Bazı ortamlarda da (gömülü sistemler, özyinelemeye izin vermeyen kodlama kuralları) özyineleme hiç kullanılamaz. Bu kesim aynı gezinmeleri döngü ve açık bir yığınla yazar. Ardından aynı kalıbı biraz değiştirerek sunumdaki dokuz soruyu çözer: döngüsel kök önde ve kök sonda gezinme, uç düğümleri yazma ve çocuk sayısına göre düğüm seçme.

10.6.1Özyinelemeden döngüye

Her özyinelemeli algoritma döngüsel hâle getirilebilir. Bunun iki yolu vardır. Birincisi, algoritmanın davranışını doğrudan bir döngüyle ifade etmektir; örneğin faktöriyel bir for döngüsüyle hesaplanır. İkincisi, işletim sisteminin özyinelemeli çağrılarda yaptığını programın kendisinin yapmasıdır: dönülecek yerler bir yığına konur ve döngü bu yığından beslenir. Ağaç gezinmesinde ikinci yol izlenir.

Kök ortada gezinmeyi düşünelim. Bir düğüm yazılmadan önce onun sol alt ağacının tamamı yazılmalıdır. Kökten başlayıp sola inerken geçilen her düğüm bekletilir: önce A, sonra B, sonra D. Sola inmek bitince bekleyenlerden hangisi yazılır? En son bekletilen D. D'den sonra B, B'den sonra A gelir. Yani bekleyen düğümlere eklenme sırasının tersiyle erişilir: son eklenen önce çıkar. Bu tam olarak bir yığının (LIFO) tanımıdır. Dersin hocası bu anı “bu bir yığın yapısı!” diye vurgular; yığının buraya dışarıdan eklenmediğini, problemin doğasından kendiliğinden çıktığını gösterir.

Yığına düğümlerin kopyası değil, adresleri konur. Bir düğümün kopyası verisiyle ve iki işaretçisiyle birlikte en az 24 bayt tutar; adresi ise 8 bayttır. Daha önemlisi, kopya yığından çıktıktan sonra da asıl düğümle aynı alt ağaçları gösterir ve gereksizdir: düğüme erişmek için adresi yeterlidir. Yığında aynı anda en fazla ağacın sola doğru derinliği kadar adres bulunur.

10.6.2Yığınla kök ortada gezinme

Yığın için iki küçük yordam yeterlidir. Yığın, agac_gost tipinde bir dizi ve üst indisi tutan bir tamsayıdır:

void yigit_ekle(int *ust, agac_gost p,
                agac_gost y[]) {
  if (*ust == MAX_SIZE - 1) {
    fprintf(stderr, "Yigit dolu\n");
    exit(EXIT_FAILURE);
  }
  y[++*ust] = p;
}
agac_gost yigit_al(int *ust,
                    agac_gost y[]) {
  return (*ust == -1) ? NULL : y[(*ust)--];
}

yigit_ekle yığın doluysa (üst indis MAX_SIZE - 1'e ulaşmışsa) bir ileti yazıp programı sonlandırır. Değilse ++*ust ile üst indisi artırır ve adresi o göze yazar. ++*ust ifadesi ++(*ust) olarak okunur: işaretçinin kendisi değil, gösterdiği tamsayı artar. yigit_al, yığın boşsa NULL döndürür; değilse üstteki adresi döndürür ve (*ust)-- ile üst indisi azaltır. Boş yığında NULL döndürmek bu uygulamada çok uygundur, çünkü yığına hiçbir zaman NULL konmaz; NULL dönüşü “yığın boş” anlamında kullanılabilir. Gezinme yordamı şudur:

void kok_ortada_dolas(agac_gost L) {
  agac_gost yigit[MAX_SIZE];
  int ust = -1;
  for (;;) {
    for (; L; L = L->solcocuk)  // solları at
      yigit_ekle(&ust, L, yigit);
    L = yigit_al(&ust, yigit);  // boşsa NULL
    if (!L) break;
    printf("%c", L->veri);
    L = L->sagcocuk;
  }
}

Kod satır satır şöyle çalışır:

1. agac_gost yigit[MAX_SIZE]; int ust = -1; yerel bir yığın açar. ust = −1 boş yığın demektir.
2. Dış döngü for (;;) sonsuz bir döngüdür; tek çıkışı aşağıdaki break'tir.
3. İç döngü for (; L; L = L->solcocuk), L'den başlayıp sola inebildiği kadar iner ve geçtiği her düğümün adresini yığına ekler. Döngü L NULL olunca biter: en soldaki düğümün sol çocuğuna gelinmiştir.
4. L = yigit_al(&ust, yigit); yığının üstündeki düğümü alır. Bu düğümün sol alt ağacı ya boştur ya da tamamen yazılmıştır.
5. if (!L) break; yığın boşsa gezinme bitmiştir.
6. printf("%c", L->veri); düğümü yazar.
7. L = L->sagcocuk; düğümün sağ alt ağacına geçer. Dış döngünün bir sonraki turu bu alt ağaçta yine sola iner. Sağ alt ağaç boşsa iç döngü hiç dönmez ve yığından bir sonraki düğüm alınır.

Fonksiyon boş ağaçla da doğru çalışır: L NULL ise iç döngü dönmez, yığın boş olduğu için yigit_al NULL verir ve döngü biter. Yığın dolarsa program “Yigit dolu” iletisiyle sonlanır. MAX_SIZE en az ağacın derinliği kadar seçilmelidir; derinlik önceden bilinmiyorsa yığın büyüyen bir diziyle tutulur.

10.6.3Kod izleme

İzleme beş düğümlü A(B(D, E), C) ağacı üzerindedir: A'nın çocukları B ve C, B'nin çocukları D ve E'dir. Tablo 10.8 her adımda yığının içeriğini ve çıktıyı verir. Değerler, yordamın her ekleme ve almada yığını yazdıran bir sürümüyle üretildi.

Çıktı DBEAC'dir ve özyinelemeli kok_ortada_dolas'ın çıktısıyla aynıdır. Yığında aynı anda en çok üç adres bulunmuştur (adım 3): A, B ve D. Bu sayı, kökten en soldaki düğüme giden yoldaki düğüm sayısıdır. Yığının iki rolü vardır. Bir yandan özyinelemeli sürümdeki çağrı yığınının yerini tutar. Ayrıca bir düğümün “solu bitti, sırada kendisi var” anını işaretler: bir düğüm yığından alındığında sol alt ağacı tamamen yazılmıştır.

10.6.4Maliyet ve seçici yazdırma

Zaman. Her düğüm yığına tam bir kez eklenir ve tam bir kez alınır. İç döngünün toplam tur sayısı n, dış döngünün tur sayısı n + 1'dir (sonuncusu break ile biter). Toplam iş 2n yığın işlemiyle orantılıdır: O(n).

Bellek. Yığında aynı anda en çok derinlik kadar adres bulunur: O(h). Ağacın şekli bu sayıyı belirgin biçimde değiştirir. Sola çarpık dört düğümlü zincirde dört adres birden yığına girer. Sağa çarpık zincirde ise her düğüm yığına girer girmez çıkar, çünkü hiçbir düğümün sol çocuğu yoktur; yığında en çok bir adres bulunur ve bellek O(1)'dir. Testte iki zincir için en büyük üst indis sırasıyla 3 ve 0 çıktı.

Yordamın bir güzel yanı, yazdırma satırının değiştirilerek başka işlere uyarlanabilmesidir. printf satırı bir koşula bağlanırsa yalnız seçilen düğümleri yazan bir yordam elde edilir: uç düğümler, tek çocuklular, iki çocuklular. Koşul yazılırken mantık işleçlerine dikkat etmek gerekir. if (!(L->sagcocuk) || !(L->solcocuk)) koşulu “sağ çocuğu yok ya da sol çocuğu yok” demektir. Bu koşul yaprakları ve tek çocuklu düğümleri birlikte, yani en çok bir çocuklu düğümleri yazar. Yalnız yapraklar için “sol çocuğu yok ve sağ çocuğu yok” gerekir: &&.

Dersin amacı küçük modülleri ustaca yazabilmektir; bu yüzden küçük kodlar farklı biçimlerde tekrar tekrar yazılır. Sunumdaki dokuz soru iki kalıptan birine indirgenir: özyinelemeli ya da yığınlı gezinme ile koşullu printf. “Sağdan sola” istenirse solcocuk ile sagcocuk yer değiştirir.

10.6.5Döngüsel kök önde gezinme

Kök önde gezinmenin döngüsel sürümü, kök ortada sürümünün neredeyse aynısıdır. Tek fark yazdırmanın yeridir: düğüm yığına girerken yazılır.

void kok_onde_dolas_d(agac_gost L) {
  agac_gost yigit[MAX_SIZE];
  int ust = -1;
  for (;;) {
    for (; L; L = L->solcocuk) {
      printf("%c", L->veri);   // girerken yaz
      yigit_ekle(&ust, L, yigit);
    }
    L = yigit_al(&ust, yigit);
    if (!L) break;
    L = L->sagcocuk;
  }
}

Sola inen iç döngüde her düğüm önce yazılır, sonra yığına eklenir. Böylece kök, sol alt ağacından önce yazılır. Yığından alınan düğüm artık yazılmıştır; yalnız sağ çocuğuna geçmek için kullanılır. Sonuç V-L-R sırasıdır. A(B(D, E), C) ağacında çıktı ABDEC'dir.

Aynı işin ikinci bir çözümü daha vardır. Kök yığına konur. Her adımda yığından bir düğüm alınır ve yazılır; sonra önce sağ, sonra sol çocuğu (varsa) yığına eklenir. Sol çocuk en son eklendiği için ilk o alınır; bu da sol alt ağacın sağdan önce gezilmesini sağlar.

if (L) yigit_ekle(&ust, L, yigit);
while ((L = yigit_al(&ust, yigit))) {
  printf("%c", L->veri);
  if (L->sagcocuk)
    yigit_ekle(&ust, L->sagcocuk, yigit);
  if (L->solcocuk)
    yigit_ekle(&ust, L->solcocuk, yigit);
}

Bu parça bir fonksiyonun gövdesidir; başında yığın dizisi ve ust = -1 bildirilir. while ((L = yigit_al(&ust, yigit))) koşulundaki çift parantez, atamanın sonucunun bilerek koşul olarak kullanıldığını derleyiciye bildirir; tek parantezle yazılsaydı -Wall bir uyarı verirdi. İki çözüm de A…L ağacında ABCDGHEIJKFL verdi. İkinci çözümde yığında bekleyen düğümler sağ çocuklardır; bir yoldaki her düğüm yığında en çok bir sağ çocuk bırakır, bu yüzden bellek yine O(h)'dir.

10.6.6Döngüsel kök sonda gezinme

Kök sonda gezinmeyi döngüsel yazmak daha zordur. Kök ortada gezinmede bir düğüm yığından alındığında sol alt ağacı bitmişti ve düğüm hemen yazılabiliyordu. Kök sonda gezinmede ise düğüm, sağ alt ağacı da bitmeden yazılamaz. Bir düğüm yığının tepesine iki kez gelir: sol alt ağaçtan dönüldüğünde ve sağ alt ağaçtan dönüldüğünde. Yordam bu iki dönüşü ayırt etmelidir. Bunun için son yazılan düğüm son değişkeninde tutulur. Tepedeki düğümün sağ çocuğu varsa ve son yazılan düğüm o sağ çocuk değilse sağ alt ağaç henüz gezilmemiştir. Önce sağa inilir. Değilse düğüm yazılır ve yığından çıkarılır.

void kok_sonda_dolas_d(agac_gost L) {
  agac_gost yigit[MAX_SIZE], son = NULL, t;
  int ust = -1;
  while (L || ust != -1) {
    if (L) {                     // sola in
      yigit_ekle(&ust, L, yigit);
      L = L->solcocuk;
    } else {
      t = yigit[ust];            // tepeye bak
      if (t->sagcocuk && t->sagcocuk != son)
        L = t->sagcocuk;         // önce sağ
      else {
        printf("%c", t->veri);
        son = yigit_al(&ust, yigit);
      }
    }
  }
}

1. Döngü, gidilecek bir düğüm (L) ya da yığında bekleyen bir düğüm olduğu sürece döner.
2. L boş değilse düğüm yığına eklenir ve sola inilir. Bu dal, özyinelemeli sürümdeki “sol alt ağacı gez” çağrısına karşılık gelir.
3. L boşsa sola inmek bitmiştir. t = yigit[ust] tepedeki düğüme bakar ama onu yığından almaz.
4. t'nin sağ çocuğu varsa ve son o çocuk değilse sağ alt ağaç henüz gezilmemiştir; L sağ çocuğa ayarlanır.
5. Değilse (sağ çocuk yok ya da az önce yazıldı) t'nin iki alt ağacı da bitmiştir. t yazılır, yığından alınır ve son'a kaydedilir.

son değişkeninin neden yalnız sağ çocukla karşılaştırıldığı şöyle açıklanır. Kök sonda sırada bir düğümden hemen önce yazılan düğüm, sağ alt ağacı varsa onun köküdür, yani sağ çocuktur. Sağ alt ağaç boşsa sol çocuktur ya da düğüm yapraktır. Bu yüzden “son yazılan, sağ çocuk mu?” sorusu sağ alt ağacın bitip bitmediğini kesin olarak söyler.

A tepeye iki kez gelir: adım 6'da ve adım 9'da. İlkinde son = B'dir ve sağ alt ağaç henüz gezilmemiştir; ikincisinde son = C'dir ve A yazılır. Zaman yine O(n)'dir: her düğüm bir kez eklenir, bir kez çıkarılır ve tepesine en çok iki kez bakılır. Bellek O(h)'dir. Yordam A…L ağacında GHDJKIECBLFA, A(B(D, E), C) ağacında DEBCA verdi; ikisi de özyinelemeli sürümle aynıdır.

Bir başka çözüm iki yığın kullanır: V-R-L sırası birinci yığınla üretilip ikinci yığına itilir, ikinci yığın boşaltılınca L-R-V çıkar. Bu çözüm daha kolay anlaşılır, ama O(n) ek bellek ister.

10.6.7Uç düğümleri yazmak

Uç düğümleri (yaprakları) soldan sağa yazmak için herhangi bir gezinme kullanılabilir, çünkü yaprakların birbirine göre sırası üç standart gezinmede de aynıdır. Kök ortada gezinmede printf bir koşula bağlanır:

void uc_dugum_yaz(agac_gost L) {
  if (L) {
    uc_dugum_yaz(L->solcocuk);
    if (!L->solcocuk && !L->sagcocuk)
      printf("%c", L->veri);
    uc_dugum_yaz(L->sagcocuk);
  }
}

Koşul, düğümün iki çocuğunun da olmamasıdır. A…L ağacında çıktı GHJKL'dir. Sağdan sola yazmak için yalnız iki özyinelemeli çağrının sırası değiştirilir: önce sağ, sonra sol.

void uc_dugum_yaz_sag(agac_gost L) {        /* SORU 4 */
  if (L) {
    uc_dugum_yaz_sag(L->sagcocuk);
    if (!L->solcocuk && !L->sagcocuk)
      printf("%c", L->veri);
    uc_dugum_yaz_sag(L->solcocuk);
  }
}

Bu yordam aynı ağaçta LKJHG verir; soldan sağa çıktının tersidir. Döngüsel sürümde de aynı yol izlenir. Yığınla kök ortada yordamında printf satırı şu koşula bağlanır:

if (!L->solcocuk && !L->sagcocuk)
  printf("%c", L->veri);

Sağdan sola döngüsel yazmak için yığınlı kodda her yerde solcocuk ile sagcocuk yer değiştirir: yığına sağlar atılır, yığından alınan düğümden sonra sola gidilir.

void uc_dugum_yaz_sag_d(agac_gost L) {      /* SORU 6 */
  agac_gost yigit[MAX_SIZE];
  int ust = -1;
  for (;;) {
    for (; L; L = L->sagcocuk)   // sağları at
      yigit_ekle(&ust, L, yigit);
    L = yigit_al(&ust, yigit);
    if (!L) break;
    if (!L->solcocuk && !L->sagcocuk)
      printf("%c", L->veri);
    L = L->solcocuk;
  }
}

Bu kod bir ters kök ortada gezinmedir (R-V-L). Yapraklar ters sırada çıkar. Dört yordam da test programında aynı ağaçla çalıştırıldı: soldan sağa sürümler GHJKL, sağdan sola sürümler LKJHG verdi. Hepsi O(n) zamanda çalışır; özyinelemeli sürümlerin çağrı yığını ve döngüsel sürümlerin açık yığını O(h) bellek ister.

10.6.8Çocuk sayısına göre seçmek

Son üç soru, düğümleri çocuk durumlarına göre seçer. Yalnız sol çocuğu olan düğümleri yazan özyinelemeli yordam şudur:

void yalniz_sol_yaz(agac_gost L) {           /* SORU 7 */
  if (!L) return;
  if (L->solcocuk && !L->sagcocuk)
    printf("%c", L->veri);
  yalniz_sol_yaz(L->solcocuk);
  yalniz_sol_yaz(L->sagcocuk);
}

Bu yordam kök önde biçimindedir: koşulu sınayıp gerekiyorsa yazar, sonra iki alt ağaca iner. Yordamın başındaki if (!L) return; erken dönüşü, if (L) { … } bloğunun yerini tutar. L->solcocuk && !L->sagcocuk koşulu “sol çocuğu var ve sağ çocuğu yok” diye okunur; !L->sagcocuk, “sağ çocuk işaretçisi NULL” demektir. Öteki iki soru yalnız koşulu değiştirir. Yalnız sağ çocuğu olan düğümler için koşul !L->solcocuk && L->sagcocuk'tur. İki çocuklu düğümler için koşul L->solcocuk && L->sagcocuk'tur:

void iki_cocuklu_yaz(agac_gost L) {         /* SORU 9 */
  if (!L) return;
  if (L->solcocuk && L->sagcocuk)
    printf("%c", L->veri);
  iki_cocuklu_yaz(L->solcocuk);
  iki_cocuklu_yaz(L->sagcocuk);
}

A…L ağacında yalnız sol çocuklu tek düğüm F'dir; yalnız sağ çocuklu düğümler B ve E'dir; iki çocuklu düğümler kök önde sırayla A, C, D ve I'dır. Sayıların tutarlılığı Teorem 10.2 ile denetlenebilir: ağaçta 5 yaprak, 3 tek çocuklu ve 4 iki çocuklu düğüm vardır; 5 = 4 + 1 ve 5 + 3 + 4 = 12. Bütün bu yordamlar “ağacı gez, koşul sağlanıyorsa yaz” kalıbının örnekleridir. Gezinmenin türü yalnız çıktının sırasını belirler; seçilen düğümlerin kümesi gezinmeden bağımsızdır.

10.7Düzey düzey gezinme

Kök önde, kök ortada ve kök sonda gezinmeler ağacın derinliklerine iner: bir dala girdiklerinde o dalı bitirmeden yan dala geçmezler. Bazı işlerde ise düğümlere kökten uzaklıklarına göre uğramak gerekir: önce kök, sonra 2. düzeydeki bütün düğümler soldan sağa, sonra 3. düzey ve böyle devam eder. Buna düzey sırası (level-order) gezinme denir. Bu kesim aynı soruyu iki yöntemle çözer ve ikinci yöntemin kuyrukla neden doğal olarak örtüştüğünü gösterir.

10.7.1Düzey listeleriyle

İlk yöntem, gezinme sırasının bir önemi olmadığını fark etmeye dayanır. Ağaç herhangi bir gezinmeyle gezilir ve her düğüm kendi düzeyinin listesinin sonuna eklenir. Gezinme bitince listeler 1. düzeyden başlayarak sırayla yazılır. Gezinme yordamına düğümün düzeyini bir parametre olarak vermek yeterlidir: kök 1 ile çağrılır, her çocuk ebeveyninin düzeyinin bir fazlasıyla. Listeler için bir dizi bağlı liste tutulur; dizinin i. gözü i. düzeyin listesinin başını gösterir.

Listelere ekleme her zaman sona yapıldığı için her listedeki düğümlerin sırası, gezinmenin onları bulma sırasıdır. Soldan sağa sıranın korunması için solun sağdan önce gezildiği bir gezinme (kök önde, kök ortada ya da kök sonda) seçilmelidir. Aynı düzeydeki iki düğümden soldaki, bu üç gezinmede de önce bulunur. Şekil 10.17'deki ağaçta listeler A; B, C; D, E, F, G; H olur ve art arda yazılınca ABCDEFGH çıkar.

Maliyet. Her düğüm üç kez ele alınır: gezinmede bulunur, listeye eklenir, listeden yazılır. Liste sonuna ekleme bir son işaretçisiyle O(1)'dir; toplam zaman 3n = O(n) olur. Bellek, listelerin n düğümü, düzey başları dizisinin h gözü ve gezinmenin O(h) çağrı yığınıdır: O(n + h). h en çok n olduğu için bu O(n)'dir.

10.7.2Kuyrukla

İkinci yöntem ek listeler kurmadan aynı sırayı üretir. Düzey düzey yazmada bir düğümün çocukları, aynı düzeydeki öteki düğümlerin hepsinden sonra yazılmalıdır. Kök yazılınca çocukları B ve C sıraya girer. B yazılınca B'nin çocukları D ve E de sıraya girer, ama C'nin arkasına; çünkü C, D'den ve E'den önce yazılmalıdır. Sıraya önce giren önce çıkar: bu kuyruğun (FIFO) tanımıdır. Derinlemesine gezinmede yığın kullanmak problemin doğasından geliyordu; düzey düzey gezinmede de kuyruk kullanmak aynı biçimde zorunludur.

Algoritma şöyledir. Kök kuyruğa konur. Kuyruk boşalana kadar her adımda kuyruğun önünden bir düğüm alınır, yazılır ve çocukları (varsa önce sol, sonra sağ) kuyruğun arkasına eklenir. Ağaç boş gelebileceği için yordamın başında if (!L) return; sınaması vardır. Kuyruğa da düğümlerin kopyaları değil adresleri konur. Kuyruk, dairesel bir dizi olarak gerçeklenir:

void kuyruk_ekle(int on, int *arka,
                 agac_gost p, agac_gost k[]) {
  *arka = (*arka + 1) % MAX_SIZE;
  if (*arka == on) {            /* dolu */
    fprintf(stderr, "Kuyruk dolu\n");
    exit(EXIT_FAILURE);
  }
  k[*arka] = p;
}
agac_gost kuyruk_al(int *on, int arka,
                    agac_gost k[]) {
  if (*on == arka) return NULL; /* boş */
  *on = (*on + 1) % MAX_SIZE;
  return k[*on];
}

Dairesel kuyrukta iki indis tutulur. arka son eklenen öğenin gözünü, on ise ilk öğenin bir öncesindeki gözü gösterir. İkisi eşitse kuyruk boştur. kuyruk_ekle, arka'yı bir ilerletir; dizinin sonuna gelinmişse % MAX_SIZE ile başa döner. İlerletilen arka on'a eşit çıkarsa kuyruk doludur: bir öğe daha eklenseydi boş kuyrukla dolu kuyruk ayırt edilemezdi. Bu yüzden MAX_SIZE gözlü dizide en çok MAX_SIZE - 1 öğe tutulur. kuyruk_al, kuyruk boşsa NULL döndürür; değilse on'u ilerletir ve o gözdeki adresi döndürür. on değeri ile değiştirilmesi gereken indis adresle verilir: kuyruk_ekle arka'yı, kuyruk_al on'u değiştirir. Düzey düzey gezinme yordamı şudur:

void duzey_dolas(agac_gost L) {
  agac_gost kuyruk[MAX_SIZE];
  int on = 0, arka = 0;
  if (!L) return;              // ağaç boş olabilir
  kuyruk_ekle(on, &arka, L, kuyruk);
  while ((L = kuyruk_al(&on, arka, kuyruk))) {
    printf("%c", L->veri);
    if (L->solcocuk)
      kuyruk_ekle(on, &arka, L->solcocuk, kuyruk);
    if (L->sagcocuk)
      kuyruk_ekle(on, &arka, L->sagcocuk, kuyruk);
  }
}

while ((L = kuyruk_al(&on, arka, kuyruk))) satırı hem kuyruktan düğüm alır hem de kuyruğun boşalıp boşalmadığını sınar: kuyruk_al NULL döndürünce döngü biter. Döngü gövdesi alınan düğümü yazar ve var olan çocuklarını arkaya ekler. NULL çocuklar kuyruğa hiç konmaz; böylece kuyruktan çıkan NULL yalnız “kuyruk boş” anlamına gelir.

10.7.3Kod izleme

Tablo 10.10 A…H ağacında kuyruğun durumunu izler. Kuyruk dizisinin 0. gözü hiç kullanılmaz, çünkü ilk ekleme arka'yı 0'dan 1'e ilerletir. Değerler, yordamın her almada on ve arka'yı yazan bir sürümüyle üretildi.

Kuyruk içeriğine dikkat edilirse, herhangi bir anda kuyrukta en çok iki ardışık düzeyin düğümleri bulunur: bir düzeyin henüz yazılmamış düğümleri ve onların önündekilerin çocukları. 4. adımdan sonra kuyrukta 3. düzeyden E, F, G ve 4. düzeyden H vardır. Aynı yordam A…L ağacında ABFCLDEGHIJK verdi. Boş ağaçla çağrıldığında hiçbir şey yazmadan döndü.

10.7.4Maliyet: yığın ile kuyruk

Zaman. Her düğüm kuyruğa bir kez girer ve bir kez çıkar: 2n = O(n).

Bellek. Kuyrukta aynı anda en çok bir düzeyin genişliği (w) kadar düğüm bulunur, artı sonraki düzeyden birkaç düğüm. Bu yüzden ek bellek O(w)'dir. Tam ağaçta son düzeyde yaklaşık n/2 düğüm vardır ve bellek O(n) olur. Çarpık ağaçta her düzeyde tek düğüm bulunur ve kuyrukta hiçbir zaman birden çok düğüm olmaz: O(1). Derinlemesine gezinmelerde durum tersidir: dengeli ağaçta yığın O(lg n), çarpık ağaçta O(n) bellek ister. Tablo 10.11 iki gezinme ailesini karşılaştırır.

Tablodaki karşıtlık önemlidir: O(lg n) bellek sınırı kuyruklu düzey sırası gezinme için değil, dengeli ağaçta yığınlı derinlemesine gezinmeler için geçerlidir. Aynı fikirler çizgelerde de karşılığını bulur. Kuyrukla yapılan düzey düzey gezinme, çizgelerde genişlik öncelikli arama (breadth-first search, BFS) adını alır. Kuyruk yerine yığın kullanılınca algoritma derinlik öncelikli aramaya (depth-first search, DFS) döner. Çizgede bir düğüme birden çok yoldan ulaşılabildiği için orada ayrıca ziyaret işaretleri tutulur.

10.8Diğer ağaç yordamları

Gezinme kalıbı yalnız yazdırmaya değil, ağaç üzerindeki hemen her işe uygulanır. Bu kesimdeki dört yordam aynı iskeleti kullanır: boş ağacı ele al, kökte bir iş yap, iki alt ağaç için kendini çağır. Fark, kökteki işin ne olduğunda ve özyinelemeli çağrıların sonuçlarının nasıl birleştirildiğindedir.

10.8.1Ağacı kopyalamak

Bir ağacın kopyası, aynı şekilde ve aynı verilerle, ama tamamen yeni düğümlerden kurulmuş bir ağaçtır. Kopyada asıl ağaçla ortak tek bir düğüm bile bulunmamalıdır; yoksa kopyada yapılan bir değişiklik asıl ağacı da bozar. Yordam özyinelemeli olarak şöyle tanımlanır: boş ağacın kopyası boş ağaçtır; boş olmayan ağacın kopyası, yeni bir kökün altına iki alt ağacın kopyalarının bağlanmasıyla elde edilir.

agac_gost agac_kopyala(agac_gost L) {
  if (!L) return NULL;
  agac_gost T = malloc(sizeof *T);
  if (!T) { perror("malloc"); exit(1); }
  T->solcocuk = agac_kopyala(L->solcocuk);
  T->sagcocuk = agac_kopyala(L->sagcocuk);
  T->veri = L->veri;
  return T;
}

1. if (!L) return NULL; boş ağacın kopyasını döndürür. Bu, yaprakların çocukları için yapılan çağrılarda da devreye girer.
2. agac_gost T = malloc(sizeof *T); yeni kök için yer ayırır. Ayırma başarısızsa perror bir hata iletisi yazar ve program sonlanır. Burada ogeal yerine doğrudan malloc ve denetim kullanılmıştır; iki biçim de doğrudur.
3. T->solcocuk = agac_kopyala(L->solcocuk); sol alt ağacın kopyasını kurar ve yeni kökün sol bağına yazar.
4. T->sagcocuk = agac_kopyala(L->sagcocuk); aynı işi sağ alt ağaç için yapar.
5. T->veri = L->veri; veriyi kopyalar ve return T; yeni kökün adresini çağırana verir.

Veri, iki çocuk kopyalandıktan sonra yazılır; yordam ağacı kök sonda biçiminde gezer. Kopya aşağıdan yukarı kurulur: önce yapraklar, sonra onların ebeveynleri. Dersin hocası bu yordamın aşağıdan yukarı (bottom-up) çalıştığını, yukarıdan aşağı (top-down) da yazılabileceğini belirtir. Satırların yeri değiştirilerek kök önde ya da kök ortada biçimine kolayca geçilir: örneğin T->veri = L->veri; satırı malloc'un hemen arkasına alınırsa veri, çocuklardan önce kopyalanır. Sonuç değişmez. Önerilen çalışma yolu, kodu yazmadan önce tahtadaki gibi kâğıt üzerinde küçük bir ağaçla çağrıları çizmek ve yordamın özyinelemeli olarak nasıl çözüldüğünü görmektir.

A(B, C) ağacının kopyalanması on altı adımda biter: üç düğüm için üç malloc, dört NULL çağrısı, üç veri kopyası ve dönen adreslerin bağlara yazılması. Test programında kopyanın kök önde ve kök ortada çıktıları asıl ağaçla aynı çıktı (ABC ve BAC); kopyanın düğüm adreslerinin asıl ağaçtakilerden farklı olduğu da denetlendi. A…L ağacının kopyası esitmi ile asıl ağaçla karşılaştırıldı ve eşit bulundu. Maliyet: zaman O(n), çağrı yığını O(h); kopyanın kendisi de n düğüm yer kaplar. Kopya artık bağımsız bir ağaçtır ve işi bitince agac_sil ile ayrıca silinmelidir.

10.8.2Eş biçimlilik

İki ikili ağaç, aynı şekle sahipse ve karşılıklı düğümlerdeki veriler aynıysa eşittir. Yalnız şekil aranıyorsa ağaçlara eş biçimli (isomorphic) denir. Özyinelemeli tanım şöyledir. İki ağaç da boşsa eşittir. Biri boş, öteki doluysa eşit değildir. İkisi de doluysa, kökteki veriler eşit, sol alt ağaçlar eşit ve sağ alt ağaçlar eşit olmalıdır.

int esitmi(agac_gost L, agac_gost T) {
  return (!L && !T) ||
         (L && T && L->veri == T->veri
          && esitmi(L->solcocuk, T->solcocuk)
          && esitmi(L->sagcocuk, T->sagcocuk));
}

Fonksiyon tek bir return ifadesinden oluşur. ||'nin sol tarafı, iki ağacın da boş olduğu durumu yakalar ve 1 verir. Sağ taraf ise && ile bağlanmış beş koşuldur: L dolu, T dolu, veriler eşit, sol alt ağaçlar eşit, sağ alt ağaçlar eşit. C'nin && ve || işleçleri kısa devre yapar: sonucu belli olunca sağ tarafı hesaplamaz. Bu iki yarar sağlar. Birincisi, L ya da T NULL ise L->veri'ye hiç erişilmez; L && T sınaması bir koruyucu görevi görür. İkincisi, ilk farkta özyineleme durur ve geri kalan düğümlere bakılmaz. Yalnız biçim benzerliği isteniyorsa L->veri == T->veri koşulu kaldırılır.

İzlemede toplam beş çağrı yapılır: (A, A), (B, B), iki kez (NULL, NULL) ve (C, D). C ile D'nin çocuklarına hiç bakılmaz. Maliyet. En kötü durumda, ağaçlar eşitse, iki ağacın bütün düğümleri karşılaştırılır. Ağaçlar farklıysa yordam ilk farkta durur; iki ağacın küçüğünün düğüm sayısını aşan karşılaştırma yapılmaz. Zaman O(min(n₁, n₂)), çağrı yığını O(h)'dir.

Dersin hocası burada bir karşıtlığa dikkat çeker: ikili ağaçların eş biçimli olup olmadığını denetlemek bu kadar kolaydır, oysa iki genel çizgenin eş biçimliliğini bulmak çok zor bir problemdir. Farkın nedeni ikili ağaçtaki sıralı yapıdır. Her düğümün sol ve sağ çocuğu belli olduğu için hangi düğümün hangisiyle eşleşeceği kendiliğinden bellidir. Çizgede düğümlerin bir sırası yoktur ve olası eşleşmelerin sayısı düğüm sayısının faktöriyeli kadar büyür.

10.8.3Erken dönüşlü yazım

Aynı yordam tek bir uzun ifade yerine, her koşulu ayrı bir satırda sınayıp sonucu belli olunca hemen dönen biçimde de yazılabilir. Bu yazıma erken dönüşlü (guard) yazım denir:

int esitmi2(agac_gost L, agac_gost T) {
  if (L == NULL || T == NULL)
    return L == T;          /* ikisi de NULL mı? */
  if (L->veri != T->veri)
    return 0;
  if (!esitmi2(L->solcocuk, T->solcocuk))
    return 0;
  return esitmi2(L->sagcocuk, T->sagcocuk);
}

İlk sınama iki ağaçtan en az biri boşken çalışır. Bu durumda return L == T; ifadesi ikisinin de boş olup olmadığını söyler: biri NULL iken L == T ancak öteki de NULL ise doğrudur. İkinci sınama verileri karşılaştırır. Üçüncüsü sol alt ağaçları karşılaştırır ve eşit değilse hemen 0 döndürür. Son satır sonucu doğrudan sağ alt ağaçların karşılaştırmasına bırakır. Davranış esitmi ile aynıdır; testte iki yordam bütün ağaç çiftlerinde aynı sonuçları verdi.

İki yazımda da her özyinelemeli çağrının dönüş değeri kullanılır. Bu, özyinelemeli fonksiyon yazarken sık atlanan bir noktadır. esitmi2(L->solcocuk, T->solcocuk); satırı sonucunu bir yere aktarmadan yazılsaydı hesaplanan değer kaybolurdu ve fonksiyon yalnız köklerin verisine bakan bir sınamaya dönerdi. Hocanın ifadesiyle, “benimki güzel çalışıyor ama geri dönmüyor” diyen öğrenci özyinelemeli algoritma yazmayı henüz öğrenmemiştir: her çağrı bir değer döndürmeli ve çağıran o değeri kullanmalıdır.

10.8.4Sol ve sağ çocukları değiştirmek

Bir ağacın aynadaki görüntüsü, her düğümün sol ve sağ alt ağaçlarının yer değiştirmesiyle elde edilir. Yordam verileri değil, yalnız işaretçileri takas eder:

#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
void cocukdegistir(agac_gost L) {
  agac_gost p;
  if (L) {
    SWAP(L->solcocuk, L->sagcocuk, p);
    cocukdegistir(L->solcocuk);
    cocukdegistir(L->sagcocuk);
  }
}

SWAP makrosu üç argüman alır: takas edilecek iki değer ve geçici bir değişken. ((t) = (x), (x) = (y), (y) = (t)) virgül işleciyle üç atamayı tek bir ifadede yapar: x'in değeri t'ye saklanır, y x'e yazılır, saklanan değer y'ye yazılır. Makro parametrelerinin parantez içinde kullanılması, L->solcocuk gibi karmaşık argümanlarla da doğru açılmasını sağlar. Yordamda geçici değişken agac_gost p'dir. Kök takas edilir, sonra iki alt ağaç için yordam yinelenir. Takas, çağrılardan önce yapıldığı için yordam kök önde biçimindedir.

Takastan sonra L->solcocuk eski sağ alt ağaçtır. Bu yüzden A(B(D), C) ağacında yordam önce C'ye, sonra B'ye iner. Tablo 10.13 adımları verir.

Sonuçta kök ortada sıra DBAC'den CABD'ye döner. Ayna ağacın kök ortada sırası her zaman asıl ağacınkinin tersidir, çünkü ayna her düğümde L-V-R sırasını R-V-L sırasına çevirir. Yordam her düğüme bir kez uğrar ve her düğümde sabit sayıda atama yapar: zaman O(n), bellek O(h). Hiçbir düğüm ayrılmaz ya da silinmez; veriler yerinde kalır, yalnız işaretçiler yer değiştirir. Yordam iki kez uygulanırsa ağaç ilk hâline döner.

10.8.5Takasın yeri

SWAP satırı iki özyinelemeli çağrının önüne, arasına ya da arkasına konabilir. Önde ve arkada iken sonuç aynıdır; arada iken sonuç bozulur. Bunu görmek için bütün sağ alt ağaçları tek kollu olan sağa çarpık bir zincir kullanılır: A'nın sağında B, B'nin sağında C, C'nin sağında D. Şekil 10.21 dört durumu gösterir.

• Takas önde (kök önde): A'da sol ve sağ yer değiştirir; B artık A'nın solundadır ve yordam B'ye iner. B'de de takas olur ve C sola geçer. Sonuç sola çarpık bir zincirdir: tam ayna.
• Takas arkada (kök sonda): Önce iki alt ağaç kendi içinde aynalanır, sonra kökte takas yapılır. Her alt ağaç aynalandıktan sonra yer değiştirdiği için sonuç yine tam aynadır.
• Takas arada (kök ortada): A'da önce sol alt ağaç işlenir; sol boş olduğu için hiçbir şey olmaz. Sonra takas yapılır ve B sola geçer. Ardından “sağ” alt ağaç işlenir; ama sağ artık boştur. B'nin alt ağacına hiç inilmez. Sonuçta yalnız kök takaslanmıştır.

Üç sürüm test programında çalıştırıldı. Takas önde ve arkadayken kök ortada sıra DCBA çıktı ve iki ağaç esitmi ile eşit bulundu. Takas aradayken kök ortada sıra BCDA çıktı. Genel ders şudur: yordamın her çağrısı, işleyeceği alt ağacı çağrı anındaki işaretçilerden okur. Takas, bu işaretçileri çağrıların arasında değiştirirse ikinci çağrı yanlış alt ağaca gider.

10.9Gezinmelerden ağacı yeniden kurmak

Bir ağacın tek bir gezinme çıktısı ağacı belirlemez. Örneğin kök ortada çıktısı AB olan iki ağaç vardır: A kök ve B sağ çocuk ya da B kök ve A sol çocuk. İki gezinme birlikte verilince ise çoğu durumda ağaç tek olarak bulunur. Bu, sık sorulan bir sınav sorusudur. Sunumdaki soruda kök ortada sıra C M D A K N B F E G, kök sonda sıra D A N F E B K M G C'dir. Bu sıraları veren ikili ağaç çizilecektir.

Yöntem iki gözleme dayanır. Kök sonda sırada her alt ağacın kökü o alt ağacın en son yazılan düğümüdür. Kök ortada sırada bir düğümün solundaki harfler onun sol alt ağacını, sağındaki harfler sağ alt ağacını oluşturur. Kök sonda sıra sondan başa okunur. Her harf bir alt ağacın köküdür; kök ortada sıra bu harfin solunu ve sağını ayırır. Sondan başa okumada önce sağ alt ağacın, sonra sol alt ağacın kökleri gelir, çünkü kök sonda sırada sağ alt ağaç kökten hemen öncedir.

Tablodaki sıra, kök sonda dizgesinin sondan başa okunuşudur: C, G, M, K, B, E, F, N, A, D. Sunum aynı ağacı adım adım çizerken K'nın sol alt ağacını (D ve A) sağ alt ağacından önce yerleştirir; iki sıra da aynı ağacı verir. Şekil 10.22 ara bir anı ve sonucu gösterir.

Sonuç ağacı test programıyla denetlendi: kurulan ağacın kök ortada gezinmesi CMDAKNBFEG, kök sonda gezinmesi DANFEBKMGC verdi. Yöntem doğrudan özyinelemeli bir C fonksiyonuna dönüşür:

/* ko: kök ortada, ks: kök sonda dizgesi; ikisi de n harf */
agac_gost yeniden_kur(const char *ko, const char *ks, int n) {
  if (n == 0) return NULL;
  agac_gost T = ogeal();
  T->veri = ks[n - 1];               /* kök sonda: kök en sonda */
  int i = 0;
  while (ko[i] != T->veri) i++;      /* kök ortada kökü bul */
  T->solcocuk = yeniden_kur(ko, ks, i);
  T->sagcocuk = yeniden_kur(ko + i + 1, ks + i, n - i - 1);
  return T;
}

ko kök ortada, ks kök sonda dizgesidir; ikisi de aynı alt ağacın n harfini tutar. Kök, ks'nin son harfidir. Kök ortada dizgede kökün konumu i bulunur: solundaki i harf sol alt ağaçtır, sağındaki n - i - 1 harf sağ alt ağaçtır. Kök sonda dizgede de sol alt ağaç ilk i harfi, sağ alt ağaç onu izleyen n - i - 1 harfi kaplar. Sol alt ağaç (ko, ks, i) ile kurulur. Sağ alt ağaç (ko + i + 1, ks + i, n - i - 1) ile kurulur. İşaretçi aritmetiği alt dizgelerin kopyalanmasını önler: ko + i + 1, dizgenin i + 1. karakterinden başlayan parçasıdır. Fonksiyon harflerin birbirinden farklı olduğunu ve iki dizgenin aynı ağaca ait olduğunu varsayar. Her düğüm için kök ortada dizgede doğrusal bir arama yapılır; çarpık ağaçta toplam zaman O(n²), dengeli ağaçta O(n lg n) olur.

Kök önde ve kök ortada sıraları da ağacı tek olarak belirler; tek fark kökün kök önde sıranın ilk harfi olmasıdır. Kök önde ve kök sonda sıraları ise genellikle belirlemez. A kök ve B tek çocuk olan iki ağacı düşünelim: birinde B soldadır, ötekinde sağdadır. İkisinin de kök önde sırası AB, kök sonda sırası BA'dır. Bu iki gezinme kökü ve çocuğu bulur, ama tek çocuğun hangi yanda olduğunu söylemez. Kök ortada sıra ise tam bu bilgiyi taşır: sol alt ağaç kökten önce, sağ alt ağaç kökten sonra yazılır.

10.10Karmaşıklık özeti

Tablo 10.15 bu nottaki bütün yordamların zaman ve ek bellek maliyetlerini toplar. n düğüm sayısı, h derinliktir; lg n ≤ h ≤ n (dengeli ↔ çarpık). Derinlik bu derste düzey sayısıyla ölçülür.

Bütün düğümlere dokunan her yordam Ω(n) zaman ister; buradaki yordamların hepsi bu alt sınıra ulaşır. Bellekte belirleyici olan ağacın şeklidir: dengeli ağaç birkaç düzine çerçeveyle, çarpık ağaç n çerçeveyle gezilir.

10.11Sık yapılan hatalar

1. L->veri'ye NULL denetimi yapmadan erişmek. Ağaç işaretçisi NULL gelebilir: ağaç boş olabilir ya da özyineleme bir yaprağın boş çocuğuna inmiş olabilir. Her ağaç yordamının ilk sorusu “ağaç boş mu?” olmalıdır.
2. Dizi gösteriminde 0'dan başlayıp 1 tabanlı formülleri kullanmak. 2i ve 2i + 1 formülleri kök 1. gözdeyken doğrudur. Kök 0. gözdeyse formüller 2i + 1, 2i + 2 ve ⌊(i − 1)/2⌋ olur.
3. Yığına ya da kuyruğa düğümün kopyasını koymak. Düğüme erişmek için adresi yeter. Kopya hem daha çok yer tutar hem de gereksiz bir bellek ayırma ya da yapı kopyası demektir.
4. Özyinelemeli çağrının dönüş değerini kullanmamak ya da return'den sonra iş yapmaya çalışmak. Değer döndüren her özyinelemeli çağrının sonucu ya döndürülmeli ya da bir değişkene alınmalıdır.
5. Uç düğüm koşulunda && yerine || yazmak. “Çocuğu yok” iki çocuğun da olmaması demektir. || ile tek çocuklu düğümler de yazılır.
6. Derece ile derinliği, düzey 1 ile derinlik 0 tanımlarını karıştırmak. Derece genişliği, derinlik uzunluğu ölçer. Kökün düzeyi bu derste 1'dir; başka kaynaklarda 0 olabilir ve formüller buna göre bir kayar.
7. Ağacı silerken kökü önce bırakmak. free(L)'den sonra L->solcocuk'u okumak tanımsız davranıştır. Silme kök sonda sırayla yapılmalıdır.

10.12Alıştırmalar ve çözümleri

Sunumun alıştırma slaytındaki altı soru aşağıda çözümleriyle verilmiştir. Kod içeren çözümler derlenip küçük test programlarıyla çalıştırıldı; ağaç çizimi isteyen çözümler bir Python betiğiyle denetlendi.

10.12.1Yaprak sayısı eşitliği

Soru. n₀ = n₂ + 1 eşitliğini kanıtlamak.

Çözüm. Düğümler derecelerine göre sayılırsa n = n₀ + n₁ + n₂ olur. Kök dışındaki her düğüme yukarıdan bir kenar girer; kenar sayısı n − 1'dir. Aynı kenarlar çıktıkları düğümlere göre sayılırsa n − 1 = n₁ + 2n₂ bulunur. İki eşitlik taraf tarafa çıkarılınca 1 = n₀ − n₂ kalır. Kanıtın ayrıntısı Teorem 10.2'de verilmiştir. A…L ağacında n₀ = 5, n₁ = 3, n₂ = 4 sayıldı; eşitlik sağlanır.

10.12.2Bir ifade ağacının üç gezinmesi

Soru. (A + B) * (C − D) ifadesinin ağacını çizip üç gezinmeyi yazmak.

Çözüm. En son uygulanan işleç *'dır; kök odur. Sol alt ağacın kökü +, çocukları A ve B'dir. Sağ alt ağacın kökü -, çocukları C ve D'dir. Kök önde gezinme * + A B - C D verir. Kök ortada gezinme A + B * C - D, kök sonda gezinme A B + C D - * verir. Kök ortada çıktıda parantezler kaybolmuştur; ifadeyi doğru okumak için her alt ağaç paranteze alınmalıdır. Ön-işleç ve son-işleç çıktıları parantezsiz de tek anlamlıdır.

10.12.3Düğüm sayısı

Soru. Ağacın düğüm sayısını döndüren int say(agac_gost L) yordamını yazmak.

int say(agac_gost L) {           /* düğüm sayısı */
  return L ? 1 + say(L->solcocuk) + say(L->sagcocuk) : 0;
}

Çözüm. Boş ağaçta düğüm yoktur: 0. Boş olmayan ağaçta kök için 1, iki alt ağaçtaki düğümler için iki özyinelemeli çağrı toplanır. Koşul işleci (? :) iki durumu tek bir return ifadesinde birleştirir. Yordam kök sonda biçimindedir: kökün değeri, alt ağaçların değerleri bilindikten sonra hesaplanır. Zaman O(n), bellek O(h)'dir. Test programında A…L ağacı için 12, A(B(D), C) için 4, boş ağaç için 0 döndü. Aynı kalıpla yaprak sayısı (L yaprak ise 1, değilse iki alt ağacın toplamı) ve derinlik de yazılır.

10.12.4Kök önde ve kök ortada sıradan ağaç

Soru. Kök önde sırası A B D E C F, kök ortada sırası D B E A F C olan ağacı çizmek.

Çözüm. Kök önde sıranın ilk harfi köktür: A. Kök ortada sırada A'nın solunda D, B, E; sağında F, C vardır. Sol alt ağacın kök önde sırası B, D, E'dir; kökü B'dir. Kök ortada sırada B'nin solunda D, sağında E vardır: B(D, E). Sağ alt ağacın kök önde sırası C, F'dir; kökü C'dir. Kök ortada sırada F, C'nin solundadır: C(F, —). Ağaç A(B(D, E), C(F, —)) olur. Bu yöntem Tablo 10.14'teki yöntemin aynısıdır; tek fark kökün baştan okunmasıdır.

10.12.5Düzeyleri sağdan sola yazmak

Soru. Ağacın düzeylerini sırayla, ama her düzeyi sağdan sola yazan kuyruklu yordamı yazmak.

void duzey_dolas_sag(agac_gost L) {         /* düzeyler sağdan sola */
  agac_gost kuyruk[MAX_SIZE];
  int on = 0, arka = 0;
  if (!L) return;
  kuyruk_ekle(on, &arka, L, kuyruk);
  while ((L = kuyruk_al(&on, arka, kuyruk))) {
    printf("%c", L->veri);
    if (L->sagcocuk)
      kuyruk_ekle(on, &arka, L->sagcocuk, kuyruk);
    if (L->solcocuk)
      kuyruk_ekle(on, &arka, L->solcocuk, kuyruk);
  }
}

Çözüm. duzey_dolas'tan tek farkı, çocukların kuyruğa ekleniş sırasıdır: önce sağ, sonra sol çocuk eklenir. Aynı düzeydeki düğümler kuyruğa sağdan sola girer ve aynı sırayla çıkar. A…H ağacında çıktı ACBGFEDH oldu: 1. düzey A, 2. düzey C B, 3. düzey G F E D, 4. düzey H. Maliyet duzey_dolas ile aynıdır.

10.12.6İki ağaç birbirinin aynası mı?

Soru. İki ağacın birbirinin aynası olup olmadığını denetleyen yordamı yazmak.

int ayna_mi(agac_gost L, agac_gost T) {
  return (!L && !T) ||
         (L && T && L->veri == T->veri
          && ayna_mi(L->solcocuk, T->sagcocuk)
          && ayna_mi(L->sagcocuk, T->solcocuk));
}

Çözüm. esitmi'den tek farkı çapraz karşılaştırmadır: L'nin solu T'nin sağıyla, L'nin sağı T'nin soluyla karşılaştırılır. A(B(D), C) ağacı cocukdegistir ile aynalandıktan sonra asıl ağaçla karşılaştırıldı ve 1 döndü. Bir ağacın kendisiyle karşılaştırılması ise 0 verdi, çünkü ağaç simetrik değildir. Zaman O(min(n₁, n₂)), bellek O(h)'dir.

10.13Özet

• Ağaç, bir kökten başlayıp ayrık alt ağaçlara bölünen hiyerarşik yapıdır. Kök dışındaki her düğümün tek ebeveyni vardır; bu yüzden ağaçta döngü yoktur ve n düğümde n − 1 kenar bulunur.
• Temel terimler: ebeveyn, çocuk, kardeş, ata, soy, derece, yaprak, iç düğüm, düzey ve derinlik. Bu derste kök 1. düzeydedir ve derinlik en büyük düzeydir; CLRS gibi kaynaklar kökü 0 sayar.
• İkili ağaçta i. düzeyde en çok 2ⁱ⁻¹, k derinlikli ağaçta en çok 2^k − 1 düğüm vardır. ⌈lg(n + 1)⌉ ≤ k ≤ n; alt sınıra tam ağaç, üst sınıra çarpık ağaç ulaşır.
• n₀ = n₂ + 1'dir. Bağlı gösterimde 2n işaretçinin n + 1'i NULL'dır.
• Tam ve sabit ağaç diziyle (1 tabanlı, ⌊i/2⌋, 2i, 2i + 1), şekli değişen ağaç agac_gost bağlarıyla tutulur. Çarpık ağaç dizide 2^k − 1 göz ister.
• Genel ağaç, sol çocuk – sağ kardeş gösterimiyle ikili ağaca çevrilir; kök önde sıra korunur, ikili ağacın kök ortada sırası genel ağacın kök sonda sırasına eşittir.
• Kök önde, kök ortada ve kök sonda gezinmeler aynı özyinelemeli iskelettir; 2n + 1 çağrı yapar, O(n) zaman ve O(h) bellek ister. İfade ağacı kök sonda gezinmeyle hesaplanır.
• Gezinmeler açık bir yığınla döngüsel yazılır; yığına düğüm adresleri konur. Kök sonda sürümde son yazılan düğüm tutulur.
• Düzey düzey gezinme kuyruk ister; belleği en geniş düzeyle orantılıdır.
• Kopyalama, eş biçimlilik, aynalama, sayma ve silme “gez ve işle” kalıbının örnekleridir. Silme ve kopyalama kök sonda sırayla yapılır.
• Kök ortada sıra ile kök sonda ya da kök önde sıra birlikte ağacı tek olarak belirler; kök önde ile kök sonda sıra belirlemez.

10.14Kavram listesi

• ağaç tree
• kök root
• alt ağaç subtree
• çizge graph
• ebeveyn parent
• çocuk child
• kardeş sibling
• ata ancestor
• soy descendant
• derece degree
• yaprak leaf
• iç düğüm internal node
• düzey level
• derinlik depth
• yükseklik height
• ikili ağaç binary tree
• çarpık ağaç skewed tree
• tam dolu ikili ağaç full binary tree
• tam ikili ağaç complete binary tree
• kılavuzlu ikili ağaç threaded binary tree
• gezinme traversal
• kök önde preorder
• kök ortada inorder
• kök sonda postorder
• düzey sırası level-order
• ifade ağacı expression tree
• çağrı yığını call stack
• dairesel kuyruk circular queue
• eş biçimli isomorphic
• genişlik öncelikli arama breadth-first search
• derinlik öncelikli arama depth-first search
• dengeli ağaç balanced tree

10.15Kendini Dene

1. A–M genel ağacında (A'nın çocukları B, C, D; B'nin çocukları E, F; E'nin çocukları K, L; C'nin çocuğu G; D'nin çocukları H, I, J; H'nin çocuğu M) H'nin düzeyi, D'nin derecesi, E'nin ataları ve B'nin soyu nedir?

   Cevap

   H 3. düzeydedir. D'nin derecesi 3'tür (H, I, J). E'nin ataları A ve B'dir. B'nin soyu E, F, K ve L'dir.

2. Derinliği 5 olan bir ikili ağaçta en çok kaç düğüm bulunur? Bu ağacın 4. düzeyinde en çok kaç düğüm olabilir?

   Cevap

   En çok 2⁵ − 1 = 31 düğüm. 4. düzeyde en çok 2³ = 8 düğüm.

3. 20 düğümlü bir tam ikili ağaç 1 tabanlı bir dizide tutuluyor. Ağacın derinliği kaçtır? 14 numaralı düğümün ebeveyni ve çocukları hangileridir? 10 numaralı düğümün çocukları var mıdır?

   Cevap

   Derinlik ⌈lg 21⌉ = 5'tir. 14'ün ebeveyni ⌊14/2⌋ = 7'dir; çocukları 28 ve 29 olurdu, ikisi de 20'yi aştığı için yoktur (14 bir yapraktır). 10'un sol çocuğu 20 vardır; sağ çocuğu 21 yoktur.

4. Bir ikili ağaçta 7 iki çocuklu ve 3 tek çocuklu düğüm vardır. Kaç yaprak vardır? Bağlı gösterimde kaç NULL işaretçi bulunur?

   Cevap

   n₀ = n₂ + 1 = 8 yaprak vardır. Toplam düğüm sayısı 8 + 3 + 7 = 18'dir ve NULL işaretçi sayısı n + 1 = 19'dur.

5. Ağaçta A'nın çocukları B ve C, B'nin çocukları D ve E'dir; C'nin yalnız sağ çocuğu F vardır. Dört gezinmenin (kök önde, kök ortada, kök sonda, düzey sırası) çıktıları nedir?

   Cevap

   Kök önde ABDECF, kök ortada DBEACF, kök sonda DEBFCA, düzey sırası ABCDEF.

6. Son-işleç gösterimi A B + C * olan ifadenin ağacı nasıldır? Ön-işleç gösterimi nedir?

   Cevap

   Kök *'dır; sol alt ağacı +(A, B), sağ çocuğu C'dir. İfade (A + B) * C'dir. Ön-işleç gösterimi * + A B C'dir.

7. Yığınla kök ortada gezinme 1000 düğümlü sola çarpık bir zincire uygulanıyor. Yığında aynı anda en çok kaç adres bulunur? Zincir sağa çarpık olsaydı?

   Cevap

   Sola çarpık zincirde kökten başlayarak bütün düğümler sola inilirken yığına girer: 1000 adres (MAX_SIZE en az bu kadar olmalıdır). Sağa çarpık zincirde hiçbir düğümün sol çocuğu olmadığı için her düğüm girer girmez çıkar: en çok 1 adres.

8. esitmi, A(B, C) ile A(B, C(D, —)) ağaçlarıyla çağrılıyor. Sonuç nedir ve toplam kaç çağrı yapılır?

   Cevap

   Sonuç 0'dır. Çağrılar: (A, A), (B, B), B'nin iki boş çocuğu için iki (NULL, NULL), (C, C) ve C'lerin sol çocukları için (NULL, D). Son çağrıda iki koşul da yanlış çıkar ve 0 döner; && kısa devre yaptığı için C'lerin sağ çocuklarına bakılmaz. Toplam 6 çağrı.

9. Kök önde sırası ABDGCEF, kök ortada sırası DGBAECF olan ağaç hangisidir?

   Cevap

   Kök A'dır. Sol alt ağaç {D, G, B}: kökü B, B'nin solunda D, G vardır; D kök, G onun sağ çocuğudur. Sağ alt ağaç {E, C, F}: kökü C, sol çocuğu E, sağ çocuğu F. Ağaç A(B(D(—, G), —), C(E, F)).

10. A(B(D, E), C) ağacına cocukdegistir uygulanıyor. Yeni ağacın kök ortada sırası nedir? Yordam ikinci kez uygulanırsa ne olur?

    Cevap

    Asıl kök ortada sıra DBEAC'dir; ayna ağacınki bunun tersidir: CAEBD. İkinci uygulama her düğümde takası geri alır ve ağaç ilk hâline döner.

10.16İleri okuma

• E. Horowitz, S. Sahni ve S. Anderson-Freed, Fundamentals of Data Structures in C (2. baskı), Bölüm 5: terminoloji, ikili ağaç lemmaları, dizi ve bağlı gösterim, gezinmeler, ağaç kopyalama ve eşitlik yordamlarının bu notun izlediği kaynağıdır; kılavuzlu ikili ağaçlarla devam eder.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (3. baskı), Ek B.5 ve Bölüm 12: ağaçların matematiksel tanımlarını (yükseklik 0 tabanlı) ve ikili arama ağaçlarında gezinmeyi verir.
• R. Sedgewick, Algorithms in C, Parts 1–4 (3. baskı), Bölüm 5: özyineleme ile ağaçları birlikte işler; gezinmelerin yığın ve kuyrukla döngüsel sürümlerini ve ağaç özelliklerinin kanıtlarını içerir.
• D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms (3. baskı), Kesim 2.3–2.3.2: ikili ağaç gezinme algoritmalarını yığınla verir ve genel ağaçların ikili ağaçlarla gösterimini ayrıntılı inceler.

10.17Kaynaklar

1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, Bölüm 5 (Trees).
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3. baskı, MIT Press, Ek B.5 ve Bölüm 12.
3. R. Sedgewick, Algorithms in C, Parts 1–4, 3. baskı, Addison-Wesley, Bölüm 5 (Trees).
4. D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3. baskı, Addison-Wesley, 1997, Kesim 2.3.

İlgili sayfalar: Bölüm 10 sunumu · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.