C'de AVL Agacı Kodu

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <windows.h>

typedef struct AVLagac {

        struct AVLagac *sol,*sag;

        int sayi;

        int yukseklik;

        }AVLagaclar;

// İki tamsayı arasında en buyugunu bulmak icin basit bir fonksiyon tanımladık.

int max(int a, int b)

{

    return (a>b)?a:b; // a büyüktür b'den ise a yı, değilse b yi yazdır.if else yapısı gibidir.

}        

        

// Ağacın yüksekligini almak icin yardımcı bir fonksiyon tanımladık.

int yukseklik(AVLagaclar *AVL) {

    

    if (AVL == NULL)

    return 0;

    

    return AVL->yukseklik;

}     

// ilk başta ana ağaç yapımızı olusturmak icin yeniDugum adında bir fonksiyon tanımladık.

AVLagaclar *yeniDugum(int sayi) {

           

         AVLagaclar *dugum = (AVLagaclar *)malloc(sizeof(AVLagaclar));

         

         dugum->sayi=sayi;

         dugum->sol=NULL;

         dugum->sag=NULL;

         dugum->yukseklik = 1;

         return dugum;

         }

         

AVLagaclar *sagaDondur(AVLagaclar *y) {

           

           AVLagaclar *x = y->sol;

           AVLagaclar *T2 = x->sag;

           

           // döndürmeyi gerçekleştiriyoruz.

           x->sag=y;

           y->sol=T2;

           

           // yukseklikleri guncelliyoruz.

           y->yukseklik = max(yukseklik(y->sol), yukseklik(y->sag))+1;

           x->yukseklik = max(yukseklik(x->sol), yukseklik(x->sag))+1;              

           

           // yeni kökü döndürüyoruz.

           return x;

}

AVLagaclar *solaDondur(AVLagaclar *x) {

           

           AVLagaclar *y = x->sag;

           AVLagaclar *T2 = y->sol;

           

           // döndürmeyi gerçekleştiriyoruz.

           y->sol=x;

           x->sag=T2;

           

           

           // yukseklikleri guncelliyoruz.

           x->yukseklik = max(yukseklik(x->sol), yukseklik(x->sag))+1;

           y->yukseklik = max(yukseklik(y->sol), yukseklik(y->sag))+1;

                         

           // yeni kökü döndürüyoruz.

           return y;

}

// denge faktörü için bir fonksiyon yazdık.

int denge(AVLagaclar *AVL)

{

    if (AVL == NULL)

    return 0;

    

    return yukseklik(AVL->sol) - yukseklik(AVL->sag);

}

AVLagaclar *ekle(AVLagaclar *dugum, int sayi) {

           

    // ilk olarak normal bir sekilde BSTye uygun eklemeye baslıyoruz.

    if (dugum == NULL) // agacta hic eleman yoksa yeniDugum fonk. göndererek gerekli atamalari orada gerçekleştiriyoruz.

        return(yeniDugum(sayi));

 

    if (sayi < dugum->sayi) // eklenen sayi kucukse dugumun soluna.

        dugum->sol  = ekle(dugum->sol, sayi);

    else // eklenen sayi buyukse dugumun sagina.

        dugum->sag = ekle(dugum->sag, sayi);

 

    // ata dugumun yuksekligini guncelliyoruz.

    dugum->yukseklik = max(yukseklik(dugum->sol), yukseklik(dugum->sag)) + 1;

 

    // ata dugumun dengeli olup olmadıgını kontrol ediyoruz.

    int dengele = denge(dugum);

 

    // dugum dengesiz ise 4 tane durum olusuyor.

 

    // Yeni kayıt, x düğümünün sol alt ağacının sol çocuğuna eklenebilir.

    if (dengele > 1 && sayi < dugum->sol->sayi)

        return sagaDondur(dugum);

 

    // Yeni kayıt, x düğümünün sağ alt ağacının sağ çocuğuna eklenebilir.

    if (dengele < -1 && sayi > dugum->sag->sayi)

        return solaDondur(dugum);

 

    // Yeni kayıt, x düğümünün sol alt ağacının sağçocuğuna eklenebilir.

    if (dengele > 1 && sayi > dugum->sol->sayi)

    {

        dugum->sol =  solaDondur(dugum->sol);

        return sagaDondur(dugum);

    }

 

    // Yeni kayıt, x düğümünün sağ alt ağacının sol çocuğuna eklenebilir.

    if (dengele < -1 && sayi < dugum->sag->sayi)

    {

        dugum->sag = sagaDondur(dugum->sag);

        return solaDondur(dugum);

    }

 

    

    return dugum;

}

void inOrder(AVLagaclar *kok)

{

    if(kok != NULL)

    {

        inOrder(kok->sol);

        printf("%d ", kok->sayi);

        inOrder(kok->sag);

    }

}

void ara(AVLagaclar *kok,int num) {

           int sayac=1;

           

           while(kok!=NULL){

           if(num<kok->sayi) { 

                             kok=kok->sol;

                             sayac++;

                             

                             }

           else if(num>kok->sayi) { 

                             kok=kok->sag;

                             

                             sayac++;

                              }

           else { printf("\naranan %d sayisi %d. adimda bulundu.\n",num,sayac);

                  return; 

                }

                

                }

                printf("\nne yazikki olmayan bir deger girdiniz, bulamadik\n");

           }

int toplam=0;

           

void ortAdim(AVLagaclar *kok) {

     

     if(kok->sol) ortAdim(kok->sol);

     if(kok->sag) ortAdim(kok->sag);        

     toplam++;

     }

int main()

{

system("COLOR 5A");

  AVLagaclar *kok = NULL;

  int deger;

  int aranan;

  

 /*printf("agaca eleman eklemek istemiyorsaniz yani cikis icin 0 girin\n\n");

  do {

      printf("\nbir sayi gir : ");

      scanf("%d",&deger);

      if(deger==0) break;

      kok=ekle(kok,deger);

      }while(deger!=0);*/

  

  

  kok = ekle(kok, 30);

  kok = ekle(kok, 60);

  kok = ekle(kok, 90);

  kok = ekle(kok, 120);

  kok = ekle(kok, 150);

  kok = ekle(kok, 75);

  

 

  printf("\n\nInorder Traversal yontemiyle listelersek \n\n");

  inOrder(kok);

  

  printf("\n\narama yapilmasini istediginiz sayi : ");

  scanf("%d",&aranan);

  ara(kok,aranan);

  

  ortAdim(kok);

  printf("\n\ntoplam eleman sayisi : %d",toplam);

  

  getch();

  return 0;

}