Avl Ağacına Eleman Ekleme ve Listeleme
[Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...] Bu yazıda, avl ağacına eleman ekleme ve listeleme işlemlerini ele alan bir örnek paylaşacağım. Öncelikle [Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...]ve [Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...] yazılarını incelemenizi öneriyorum.Burada kullanacağımız yapı tıpkı yukarıdaki linkte verilen örnekteki gibi rekürsif bir yapı olduğu için örneği incelemeniz aşağıdaki kodu anlamanızı kolaylaşacaktır. Avl ağacında, dengesiz ağaçtan farklı olarak döndürme işlemleri vardır biraz bu işlemlerden bahsedelim. Yeni eklenen eleman ağacın dengesini bozarsa döndürme işlemlerini gerçekleştirerek ağacın yeniden dengeye gelmesini sağlamamız gerekmektedir. Basit bir örnek olarak aşağıdaki resmi inceleyebiliriz.
Kod:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#include<windows.h>
struct Dugum
{
char Kelime[100];
Dugum* Sag;
Dugum* Sol;
int kelimesay;
int Derece;
};
Dugum* Kok;
int Max( int say1, int say2 )
{
if(say1>say2)
return say1;
else
return say2;
}
int Derece(Dugum* dugum)
{
if(dugum)
return dugum->Derece;
else return -1;
}
Dugum* SoldanDondur(Dugum* D )//sol taraftan ekleme yaparken döndürme işlemi
{
Dugum* D2;
D2 = D->Sol;
D->Sol = D2->Sag;
D2->Sag = D;
D->Derece = Max(Derece (D->Sol) ,Derece(D->Sag)) + 1;
D2->Derece = Max(Derece(D2->Sol),D->Derece ) + 1;
return D2;
}
Dugum* SagdanDondur( Dugum* D )//sağ taraftan ekleme yaparken döndürme işlemi
{
Dugum* D2;
D2 = D->Sag;
D->Sag = D2->Sol;
D2->Sol = D;
D->Derece = Max( Derece(D->Sol),Derece(D->Sag)) + 1;
D2->Derece = Max(Derece(D2->Sag),D->Derece ) + 1;
return D2;
}
Dugum* SoldanCiftDondur( Dugum* D )//sol taraftan çift döndürme işlemi
{
D->Sol= SagdanDondur(D->Sol);
return SoldanDondur(D);
}
Dugum* SagdanCiftDondur( Dugum* D )//sağ taraftan çift döndürme işlemi
{
D->Sag = SoldanDondur( D->Sag );
return SagdanDondur(D);
}
Dugum* Ekle(char * eklenenKelime, Dugum* EklenenDugum)
{
if( EklenenDugum == NULL )
{
EklenenDugum =(Dugum*) malloc( sizeof(struct Dugum) );//bellekten yer alınıyor
if( EklenenDugum== NULL )
printf("bellek alınırken hata oluştu...");
else
{
EklenenDugum->kelimesay=1;//dugum ilk defa eklendiği için kelimesay değeri 1 yapılıyor
EklenenDugum->Derece = 0;
strcpy(EklenenDugum->Kelime,eklenenKelime);//yeni eklenen düğümün kelime değeri belirlendi
EklenenDugum->Sol = NULL;//yeni eleman eklendiği için elemanın sağ ve sol işaretçileri sıfırlandı
EklenenDugum->Sag = NULL;
}
}
else if(strcmp(eklenenKelime , EklenenDugum->Kelime)==-1 )
{
EklenenDugum->Sol = Ekle( eklenenKelime, EklenenDugum->Sol );//ikili ağaçtaki gibi recursiv fonksiyonla ekleme yapılıyor,
if(Derece(EklenenDugum->Sol)-Derece( EklenenDugum->Sag)== 2 )//ikili ağaçtan farklı olarak denge farkı oluşmuşsa döndürme fonksiyonları çağrılıyor
{
if(strcmp( eklenenKelime, EklenenDugum->Sol->Kelime)<0 )//eğer eklenen eleman aynı taraflı ise tek döndürme
EklenenDugum= SoldanDondur(EklenenDugum);
else //değilse çift döndürme işlemi yapılıyor
EklenenDugum = SoldanCiftDondur(EklenenDugum);
}
}
else if(strcmp(eklenenKelime , EklenenDugum->Kelime)==1 )
{
EklenenDugum->Sag = Ekle(eklenenKelime,EklenenDugum->Sag);
if(Derece(EklenenDugum->Sag) -Derece(EklenenDugum->Sol)== 2 )
{
if( strcmp(eklenenKelime , EklenenDugum->Sag->Kelime)==1 )
EklenenDugum= SagdanDondur(EklenenDugum);
else
EklenenDugum= SagdanCiftDondur(EklenenDugum);
}
}
else if(strcmp(eklenenKelime,EklenenDugum->Kelime)==0)
{
EklenenDugum->kelimesay++;
//aynı kelimeden tekrar girilmişse eklenen düğümün kelime sayısını bir arttır
}
EklenenDugum->Derece = Max(Derece(EklenenDugum->Sol),Derece(EklenenDugum->Sag)) + 1;//Kok düğümün derecesi belirleniyor
return EklenenDugum;
}
void Listele( Dugum* T )
{
if( T )
{
Listele( T->Sol );
printf("\n%s %d",T->Kelime,T->kelimesay);
Listele( T->Sag );
}
}
void elemanEkle()
{
char eleman[100];
printf("Eklenecek eleman adı ");
gets(eleman);
Kok=Ekle(eleman,Kok);
}
main()
{
char sec=' ';
while(sec!='C' || sec!='c')
{
printf("\n Ekle\n");
printf(" Listele\n ");
printf(" Cik\n ");
sec=getch();
system("cls");
switch(sec)
{
case 'E': case 'e':elemanEkle();break;
case 'L': case 'l':Listele(Kok);printf("\n");;break;
case 'C': case 'c' :exit(0);break;
}
}
getch();
}
| 