#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(); 
}