Showing posts with label ikili arama ağacı. Show all posts
Showing posts with label ikili arama ağacı. Show all posts
Kendisine gönderilen ikili arama ağacındaki tek çocuk düğüme sahip olan düğümlerin sayısını veren fonksiyonun c kodu
int TekCocukluDugumSayisi(struct dugum *agac){
if(agac->sag != NULL && agac->sol != NULL){
return TekCocukluDugumSayisi(agac->sol) + TekCocukluDugumSayisi(agac->sag);
}
else if(agac->sag == NULL && agac->sol != NULL){
return 1 + TekCocukluDugumSayisi(agac->sol);
}
else if(agac->sag != NULL && agac->sol == NULL){
return 1 + TekCocukluDugumSayisi(agac->sag);
}
else{
return 0;
}
}
Ağaçlar(İkili Arama Ağacı)
//5.Bölüm-Ağaçlar (İkili Arama Ağacı)
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct dugum
{
int icerik;
struct dugum *sol;
struct dugum *sag;
};
struct ikili_arama_agaci
{
struct dugum *kok; //En tepedeki kısım
};
void ikili_arama_agaci_olustur(struct ikili_arama_agaci **agac)
{
*agac=(struct ikili_arama_agaci *)malloc( sizeof(struct ikili_arama_agaci) ); //4 Bayt'lık yer ayrıldı. (Pointer=>4 Bayt)
if(*agac==NULL)
{
printf("Heap'te gerekli yer ayrilmadi...");
exit(1);
}
(*agac)->kok=NULL;
}
int ikili_agac_bosmu(struct ikili_arama_agaci *agac)
{
if(agac->kok==NULL)
return 1;
else
return 0;
}
struct dugum *dugum_olustur(int icerik)
{
struct dugum *d=(struct dugum *)malloc( sizeof(struct dugum) ); //12 Bayt'lık yer ayrıldı.
if(d==NULL)
{
printf("Heap'te gerekli yer ayrilmadi...");
exit(1);
}
d->icerik=icerik; //(*d).icerik=icerik
d->sol=d->sag=NULL; //Önce sag'a NULL atanıyor sonra bu değer sol'a aktarılıyor.
return d;
}
void ekle(struct ikili_arama_agaci *agac,int icerik)
{
struct dugum *dugum;
struct dugum *d;
struct dugum *geri; //[ ][icerik][geri]
d=agac->kok;
while(d!=NULL)
{
geri=d;
if(icerik < d->icerik)
d=d->sol;
else if(icerik > d->icerik)
d=d->sag;
else
return;
}
dugum=dugum_olustur(icerik);
if(agac->kok==NULL)
{
agac->kok=dugum;
return;
}
if(icerik < geri->icerik)
geri->sol=dugum;
else
geri->sag=dugum;
}
void inorder_yardimci(struct dugum *kok)
{
if(kok==NULL)
return;
inorder_yardimci(kok->sol);
printf("%4d ",kok->icerik);
inorder_yardimci(kok->sag);
}
void inorder(struct ikili_arama_agaci *agac)
{
if(agac==NULL)
return;
inorder_yardimci(agac->kok);
printf("\n");
}
void preorder_yardimci(struct dugum *kok)
{
if(kok==NULL)
return;
printf("%4d ",kok->icerik);
preorder_yardimci(kok->sol);
preorder_yardimci(kok->sag);
}
void preorder(struct ikili_arama_agaci *agac)
{
if(agac==NULL)
return;
preorder_yardimci(agac->kok);
printf("\n");
}
void postorder_yardimci(struct dugum *kok)
{
if(kok==NULL)
return;
postorder_yardimci(kok->sol);
postorder_yardimci(kok->sag);
printf("%4d ",kok->icerik);
}
void postorder(struct ikili_arama_agaci *agac)
{
if(agac==NULL)
return;
postorder_yardimci(agac->kok);
printf("\n");
}
int dugum_sayisi(struct dugum *kok)
{
if(kok==NULL)
return 0;
return 1+dugum_sayisi(kok->sol)+dugum_sayisi(kok->sag);
}
int yaprak_sayisi(struct dugum *kok)
{
if(kok==NULL)
return 0;
if(kok->sol==NULL && kok->sag==NULL)
return 1;
else
return yaprak_sayisi(kok->sol)+yaprak_sayisi(kok->sag);
}
void sil(struct ikili_arama_agaci *agac,int silinen)
{
struct dugum *d=agac->kok;
struct dugum *parent=NULL; //Silinen elemanın bir üstü.
struct dugum *d1,*d2;
int sol; //Parentin solundan.
while(d!=NULL)
{
if(silinen < d->icerik) //Silinmeye soldan devam edilir.
{
parent=d;
d=d->sol;
sol=1; //Silinen elemana nereden yaklaşıldığını tespit etmek için.
}
else if(silinen > d->icerik)
{
parent=d;
d=d->sag;
sol=0;
}
else
break;
}
if(d==NULL)
return;
if(d->sol==NULL) //Silinen düğümün solu boş.
{
if(parent==NULL)
agac->kok=d->sag;
else
{
if(sol==1)
parent->sol=d->sag;
else
parent->sag=d->sag;
}
}
else if(d->sag==NULL) //Silinen düğümün sağı boş.
{
if(parent==NULL)
agac->kok=d->sol;
else
{
if(sol==1)
parent->sol=d->sol;
else
parent->sag=d->sol;
}
}
else //Silinen düğümün hem sağı hem de solu dolu.
{ //Silinecek düğümün solunun en sağına git.
//En sağdaki düğüm silinen düğümün konumunu alır.
d1=d->sol;
d2=NULL;
while(d1->sag!=NULL)
{
d2=d1;
d1=d1->sag;
}
if(d2!=NULL)
{
d2->sag=d1->sol;
d1->sol=d->sol;
}
d1->sag=d->sag;
if(parent==NULL)
agac->kok=d1; //Ağacın kökü değişti.
else
{
if(sol==1)
parent->sol=d1;
else
parent->sag=d1;
}
}
/*else //Silinen düğümün hem sağı hem de solu dolu.
{ //Silinecek düğümün sağının en soluna git.
//En soldaki düğüm silinen düğümün konumunu alır.
d1=d->sag;
d2=NULL;
while(d1->sol!=NULL)
{
d2=d1;
d1=d1->sol;
}
if(d2!=NULL)
{
d2->sag=d1->sag;
d1->sol=d->sag;
}
d1->sag=d->sol;
if(parent==NULL)
agac->kok=d1; //Ağacın kökü değişti.
else
{
if(sol==1)
parent->sol=d1;
else
parent->sag=d1;
}
}*/
}
void yoket(struct dugum **kok) //Kök değişeceği için ** .
{
if(*kok!=NULL)
{
yoket( &(*kok)->sol );
yoket( &(*kok)->sag );
free(*kok);
*kok=NULL;
}
}
int main()
{
struct ikili_arama_agaci *agac; //Başlangıç değeri random bir değer.
ikili_arama_agaci_olustur(&agac);
/*Not 1:
Yazdırma Biçimleri: 100
Inorder: 5-80-100-200 80 200
Preorder: 100-80-5-200 5
Postorder: 5-80-200-100
*/
/*Not 2:
struct dugum d; => Nesnenin kendisi. (*d).icerik şeklinde bir tanımlama olamaz!
struct dugum *p; => Nesnenin göstericisi. (*p).icerik || p->icerik şeklinde tanımlanabilir.
*/
/*Not 3:
ekle(agac,100); 100
ekle(agac,80); 80 120
ekle(agac,45); 45 167
ekle(agac,120); 150
ekle(agac,167);
ekle(agac,150);
inorder(agac); //45 80 100 120 150 167
preorder(agac); //100 80 45 120 167 150
postorder(agac); //45 80 150 167 120 100
printf( "Dugum Sayisi: %4d\n",dugum_sayisi(agac->kok) ); //Düğüm Sayısı:6
printf( "Yaprak Sayisi: %4d\n",yaprak_sayisi(agac->kok) ); //Yaprak Sayısı:2
*/
ekle(agac,100);
ekle(agac,50);
ekle(agac,200);
ekle(agac,25);
ekle(agac,75);
ekle(agac,20);
ekle(agac,35);
ekle(agac,98);
ekle(agac,99);
ekle(agac,500);
ekle(agac,400);
ekle(agac,300);
ekle(agac,210);
ekle(agac,375);
inorder(agac); //20 25 35 50 75 98 99 100 200 210 300 375 400 500
preorder(agac); //100 50 25 20 35 75 98 99 200 500 400 300 210 375
postorder(agac); //20 35 25 99 98 75 50 210 375 300 400 500 200 100
/*
[100]----
[50] [200]--------
[25] [75] [500]
[20][35] [98] [400]
[99] [300]
[210][375]
*/
//sil(agac,50);
//preorder(agac);
//yoket(&agac->kok);
//preorder(agac);
getch();
return 0;
}