💻 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:

  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:

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 - [email protected]
#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]

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 < 50, o yüzden sola dallanmalıyız.
  3. 30 ile 40 karşılaştırıldı, 30 < 40, o yüzden sola dallanmalıyız.
  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.

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 🙂

    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

  6. Merhaba arkadaşlar,

    Bu yazıyı yazdığımda 2.sınıftaydım fakat artık mezun ve yoğun olarak çalışan birisi olduğum için, web sitesini sık sık kontrol edemiyorum.

    Birkaç arkadaşımız mail ile benimle iletişime geçmişler, kendilerine yardımcı olmaya çalıştım. Sizler de [email protected] adresi üzerinden benimle iletişime geçebilirsiniz. Vakit buldukça yardımcı olmaya çalışırım.

    İyi çalışmalar,

    Oben

  7. merhaba arkadaslar benım veri yapıları ve algorıtma dersimden bi ödevim var yardımcı olabılırmısınız lutfen
    1. Bağlantılı liste kullanılarak yapılan yığın ile yine bağlantılı liste kullanılarak yapılan kuyruk kullanarak iki soyut veri yapısı tanımlayınız ve programlarını (temel işlemler dahil) yapınız? Yığın ve kuyruğun her bir düğümünde öğrencinin numarası, adı, soyadı ve bölümü bilgileri tutulacaktır.
    2. Tasarlamış olduğunuz yığın kullanarak Veri Yapıları dersinin sınıf listesi oluşturulacaktır ve kuyruk kullanılarak Matematik dersinin sınıf listesi tutulacaktır. (Not: Dersleri bilgisayar mühendisliği dışındaki öğrenciler de alabilmektedir) Yazacağınız program yığın ve kuyruk temel işlemlerini içerecektir ve ek olarak aşağıda istenen fonksiyonlar olacaktır. Ana programda temel işlemleri içeren ve aşağıdaki istenenlere ulaşmak için kullanılabilecek bir menü oluşturunuz?
    a. Her iki dersi de alan öğrencileri listeleyiniz?
    b. Sadece Matematik dersini alan öğrencileri listeleyiniz? (Bu öğrenciler Veri Yapıları dersini alıyor olmayacaklar.)
    c. Kullanıcı isterse Veri Yapıları dersini A ve B grubu olarak ikiye ayıracaktır. A grubunda tek numaralı öğrenciler ve B grubunda çift numaralı öğrenciler olacaktır. Veri Yapıları dersini iki gruba ayırmak için gerekli yığın fonksiyon ve işlemlerini yazınız?
    d. Matematik ve Veri Yapıları derslerinin en az birini alan ve bilgisayar mühendisliği bölümü öğrencisi olan öğrencileri listeleyiniz (Derslerde yandal ve çift anadal ile ders alan farklı bölüm öğrencileri ve diğer bölümlerden öğrenciler bulunabilmektedir.)
    e. Her iki dersi alan fakat soyadları farklı adları aynı olan öğrencileri (adaşları) bulunuz?
    3. Yazdığınız programın ve her bir fonksiyonun mantığını birer paragraf şeklinde açıklayınız (programın her bir satırının ne iş yaptığı kodun yanına yazılarak mantık açıklanmaz. Koddan veya fonksiyonlardan önce birer paragraf mantığı açıklamanız gerekmektedir. ) ve bunların çalıştığını gösterir ekran çıktılarını ödevinize ekleyiniz?
    a. Ekran çıktıları bütün fonksiyonları içermelidir.
    b. Eğer çalıştırılamayan veya doğru sonuç vermeyen kod ve/veya fonksiyon varsa nedenini belirtiniz

    YARDIM EDEBİLİRSENİZ SEVİNİRİM CUMA SON GÜN ??? …

  8. mrh oben siten gercekten güzel.bir soru soracaktım yardımcı olrsan çok sevinirim.
    ağac veri yapısında veya bağlı listedeki elemanlara rastgele ulaşabilirmiyiz.mesala ağac veri yapısında kök ile yaprak konumundaki elemanı programmımda kullanmak istitorum nasıl yapacam acaba …
    aslında bir işlem oyunu c ile programamayı düşünüyorum araştırmalarım sonucu ağac veri yapısını kullanmam gerektiğini anadım sizce doğru yoldamıyım evet ise nasıl olacak bir ipucu lütfen

  9. Merhaba Memet,

    Öncelikle site benim değil, arkadaşım Umut'un. Sordugun soruya gelince; Bu örnekte, kökten başlayarak tüm ağacı taramak suretiyle objenin nexti null olan kayıtlarına yaprak diyebilirsin. Fakat bu masraflı bir çözüm olur. Bunun yerine yapraklar değiştikçe güncellenen ek bir liste kullanmanı önerebilirim.

    İyi çalışmalar

  10. İyi günler.. Prefix tree (veya Trie ) veri yapısını kullanarak kişi isimlerinin (ad ve soyad) kayıt edilebileceği bir telefon rehberi programı yazmam lazım.. yardımcı olabilirmisiniz?

  11. öncelikle paylaşımınız için teşekkürler.
    bu kodların bir de silme fonksiyonlu olanı var mıdır elinizde ?

Bir cevap yazın

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