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:

ikiliagac.jpg

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.

ikilizincir.jpg

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.

Yorumlar

  1. merve

    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.

  2. Şadi Evren ŞEKER Article Author

    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.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    
    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;
    }
  3. olcay

    Hocam ben ikili ağaç yapısında ekleme fonsiyonu yazdım.yazdığım fonsiyon kok degerinden kucuk degerleri kayıt edıyor fakat buyuk degerlerde sistem hata veriyor windows calısmayı durduruyor.oluşturduğum yapıda pointerların sırasını değiştirdiğimde bu sefer tam tersi yani buyukleri ekleyi kucukler için hata veriyor.yazdığım fonksiyon şudur hocam..

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    
    typedef struct data{
                         int veri;
                         data *sag;
                         data *sol;                                
                         };
     
                         data *kok =(data *)malloc(sizeof(data)); 
                         data *gkok;
     void ekle(int cocuk){
                          gkok = kok;                    
                        while(1){
                                  if (cocuk == gkok->veri){
                                   cout<<"sayi zaten var"<<endl;
                                   break;
                                                          }
     
                                 if(cocuk veri){
     
                                                      if(gkok->sol == 0){
                                                                   gkok->sol = (data *)malloc(sizeof(data));
                                                                   gkok = gkok->sol;
                                                                   gkok->veri =cocuk;
     
                                                                   break;
                                                                         }
                                                if(gkok->sol != 0){
                                                     gkok= gkok->sol;}
     
                                                      }
                                  if(cocuk > gkok->veri){
                                                      if(gkok->sag == 0){
                                                                   gkok->sag = (data *)malloc(sizeof(data));
                                                                   gkok = gkok->sag;
                                                                   gkok->veri =cocuk;
     
                                                                 break;
                                                                         }
                                                   if(gkok->sag != 0){
                                                   gkok=gkok->sag;}                
     
                                                      }
     
     
     
                                          }
                                          }
  4. Şadi Evren ŞEKER Article Author

    Sorunuz sanırım ikili arama ağacı (Binary search tree) kodlaması ile ilgili. Yani soldaki değerlerin atalarından (parent) küçük ve sağdaki değerlerin büyük olmasını istiyorsunuz.

    Bunu yapan bir kodu zaten daha önce aşağıdaki adreste anlatmıştım.

    http://www.bilgisayarkavramlari.com/2008/05/07/ikili-arama-agaci-binary-search-tree/

    Ayrıca ekleme fonksiyonunu da yine aynı yazının altında gelen bir soru üzerine yorum olarak yazmıştım. Tam çözümü bulunuyor ve buradan faydalanabilirsiniz. Yine de anlaşılmayan birşey veya soracağınız birşey olursa lütfen sorun elimden geldiğince cevaplamaya çalışırım.

    Başarılar

  5. hüseyin

    merhaba arkadaşlar elemanları aynı olursa neresine yazacaz sağına mı soluna mı?
    örnek = 25,46,4,90,90,46,3,78 mesele burda 90 ile 46 aynı ağaç şemasın da sağa mısola mı yazacağız.

  6. Şadi Evren ŞEKER Article Author

    Kerim Beyin yazdığı doğru. Yani sola konularak sorun çözülebilir ancak sağa yazılması da hatalı değil.

    Öncelikle şunun kararı verilmeli, tekrarlı veri tutulacak mı? (duplicate) şayet tutulmayacaksa, ağaçta olan bir verinin ikinci kere gelmesi durumunda ağaca konulmaması gerekir.

    Şayet tutulacaksa ister sağa veya ister sola bu değer konulabilir. Bir tercih yapılması gerekir. Ancak aynı tercihin ağaç ile ilgili diğer işlemlerde de uygulanması gerekir, örneğin arama veya ağacın dolaşılması gibi.

    Gerek soruda gerekse yapılan yorumlarda aslında ikili ağaç (binary tree) kavramından çok ikili arama ağacı (binary search tree) kabulü yapılmış. Çünkü verilerin sıralı tutulması ancak ikili arama ağacında gerekli oluyor, ikili ağaçta verinin nerede durduğunun önemi yok. Benzer yorumlar aşağıdaki ana konuda yer alıyor oraya bakabilirsiniz:

    http://www.bilgisayarkavramlari.com/2008/05/07/ikili-arama-agaci-binary-search-tree/

    Başarılar

  7. cem

    Merhabalar hocam aşağıdaki kodda yapmak istediğim main fonksiyonundan dizilerin adresini insert fonksiyonuna gönderip structure içindeki değerlere atamak.Bir türlü başaramadım

    #include
    #include
    typedef struct BST
    {
    int ID;
    char name[30];
    char surname[30];
    int friendsID[30];
    struct BST *left;
    struct BST *right;
    }BST;
    int main ()
    {

    }
    BST *newNode(int ID, char name[], char surname[], int friendsID[])
    {
    BST *newNodeTemp=(BST*)malloc(sizeof(BST));

    if(newNodeTemp==NULL)
    {
    printf("Not Allowed!!\n");
    exit(0);
    }

    newNodeTemp->ID=ID;
    newNodeTemp->name=name;
    newNodeTemp->surname=surname;
    newNodeTemp->friendsID=friendsID;
    }

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


yedi × 9 =