oben agac 3
💻 Bilgisayar, 💾 Programlama

Ağaç Veri Yapısı [C++ Örnek]

Bu yazı ziyaretçilerimden Oben Işık tarafından yazılmıştır. Oben Işık, İstanbul Teknik Üniversitesi Bilgisayar Mühendisliği ikinci sınıfta okumaktadır. Katkıları için kendisine teşekkür eder, web sitesine bir an önce kavuşmasını dilerim.

Merhaba arkadaşlar, bir localhost yazısı ile daha karşınızdayım.

Sağolsun yazılımportal.com adresindeykenki sponsorumuz Turan İnanır’ın sitemin kapanacağını ve beni yüzüstü bırakacağını 10 gün kala haber vermesinden dolayı artık yazılarımı localhostta yazıp sizlerle paylaşıyorum, yani paylaşacağım.

Bu yazımda ağaç (tree) veri yapısını irdeleyeceğiz, hem de ne irdeleme!

Şunu en baştan söylemekte fayda var; bir çok veri yapısı zaten Standart Template Library (STL) de olan veri yapıları yani hazır olarak var fakat bizim amacımız bedava kullanmayı değil de işin mantığını öğretmek.

Mantığı öğrenmek sizin için çok önemli olacak çünkü belki ilerde başka bir veri yapısını da siz üreteceksiniz ve millet sizin hazır kütüphanenizi kullanacak, hoş olmaz mı? 😀

Öncelikle size ağaç yapımızdaki structlarımızı bir tanıtayım:

[rawr]

struct dugum{
	int sayi;
	dugum *sol;
	dugum *sag;
};
struct agac{
	dugum *kok;
	int elemansayisi;
	void agacolustur();
	void ekle(dugum *);
	void yazdir();
	void preorder(dugum *);
	void inorder(dugum *);
	void postorder(dugum *);
};

[/rawr]

Şimdi arkadaşlar, öncelikle ben programın tüm kodlarını koymadan önce size biraz structtaki preorder, inorder ve postorder nedir onları anlatayım.

Mesela ağacımız şu şekilde olsun:

oben agac 1

  1. Sıralı (inorder): İlk adımda sol alt ağaç sıralı şekilde dolaşılır (a-b-c). Kök düğüme uğranır (d). Son adımda sağ alt ağaç sıralı şekilde dolaşılır (e-f-g). Sonuçta ağaç sırasıyla a-b-c-d-e-f-g düğümlerine erişilerek gezilir.
  2. Kökten Başlayarak (preorder): İlk adımda köke uğranır(d). Sol alt ağaç kökten başlayarak dolaşılır (b-a-c). Son adımda sol alt ağaç kökten başlayarak dolaşılır (f-e-g). Sonuçta ağaç sırasıyla d-b-a-c-f-e-g düğümlerine erişilerek gezilir.
  3. Sondan Başlayarak (postorder): İlk adımda sol alt ağaç sondan başlayarak dolaşılır (a-c-b). İkinci adımda sağ alt ağaç sondan başlayarak dolaşılır (e-g-f). Son adımda ise köke uğranır(d). Sonuçta ağaç sırasıyla a-c-b-e-g-f-d düğümlerine erişilerek gezilir.

Ve bunların da yanı sıra size sıralı ikili ağaç mantığından bahsetmek istiyorum:

oben agac 2

Sıralı ikili ağaçlarda kök hücresinden başlayarak, eğer eklenecek düğümün veri kısmındaki değer, kök düğümünün veri kısmındaki değerden büyük ise sağ tarafa , küçük yada eşit ise sol tarafa eklenir. Bu şekilde olşturulan sıralı ikili ağaçta biliriz ki, sol alt ağaçtaki düğümlerde kökten küçük ya da köke eşit değerler, sağ alt ağaçtaki düğümlerde ise kökten büyük değerler bulunur.

Örneğin üstteki ağaç. 🙂

Şimdi de programımızın kodlarını inceleyelim:

[rawr]

//OBEN ISIK - solid3y3@gmail.com
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
using namespace std;
 
struct dugum{
    int sayi;
    dugum *sol;
    dugum *sag;
};
struct agac{
    dugum *kok;
    int elemansayisi;
    void agacolustur();
    void ekle(dugum *);
    void yazdir();
    void preorder(dugum *);
    void inorder(dugum *);
    void postorder(dugum *);
};
 
void agac::preorder(dugum *p){
    if(p){
        cout << p->sayi << "  ";
        preorder(p->sol);
        preorder(p->sag);
    }
}
void agac::inorder(dugum *p){
    if(p){
        inorder(p->sol);
         cout << p->sayi << "  ";
        inorder(p->sag);
    }
}
void agac::postorder(dugum *p){
    if(p){
        postorder(p->sol);
        postorder(p->sag);
         cout << p->sayi << "  ";
    }
}
void agac::agacolustur(){
    kok = NULL;
    elemansayisi = 0;
    cout << "Agac olusturuldu ;) " <<endl;
}
 
void agac::ekle(dugum *eklenecek){
    bool eklendi = false;
    dugum *tara; dugum *yeni = new dugum;
    tara = kok;
    *yeni = *eklenecek; yeni->sol = NULL; yeni->sag = NULL;
 
    if(kok == NULL){
        kok = yeni;
        cout << "Ilk eleman eklendi ! (" << kok->sayi << ")"<<endl;
        elemansayisi++;
        return;
    }
    while((tara != NULL) && (!eklendi))
    {
        if( yeni->sayi < tara->sayi)
        {
            if(tara->sol != NULL) { tara = tara->sol; }
            else
            {
                cout << tara->sayi << " dugumunun soluna " << yeni->sayi << " elemanini ekledim, sanirim :D" << endl;
                tara->sol = yeni;
                eklendi = true;
            }
        }
        else if ( yeni->sayi > tara->sayi)
        {
          if(tara->sag != NULL) tara = tara->sag;
          else
          {
              cout << tara->sayi << " dugumunun sagina " << yeni->sayi << " elemanini ekledim, sanirim :D " << endl;
              tara->sag = yeni;
              eklendi = true;
          }
        }else { cout << "Kopya" << endl;  return;}
    }
    if(eklendi == true) { elemansayisi++; }
    cout << "Eleman sayisi : " << elemansayisi  << endl  ;
    cout << "PREORDER :\t\t"; preorder(kok);
    cout << endl;
    cout << "INORDER :\t\t"; inorder(kok);
    cout << endl;
    cout << "POSTORDER :\t\t"; postorder(kok);
    cout << endl;
}

int main(){
    typedef agac veriyapisi;
    veriyapisi kayit;
    dugum yenikayit;
    kayit.agacolustur();
 
     for(int i=1;i<10 ;i++){
    cout << endl << "Eleman : ";
    cin>>yenikayit.sayi;
    kayit.ekle(&yenikayit);
    }
 
    system("pause");
    return 0;
}

[/rawr]

oben agac 3

Kodlardan da anlaşılabileceği gibi aslında mantığı çok basit, yukarıdaki ağacı programımızla oluşturalım ve preorder , inorder ve postorder durumlarını inceleyelim.

Ağacımıza ilişkin veriler programa girildiğinde;

[rawr]

Agac olusturuldu ;)
 
Eleman : 30
Ilk eleman eklendi ! (30)
 
Eleman : 20
30 dugumunun soluna 20 elemanini ekledim, sanirim :D
Eleman sayisi : 2
PREORDER :              30  20
INORDER :               20  30
POSTORDER :             20  30
 
Eleman : 50
30 dugumunun sagina 50 elemanini ekledim, sanirim :D
Eleman sayisi : 3
PREORDER :              30  20  50
INORDER :               20  30  50
POSTORDER :             20  50  30
Eleman : 10
20 dugumunun soluna 10 elemanini ekledim, sanirim :D
Eleman sayisi : 4
PREORDER :              30  20  10  50
INORDER :               10  20  30  50
POSTORDER :             10  20  50  30
 
Eleman : 40
50 dugumunun soluna 40 elemanini ekledim, sanirim :D
Eleman sayisi : 5
PREORDER :              30  20  10  50  40
INORDER :               10  20  30  40  50
POSTORDER :             10  20  40  50  30
 
Eleman : 60
50 dugumunun sagina 60 elemanini ekledim, sanirim :D
Eleman sayisi : 6
PREORDER :              30  20  10  50  40  60
INORDER :               10  20  30  40  50  60
POSTORDER :             10  20  40  60  50  30
 
Eleman : 35
40 dugumunun soluna 35 elemanini ekledim, sanirim :D
Eleman sayisi : 7
PREORDER :              30  20  10  50  40  35  60
INORDER :               10  20  30  35  40  50  60
POSTORDER :             10  20  35  40  60  50  30
 
Eleman : 45
40 dugumunun sagina 45 elemanini ekledim, sanirim :D
Eleman sayisi : 8
PREORDER :              30  20  10  50  40  35  45  60
INORDER :               10  20  30  35  40  45  50  60
POSTORDER :             10  20  35  45  40  60  50  30
 
Eleman : 75
60 dugumunun sagina 75 elemanini ekledim, sanirim :D
Eleman sayisi : 9
PREORDER :              30  20  10  50  40  35  45  60  75
INORDER :               10  20  30  35  40  45  50  60  75
POSTORDER :             10  20  35  45  40  75  60  50  30
Devam etmek için bir tuşa basın . . .

[/rawr]

şeklinde bir ekran görüntüsü oluşur.

Şimdi de ağacımızda rakam aramaya çalışalım. Kodları vermeden önce sonucu vermek istiyorum:

[rawr]

Eleman sayisi : 9
PREORDER :              30  20  10  50  40  35  45  60  75
INORDER :               10  20  30  35  40  45  50  60  75
POSTORDER :             10  20  35  45  40  75  60  50  30
Hangi elemani ariyorsunuz ?  : 35
ARADIGIM : 35
Siz 35 girdiniz ve ben de 35 elemanini 4.denemede buldum ;)
Devam etmek için bir tuşa basın . . .

[/rawr]

Şimdi program böyle diyor, bakalım 4. denemede bulmuş muyuz? İrdeleyelim:

  1. 30 ile 35 karşılaştırıldı, 35 > 30, o yüzden sağa dallanmalıyız.
  2. 30 ile 50 karşılaştırıldı, 30
  3. 30 ile 40 karşılaştırıldı, 30
  4. 35 ile 35 karşılaştırıldı, TRUE RESULT!

Peki ya olmayan bir değeri aramaya çalışsak ne olacaktı? Ben denedim programda ve böyle bir sonuç çıktı:

[rawr]

Hangi elemani ariyorsunuz ?  : 100
ARADIGIM : 100
Olmayan deger aradin eline ne gecti ?
Devam etmek için bir tuşa basın . . .

[/rawr]

Kodları merak ediyorsunuz dimi, 😀 aslında mantığı tamamen ekleme ile aynı, inceleyince siz de anlayacaksınız.

[rawr]

void agac::ara(dugum *eklenecek){
dugum *tara;
tara = kok;
bool bulundu = false;
int kacinci = 1;
cout << "ARADIGIM : " << eklenecek-> sayi <<endl ;
while((tara != NULL) && !bulundu){
  if(eklenecek->sayi < tara->sayi)
  {
    tara = tara->sol;
    kacinci++;
  }
  else if(eklenecek->sayi > tara->sayi)
  {
      tara = tara->sag;
      kacinci++;
  }
  else { cout << "Siz " << eklenecek->sayi << " girdiniz ve ben de " << tara->sayi << " elemanini "<< kacinci << ".denemede buldum ;) " << endl; return;}
}
cout << "Olmayan deger aradin eline ne gecti ? " << endl;
}

[/rawr]

Not: struct yapımıza fonksiyonumuzu tanıtmayı unutmuyoruz, main fonksiyonumuzdan da aranacak elemanı aşağıdaki şekilde göndertebiliriz:

[rawr]

cout << "Hangi elemani ariyorsunuz ?  : " ;
    int aranan;
    cin >> yenikayit.sayi;
    kayit.ara(&yenikayit);

[/rawr]

Buraya kadar sanırım bir çok birşey öğrendik.

Ağaç yapısında veri silme başlı başına bir olay oldugu için başka bir konuda başlıca değineceğiz.

Umarım bu bilgileri iyi harmanlarsınız çünkü ilerde çok işinize yarayacak bence. 😀

İyilikler dilerim, OBEN IŞIK.

👋 🚨 Yeni yazılardan haberdar olmak ister misiniz? 👇

Bir cevap yazın

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

Ağaç Veri Yapısı [C++ Örnek] 34 yorum aldı.

  1. çalışmanız çok güzel olmuş tebrikler.Benim bir sorum olacaktı gerçi konuya alakası yok ama neyse .
    herhangi bir kod loğunu sitenize nasıl ekliyorsunuz.üstelik renkli.sizinki gibi yani.Cevaplarsanız çok sevinirim.

  2. Huffman kodlama ağacı nedir ?

    Soru 1-) Huffman kodlama ağacı nedir ? nerelerde kullanılır açıklayınız.

    Cevap 1-) Huffman Kodu, 1952′de MIT’de bir Doktora öğrencisiyken David A. Huffman tarafından bulunmuş kayıpsız bir sıkıştırma algoritmasıdır. Pek çok algoritmanın üstüne geliştirildiği, veri sıkıştırmayı anlamak için temel oluşturan bir veri sıkıştırma tekniğidir. Bu algoritmanın sorduğu iki basit soru vardır;

    * Karakterler kodlamak için sabit uzunluk (aynı sayıda bit) kullanmalı mıyız?
    * Sabit uzunluk kullanmayacaksak iki karakter arasındaki farkı nasıl anlayacağız?

    Bilgisayar bilimlerinde veri sıkıştırmak için kullanılan bir kodlama yöntemidir. Kayıpsız (lossless) olarak veriyir sıkıştırıp tekrar açmak için kullanılır. Huffman kodlamasının en büyük avantajlarından birisi kullanılan karakterlerin frekanslarına göre bir kodlama yapması ve bu sayede sık kullanılan karakterlerin daha az, nadir kullanılan karakterlerin ise daha fazla yer kaplamasını sağlamasıdır.

    Şayet bütün karakterlerin dağılımı eşitse yani aynı oranda tekrarlanıyorsa, bu durumda Huffman kodlaması aslında blok sıkıştırma algoritması (örneğin ASCII kodlama) ile aynı başarıya sahiptir. Ancak bu teorik durumun gerçekleşmesi imkansız olduğu için her zaman daha başarılı sonuçlar verir.

  3. merhabalar bende bilgisayarımdaki tüm text dosyalarını bulup sıralamak istiyorum ama bu yapıyı yeni duydugumdan kodunu bilmiyorum yardımcı olursanız sevinirim

    1. Pelin selam,

      Bilgisayarındaki text dosyalarını bulup sıralamak istiyorsan, bunu yaparken linux işletim sistemi altında geliştirme yapıyorsan, öncelikle belirtmek isterim ki, bizim ağacımız sayılar üzerinde işlem yapmak üzere tasarlanmıştı bu yazıda. Bu sebeple bucketsort, radixsort, quicksort vb. algoritmaları incelemeni tavsiye ederim.

      2 seneden bu yana hiç bir araştırma yapmamışsan tabii :))

  4. hazırlayana çok teşekkürler.şu internet çöplüğünde böyle bir makaleyi bulabildiğim için şanslıyım++; diorm 😉

  5. Merhaba ekleme kodunu çok iyi anladım ve uygulamada da çalışıyor ancak arama metotunda bir problem var sanırım çalıştırdığımda 35 i aratırken 2. denemede buldum yazıyor halbuki dediğiniz gibi 4 olması lazım tek tek inceledim kodu 30un sağ düğümü olan 50 nin köke atanması gerekirken direk 35 olarak gösteriyor hata nereden kaynaklanıyor çözemiyorum…

    1. Kodu yazalı baya vakit geçti, şu an problem nerdedir,i kestirebilmem çok mümkün değil. Ama boş bir vaktimde kontrol edeceğim. 🙂

      1. ben buldum hatamı (: kodların hepsi doğru ve çalışıyor sadece ağaçın elemanlarını doğru sırayla girmek gerekiyormuş..

      2. Kodu yazalı deyince, sanki sen yazalı çok vakit geçmiş gibi bir ifade anladım ben. Bunu demek istemediğini düşünmeyi tercih ediyorum.

      3. Evet Oben ya, bir hata olmuş. Yazıya girmeden yorumları direk yönetici arayüzünden onayladığım için, yazının başlığına göre hatırlayıp hatırlamadığıma karar veriyorum. Sitedeki yazıların neredeyse hepsi benim olunca da başlıktan bu yazının ve kodun senin olduğunu hiç fark etmemişim yoruma cevap verirken. :/ Özür diliyorum, yanlış anlaşılma, kırgınlık olmasın. 🙂

      4. Selam Umut,

        Yok yanlış anlamak değil de, sen yazmazsın böyle şeyler, seneler insanları bu kadar değiştirmemeli diye şaşırmıştım sadece ama sen de bu şekilde ifade ettiğine göre problem yok, dargınlık da yok 🙂

  6. allah razı olsun kardesim elimde kayda değer hic kaynak yoktu cok iyi bir referans ldu tesekkür ederim

    1. reccep Selam,

      Arama metodunun 18.satırında, arama neticesinde herhangi bir sonuç bulunursa, return edilen while döngüsünde, dilenirse bir sonuç bulunup bulunmadığını takip edebilmek için değişken tanımlanmıştır.

      İyi çalışmalar,

      Oben