...Yazan: Şadi Evren ŞEKER
Ağaçların özel bir hali olan ikili ağaçlarda her düğümün çocuklarının sayısı azami 2 olabilir. Bir düğümün daha az çocuğu bulunması durumunda ( 0 veya 1) ağacın yapısı bozulmaz. Yapraklar hariç bütün düğümlerin ikişer çocuğu bulunması ve yaprakların aynı derinlikte bulunması durumunda bu ağaca dengeli ağaç (balanced tree) denilir. Aşağıda bir dengeli ikili ağaç örneği tasvir edilmiştir:
Bu ağacı değişik sıralarda yeniden oluşturabiliriz. Örneğin aşağıdaki ağaç da yukarıdaki verilerin aynılarını taşıyan bir ikili ağaç örneğidir.
Yukarıdaki bu ağacın ilk örnekten farkı dengesiz olması ve özel olarak her düğümün çocuk sayısının 1 olmasıdır. Tanım hatırlanacak olursa yukarıdaki bu ağaç da bir ikili ağaç olarak kabul edilebilir.
C dilinde bir ikili ağacı ifade edecek struct aşağıdaki şekilde yazılabilir:
typedef struct dugum{
int veri;
dugum *sol;
dugum *sag;
};
Yukarıdaki kodda bir düğümün taşıması gereken bilgiler tanımlanmıştır. Buna göre düğümün sağındaki ve solundaki çocukları gösteren birer gösterici (pointer) ve düğümün içindeki veriyi tutan bir veri değişkeni bulunmaktadır.
Benzer durum java dilinde aşağıdaki şekilde ifade edilebilir:
class dugum{
int veri;
dugum sol;
dugum sag;
};
Yukarıdaki kodda ise nesne göstericisi (object referrer) kullanılarak bir nevi gösterici (pointer) yapısı kullanılmıştır. Buna göre her düğümün sol ve sağında gene düğüm cinsinden birer nesne bulunabilecektir.
Daha fazla bilgi için ikili ağaçların özel bir hali olan ikili arama ağaçlarına (binary search tree) bakabilirsiniz.
1,082 views
Merhaba hocam;
Parametre olarak girilen level degerinden buyuk olan level’deki node sayisini döndüren bir fonksiyona ihtiyacım var hocam.Mesela (level=3 ise 4,5,… levellerdeki node sayisinı döndürücek).Ayrıca ağacımı Binary Tree yapısında.Verceğiniz cevap için şimdiden çok teşekkür ederim.
Kabaca bir ağacı dolaşırken kaçıncı seviyede olduğunuzu tutmanız yeterlidir. Kabaca aşağıdaki şekilde bir müsvette kod yazılabilir.
int dolas(int seviye, int limit, node *dugum){ int sayi = 0; if(dugum->sol !=NULL){ if(seviye >= limit) sayi = 1 + dolas(seviye + 1 , limit, dugum->sol); else sayi = dolas(seviye + 1 , limit, dugum->sol); } if(dugum->sağ !=NULL){ if(seviye >= limit) sayi = sayi + 1 + dolas(seviye + 1 , limit, dugum->sağ); else sayi = sayi + dolas(seviye + 1 , limit, dugum->sağ); } return sayi; }