Veri yapıları ve algoritmalar II dersi – Ağaç

İkili arama ağacı C++ kodları

#include<iostream>
using namespace std;

// Ağaç düğüm yapısının tanımlanması
struct dugum{
    char harf;
    dugum *sol;
    dugum *sag;
};

// Yeni düğüm ekleme
dugum *ekle(dugum *kok, char veri)
{
    if (kok == NULL)
    {
        dugum *yeni = new dugum;
        yeni->sag = NULL;
        yeni->sol = NULL;
        yeni->harf = veri;
        return yeni;
    }
    else if (veri < kok->harf)
    {
        kok->sol =  ekle(kok->sol, veri);
        return kok;
    }
    else if (veri >= kok->harf)
    {
        kok->sag = ekle(kok->sag, veri);
        return kok;
    }
    return kok;
}

// Ağacı listeleme
void listele(dugum *kok)
{
    if (kok == NULL)
    {
        return;
    }
    else
    {
        // INFIX
        listele(kok->sol);
        cout<<kok->harf<<" ";
        listele(kok->sag);
        
        /*
        //PREFIX
        cout<<kok->harf<<" ";
        listele(kok->sol);
        listele(kok->sag);
    
        //POSTFIX
        listele(kok->sol);
        listele(kok->sag);
        cout<<kok->harf<<" ";
        */
    }
}

// Arama
void ara(dugum *kok, char aranan)
{
    if (kok->harf==aranan){
        //cout<<endl<<aranan<<" değeri "<<kok<<" adresinde bulundu";
    }
    else if (kok == NULL){
        //cout<<endl<<aranan<<" değeri bulunamadı.";
    }
    else if (aranan < kok->harf){
        ara(kok->sol, aranan);
    }
    else if (aranan >= kok->harf){
        ara(kok->sag, aranan);
    }
}

// Maksimum değer bulma
char maks(dugum *kok)
{
    while (kok->sag != NULL)
        kok = kok->sag;
    return kok->harf;
}

// Minimum değer bulma
char min(dugum *kok)
{
    while (kok->sol != NULL)
        kok = kok->sol;
    return kok->harf;
}

// Silme işlemi
dugum* sil(dugum *kok, char silinecek)
{
    if (kok == NULL)
        return NULL;
    else if (kok->harf == silinecek)
    {
        if ((kok->sag == NULL) && (kok->sol == NULL)) // Aranan veri bir yapraktaysa, yani sol ve sağ bağlantıları boşsa düğümü sil
        {
            delete(kok);
            return NULL;
        }
        // Eğer arada bir düğüm silinecekse;
        //Ya o düğümün sol altındaki en büyük düğüm silinen düğümün yerine gelir
        // Ya da o düğümün sağ altındaki en küçük düğüm silinen düğümün yerine gelir.
        else if (kok->sag!=NULL) // Düğümün sağ bağlantısı doluysa sağdaki en küçük düğümü getir
        {
            kok->harf = min(kok->sag);
            kok->sag = sil(kok->sag, min(kok->sag));
            return kok;
        }
        else if (kok->sol!=NULL) // Sağ bağlantısı boş ve sol bağlantısı doluysa soldaki en büyük düğümü getir
        {
            kok->harf = maks(kok->sol);
            kok->sol = sil(kok->sol, maks(kok->sol));
            return kok;
        }
    }
    else if (silinecek >= kok->harf) // Silinecek değer düğümden büyük eşitse sağdan devam et
    {
        sil(kok->sag, silinecek);
        return NULL;
    }
    else if (silinecek< kok->harf) // Silinecek değer düğümden küçükse soldan devam et
    {
        sil(kok->sol, silinecek);
        return NULL;
    }
    return NULL;
}

int main()
{
    // Yeni ağaç oluştur
    dugum *kok = new dugum;
    kok = NULL;
    
    // Ağaca düğümler ekle
    kok = ekle(kok, 'M');
    kok = ekle(kok, 'A');
    kok = ekle(kok, 'K');
    kok = ekle(kok, 'U');
    kok = ekle(kok, 'Z');
    kok = ekle(kok, 'T');
    kok = ekle(kok, 'Y');
    kok = ekle(kok, 'O');
    
    //Ağacı listele
    listele(kok);
    
    // Bir veri ara
    ara(kok, 'Z');
    
    // Min ve max değerleri bul
    cout<<endl<<"en buyuk: "<<maks(kok);
    cout<<endl<<"en kucuk: "<<min(kok);
 
    // Bir veri sil
    cout<<endl<<"Z harfini silelim:"<<endl;
    sil(kok, 'Z');
    listele(kok);
    
    return 0;
}