25
May
2022

Veri yapıları ve algoritmalar dersi 10.slayt – Ağaç

Slayt ana hatları

Please wait while flipbook is loading. For more related info, FAQs and issues please refer to DearFlip WordPress Flipbook Plugin Help documentation.

Animasyonlu görünüm

Kaynak kod

#include<iostream>
using namespace std;

// Ağaç düğümü yapısını tanımla
struct dugum{
  int ID;
  dugum *sol;
  dugum *sag;	
};

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

// Ağacı dolaş (traverse)
void dolas(dugum *kok)
{
  if (kok == NULL) 
    cout<<"bos";//return;
  else
  {
    /* 1. seçenek infix: LNR veya RNL (kök ortada)
    // işlem
    dolas(kok->sol); 
    dolas(kok->sag);*/
    
    /* 2 seçenek prefix: NLR veya NRL (kök başta)
    // işlem
    dolas(kok->sol); 
    dolas(kok->sag);*/
    
    // 3. seçenek postfix: LRN veya RLN (kök sonda)
    dolas(kok->sol); 
    dolas(kok->sag);
    // işlem
  }
}
// Ağacı listele
void listele(dugum *kok)
{
  if (kok == NULL) 
  {
    return;
  }
  else
  {
    // 1. seçenek infix: LNR veya RNL (kök ortada)
    listele(kok->sol); 
    cout<<kok->ID<<" ";
    listele(kok->sag);
    
    /* 2 seçenek prefix: NLR veya NRL (kök başta)
    cout<<kok->ID<<" ";
    listele(kok->sol); 
    listele(kok->sag);*/
    
    /* 3. seçenek postfix: LRN veya RLN (kök sonda)
    listele(kok->sol); 
    listele(kok->sag);
    cout<<kok->ID<<" ";*/
  }
}

// Arama
bool ara(dugum *kok, int aranan)
{
  if (kok->ID == aranan)
  {
    return true;
  }
  if (kok == NULL)
  {
    return false;
  }
  if (aranan < kok->ID)
    ara(kok->sol, aranan);
  if (aranan >= kok->ID)
    ara(kok->sag, aranan);
}

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

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

// Silme işlemi
dugum* sil(dugum *kok, int silinecek)
{
  if (kok == NULL)
    return NULL;
  else if (kok->ID == silinecek)
  {
    if ((kok->sag == NULL) && (kok->sol == NULL)) // Aranan veri bir yapraktaysa yaprağı sil
    {
      delete(kok);
      return NULL;
    }
    // Çocukları olan 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.
    if (kok->sag!=NULL) // Düğümün sağ bağlantısı doluysa sağdaki en küçük düğümü getir
    {
      kok->ID = 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->ID = maks(kok->sol);
      kok->sol = sil(kok->sol, maks(kok->sol));
      return kok;
    }
  }	
  else if (silinecek >= kok->ID) // Silinecek değer düğümden büyük eşitse sağdan devam et
  {
    sil(kok->sag, silinecek);
  }
  else if (silinecek< kok->ID) // Silinecek değer düğümden küçükse soldan devam et
  {
    sil(kok->sol, silinecek);
  }	
}

main()
{
  // Yeni ağaç oluştur	
  dugum *kok = new dugum;
  kok = NULL;
  
  // Ağaca düğümler ekleyelim
  kok = ekle(kok, 23);
  kok = ekle(kok, 12);
  kok = ekle(kok, 9);
  kok = ekle(kok, 33);
  kok = ekle(kok, 41);
  //Ağacı listele
  listele(kok);

  // Arama yap
  int arananSayi = 41;
  if (ara(kok, arananSayi) == true ) cout<<arananSayi<<" bulundu"<<endl;
  else cout<<arananSayi<<" bulunmadi"<<endl;
    
  cout<<"en buyuk: "<<maks(kok)<<endl;    
  cout<<"en kucuk: "<<min(kok)<<endl;    
  
  sil(kok, 33);
  listele(kok);
}

 

%d blogcu bunu beğendi: