Binary Tree (İkili Ağaç)
İstersen buraya tıklayarak açıklamalı binary tree kodunu indirebilirsin.
#include <stdio.h>
#include <stdlib.h>
/**
* İkili ağaç yapısı
* @author Yunus Emre AK
*/
/**
* İkili ağaç yapısında, daldaki değerden
* küçük ise soluna
* büyük ise sağına yazılır.
*
* 11
* / \
* 7 14
* / \ / \
* 3 8 12 18
*
*/
typedef struct _dal{
int veri;
_dal* solundaki;
_dal* sagindaki;
}dal;
// Kullanıcı arayüzünüdeki yazıları oluşturan fonksiyon (Anlaşılabilirlik için.)
void menu();
// Kullanıcı arayüzünü oluşturan fonksiyon (Anlaşılabilirlik için.)
void loop(dal **);
// Ağacı oluşturmak için kullanılan fonksiyon.
void create(dal **);
// Bellek ayırmak için fonksiyon. (Tamamen kolaylık amaçlıdır.)
dal* get_leaf();
// İkili ağaç yapısına veri ekleme fonksiyonu.
void insert(dal*);
// Ağactaki verileri sıralayıp ekrana yazan fonksiyon (Anlaşılabilirlik için.)
void sort_disploy(dal*);
// Ağacta veri arama ve verinin bulundağı dalı geri döndüren fonksiyon.
dal* search(dal*, int);
// Ağacın dalları silen fonksiyon.
void destroy_leaf(dal*);
// Ağacı komple silen fonksiyon
void destroy_tree(dal**);
int main(){
dal *agacim = NULL;
loop(&agacim);
}
// Fonksiyonlar;
dal* get_leaf(){
return (dal*)malloc(sizeof(dal));
}
void insert(dal* gelen_dal, int veri){
// Eğer gelen dal boş ise, yeni dal oluşturup veriyi atıyoruz.
if(gelen_dal == NULL){
printf("\n Agac yapisi mevcut degil. Lutfen once agaci olusturunuz.");
return;
}
// Öncelikle gelen verinin baslangıç verimizden küçük olma durumunu inceliyoruz.
if(veri < gelen_dal->veri){
/**
* Eğer gelen veri, baş veriden "küçükse" dallarındaki diğer verileriyle de kıyaslamamız
* lazım. Bu kıyaslama işlemi, küçük olma durumunu incelediğimiz için ağacın
* başlangıcınının sol tarafında dal olmayana kadar devam etmeli.
*/
if(gelen_dal->solundaki != NULL)
/**
* Eğer dalın sonundaki null değilse, tekrardan ekleme fonksiyonunu çağırcağız.
* Bu sayede her alt dal için başlangıç dalına uygulamış olduğumuz işlemler
* uygulanacak.
*/
insert(gelen_dal->solundaki, veri);
/**
* Eğer dalın solunda başka dal yoksa, soluna yeni bir dal uluşturup veriyi atıyacağız.
* 11
* /
* (Yeni Dal)
* / \
* NULL NULL
*/
else{
// Yeni dalımız için gelen dalın soluna dal oluşturuyoruz.
gelen_dal->solundaki = get_leaf();
// Gelen dalın soluna eklenen dala, gelen veriyi atıyoruz.
gelen_dal->solundaki->veri = veri;
/**
* Gelen dalın solunda oluşturulan daldan sonra dal olmadığı için her yönüne
* de NULL atıyoruz.
*/
gelen_dal->solundaki->solundaki = NULL;
gelen_dal->solundaki->sagindaki = NULL;
}
}
/**
* Eğer gelen veri, baş veriden "küçük değilse" dallarındaki diğer verileriyle de kıyaslamamız
* lazım. Bu kıyaslama işlemi, küçük olma durumunu incelediğimiz için ağacın
* başlangıcınının sağ tarafında dal olmayana kadar devam etmeli.
*/
else{
if(gelen_dal->sagindaki != NULL)
/**
* Eğer dalın sonundaki null değilse, tekrardan ekleme fonksiyonunu çağırcağız.
* Bu sayede her alt dal için başlangıç dalına uygulamış olduğumuz işlemler
* uygulanacak.
*/
insert(gelen_dal->sagindaki, veri);
/**
* Eğer dalın sağında başka dal yoksa, sağında yeni bir dal uluşturup veriyi atıyacağız.
* 11
* \
* (Yeni Dal)
* / \
* NULL NULL
*/
else{
// Yeni dalımız için gelen dalın sağına dal oluşturuyoruz.
gelen_dal->sagindaki = get_leaf();
// Gelen dalın sağına oluşturulan yeni dala veriyi atıyoruz.
gelen_dal->sagindaki->veri = veri;
/**
* Gelen dalın sağında oluşturulan daldan sonra dal olmadığı için her yönüne
* de NULL atıyoruz.
*/
gelen_dal->sagindaki->sagindaki = NULL;
gelen_dal->sagindaki->solundaki = NULL;
}
}
}
dal *search(dal* gelen_dal, int istenen_veri){
// Sadece gelen dalda veri olduğu sürece işlem yapabiliriz.
if(gelen_dal != NULL){
// İlk olarak istenen veri gelen dalın verisi olup olmadığını kontrol ediyoruz.
if(gelen_dal->veri == istenen_veri)
return gelen_dal;
/**
* Eğer istenen veri gelen daldan küçükse;
* Ekleme yaparken küçük verileri gelen dalın soluna eklediğimiz için, bu fonksiyonu
* gelen dalın solundaki dalı parametre vererek tekrar çağıracağız.
*/
if(istenen_veri < gelen_dal->veri)
search(gelen_dal->solundaki, istenen_veri);
/**
* Eğer istenen veri gelen daldan küçük değilse yani gelen daldan büyük veya dala eşitse;
* Ekleme yaparken küçük olmayan verileri gelen dalın sağına eklediğimiz için, bu fonksiyonu
* gelen dalın sağındaki dalı parametre vererek tekrar çağıracağız.
*/
else
search(gelen_dal->sagindaki, istenen_veri);
// Hiçbir koşul gerçekleşmiyorsa, istenen veri dalda mevcut değil demektir.
}
else
return NULL;
}
void destroy_leaf(dal *gelen_dal){
/**
* (Agacın kökü (en üst verisi) gönderilirse, tüm ağacı siler.)
* 11 11
* / \ / \
* 7 14 -> 7 14
* / \ / \ / \ / \
* 3 8 12 18 NULL NULL NULL NULL
*
* Alttan üste doğru silme işlemi yapmalıyız.
*
*/
// Öncelikle gelen dal boş (NULL) değilse işlem yapılır.
if(gelen_dal != NULL){
/**
* Ağacın verileri silmeden önce ağacın dallarını temizlememiz gerekiyor,
* aksi halde diğer dallara erişimimiz kesilecek ve dallar için ayrılan bellekleri
* serbest bırakamayacağız. Bu sebeple bu fonksiyonu ağacın hem sağındaki hem de
* solundaki dalları için tekrar çağırmamız, en sonda ağacın verisini silmemiz
* gerekir.
*/
destroy_leaf(gelen_dal->sagindaki);
destroy_leaf(gelen_dal->solundaki);
// Sağındaki ve solundaki tüm dallar silindikten sonra, ağacın baş verisi silinir.
free(gelen_dal);
}
}
void destroy_tree(dal **gelen_agac){
// Öncelikle gelen dal boş (NULL) değilse işlem yapılır.
if(*gelen_agac != NULL){
// Agacin dallarını sildiriyoruz.
destroy_leaf(*gelen_agac);
// Gelen agacta dal kalmadığı için agaca NULL atıyoruz.
*gelen_agac = NULL;
}
}
void display_tree(dal *gelen_dal){
if(gelen_dal != NULL){
if(gelen_dal->solundaki != NULL)
printf("| %d", gelen_dal->solundaki->veri);
if(gelen_dal->sagindaki != NULL)
printf("| %d", gelen_dal->sagindaki->veri);
}
}
void sort_display(dal *gelen_dal){
if(gelen_dal == NULL){
printf("\nGosterilecek agac yok.");
return;
}
if(gelen_dal->solundaki != NULL){
sort_display(gelen_dal->solundaki);
}
printf("%d-",gelen_dal->veri);
if(gelen_dal->sagindaki != NULL)
sort_display(gelen_dal->sagindaki);
}
void menu(){
printf("\n***************************\n");
// Görsel hizalama için "%30s" 30 karakterlik alana sağa dayalı yazdırdık.
printf("->%30s\n"," Agaci olusturmak icin 1'e");
printf("->%30s\n"," Agaca sayi eklemek icin 2'e");
printf("->%30s\n"," Agaci gostermek icin 3'e");
printf("->%30s\n"," Agaci silmek icin 4'e");
printf("->%30s\n"," Cikmak icin 0'a");
}
void loop(dal **agacim){
int x = 5;
while(x !=0){
menu();
/**
* Dipnot : Boşluk %c (" %c") yazılırsa, öncesinde basılan enter'ı veri olarak ("\n") görmez, hatalar engellenir.
* %d kullanımı için bir satır atlatma karakteri algılama durumu olmaz.
*/
scanf("%d", &x);
switch(x){
case 1:
create(agacim);
break;
case 2:
printf("\nLutfen eklemek istediginiz veriyi giriniz:\t");
int eklenecek_veri;
scanf(" %d",&eklenecek_veri);
insert(*agacim, eklenecek_veri);
break;
case 3:
printf("Agacin verilerinin siralanmis hali:\n");
sort_display(*agacim);
break;
case 4:
printf("\nAgac silindi.\n");
destroy_tree(agacim);
break;
default:
break;
}
}
}
void create(dal **agac){
if(*agac == NULL)
*agac =get_leaf();
printf("\nAgacin ilk verisini giriniz:\t");
int bas_veri;
scanf(" %d", &bas_veri);
(*agac)->veri = bas_veri;
(*agac)->sagindaki = NULL;
(*agac)->solundaki = NULL;
printf("\nAgac %d verisiyle olusturuldu.", bas_veri);
}
#include <stdio.h>
#include <stdlib.h>
/**
* İkili ağaç yapısı
* @author Yunus Emre AK
*/
/**
* İkili ağaç yapısında, daldaki değerden
* küçük ise soluna
* büyük ise sağına yazılır.
*
* 11
* / \
* 7 14
* / \ / \
* 3 8 12 18
*
*/
typedef struct _dal{
int veri;
_dal* solundaki;
_dal* sagindaki;
}dal;
// Kullanıcı arayüzünüdeki yazıları oluşturan fonksiyon (Anlaşılabilirlik için.)
void menu();
// Kullanıcı arayüzünü oluşturan fonksiyon (Anlaşılabilirlik için.)
void loop(dal **);
// Ağacı oluşturmak için kullanılan fonksiyon.
void create(dal **);
// Bellek ayırmak için fonksiyon. (Tamamen kolaylık amaçlıdır.)
dal* get_leaf();
// İkili ağaç yapısına veri ekleme fonksiyonu.
void insert(dal*);
// Ağactaki verileri sıralayıp ekrana yazan fonksiyon (Anlaşılabilirlik için.)
void sort_disploy(dal*);
// Ağacta veri arama ve verinin bulundağı dalı geri döndüren fonksiyon.
dal* search(dal*, int);
// Ağacın dalları silen fonksiyon.
void destroy_leaf(dal*);
// Ağacı komple silen fonksiyon
void destroy_tree(dal**);
int main(){
dal *agacim = NULL;
loop(&agacim);
}
// Fonksiyonlar;
dal* get_leaf(){
return (dal*)malloc(sizeof(dal));
}
void insert(dal* gelen_dal, int veri){
// Eğer gelen dal boş ise, yeni dal oluşturup veriyi atıyoruz.
if(gelen_dal == NULL){
printf("\n Agac yapisi mevcut degil. Lutfen once agaci olusturunuz.");
return;
}
// Öncelikle gelen verinin baslangıç verimizden küçük olma durumunu inceliyoruz.
if(veri < gelen_dal->veri){
/**
* Eğer gelen veri, baş veriden "küçükse" dallarındaki diğer verileriyle de kıyaslamamız
* lazım. Bu kıyaslama işlemi, küçük olma durumunu incelediğimiz için ağacın
* başlangıcınının sol tarafında dal olmayana kadar devam etmeli.
*/
if(gelen_dal->solundaki != NULL)
/**
* Eğer dalın sonundaki null değilse, tekrardan ekleme fonksiyonunu çağırcağız.
* Bu sayede her alt dal için başlangıç dalına uygulamış olduğumuz işlemler
* uygulanacak.
*/
insert(gelen_dal->solundaki, veri);
/**
* Eğer dalın solunda başka dal yoksa, soluna yeni bir dal uluşturup veriyi atıyacağız.
* 11
* /
* (Yeni Dal)
* / \
* NULL NULL
*/
else{
// Yeni dalımız için gelen dalın soluna dal oluşturuyoruz.
gelen_dal->solundaki = get_leaf();
// Gelen dalın soluna eklenen dala, gelen veriyi atıyoruz.
gelen_dal->solundaki->veri = veri;
/**
* Gelen dalın solunda oluşturulan daldan sonra dal olmadığı için her yönüne
* de NULL atıyoruz.
*/
gelen_dal->solundaki->solundaki = NULL;
gelen_dal->solundaki->sagindaki = NULL;
}
}
/**
* Eğer gelen veri, baş veriden "küçük değilse" dallarındaki diğer verileriyle de kıyaslamamız
* lazım. Bu kıyaslama işlemi, küçük olma durumunu incelediğimiz için ağacın
* başlangıcınının sağ tarafında dal olmayana kadar devam etmeli.
*/
else{
if(gelen_dal->sagindaki != NULL)
/**
* Eğer dalın sonundaki null değilse, tekrardan ekleme fonksiyonunu çağırcağız.
* Bu sayede her alt dal için başlangıç dalına uygulamış olduğumuz işlemler
* uygulanacak.
*/
insert(gelen_dal->sagindaki, veri);
/**
* Eğer dalın sağında başka dal yoksa, sağında yeni bir dal uluşturup veriyi atıyacağız.
* 11
* \
* (Yeni Dal)
* / \
* NULL NULL
*/
else{
// Yeni dalımız için gelen dalın sağına dal oluşturuyoruz.
gelen_dal->sagindaki = get_leaf();
// Gelen dalın sağına oluşturulan yeni dala veriyi atıyoruz.
gelen_dal->sagindaki->veri = veri;
/**
* Gelen dalın sağında oluşturulan daldan sonra dal olmadığı için her yönüne
* de NULL atıyoruz.
*/
gelen_dal->sagindaki->sagindaki = NULL;
gelen_dal->sagindaki->solundaki = NULL;
}
}
}
dal *search(dal* gelen_dal, int istenen_veri){
// Sadece gelen dalda veri olduğu sürece işlem yapabiliriz.
if(gelen_dal != NULL){
// İlk olarak istenen veri gelen dalın verisi olup olmadığını kontrol ediyoruz.
if(gelen_dal->veri == istenen_veri)
return gelen_dal;
/**
* Eğer istenen veri gelen daldan küçükse;
* Ekleme yaparken küçük verileri gelen dalın soluna eklediğimiz için, bu fonksiyonu
* gelen dalın solundaki dalı parametre vererek tekrar çağıracağız.
*/
if(istenen_veri < gelen_dal->veri)
search(gelen_dal->solundaki, istenen_veri);
/**
* Eğer istenen veri gelen daldan küçük değilse yani gelen daldan büyük veya dala eşitse;
* Ekleme yaparken küçük olmayan verileri gelen dalın sağına eklediğimiz için, bu fonksiyonu
* gelen dalın sağındaki dalı parametre vererek tekrar çağıracağız.
*/
else
search(gelen_dal->sagindaki, istenen_veri);
// Hiçbir koşul gerçekleşmiyorsa, istenen veri dalda mevcut değil demektir.
}
else
return NULL;
}
void destroy_leaf(dal *gelen_dal){
/**
* (Agacın kökü (en üst verisi) gönderilirse, tüm ağacı siler.)
* 11 11
* / \ / \
* 7 14 -> 7 14
* / \ / \ / \ / \
* 3 8 12 18 NULL NULL NULL NULL
*
* Alttan üste doğru silme işlemi yapmalıyız.
*
*/
// Öncelikle gelen dal boş (NULL) değilse işlem yapılır.
if(gelen_dal != NULL){
/**
* Ağacın verileri silmeden önce ağacın dallarını temizlememiz gerekiyor,
* aksi halde diğer dallara erişimimiz kesilecek ve dallar için ayrılan bellekleri
* serbest bırakamayacağız. Bu sebeple bu fonksiyonu ağacın hem sağındaki hem de
* solundaki dalları için tekrar çağırmamız, en sonda ağacın verisini silmemiz
* gerekir.
*/
destroy_leaf(gelen_dal->sagindaki);
destroy_leaf(gelen_dal->solundaki);
// Sağındaki ve solundaki tüm dallar silindikten sonra, ağacın baş verisi silinir.
free(gelen_dal);
}
}
void destroy_tree(dal **gelen_agac){
// Öncelikle gelen dal boş (NULL) değilse işlem yapılır.
if(*gelen_agac != NULL){
// Agacin dallarını sildiriyoruz.
destroy_leaf(*gelen_agac);
// Gelen agacta dal kalmadığı için agaca NULL atıyoruz.
*gelen_agac = NULL;
}
}
void display_tree(dal *gelen_dal){
if(gelen_dal != NULL){
if(gelen_dal->solundaki != NULL)
printf("| %d", gelen_dal->solundaki->veri);
if(gelen_dal->sagindaki != NULL)
printf("| %d", gelen_dal->sagindaki->veri);
}
}
void sort_display(dal *gelen_dal){
if(gelen_dal == NULL){
printf("\nGosterilecek agac yok.");
return;
}
if(gelen_dal->solundaki != NULL){
sort_display(gelen_dal->solundaki);
}
printf("%d-",gelen_dal->veri);
if(gelen_dal->sagindaki != NULL)
sort_display(gelen_dal->sagindaki);
}
void menu(){
printf("\n***************************\n");
// Görsel hizalama için "%30s" 30 karakterlik alana sağa dayalı yazdırdık.
printf("->%30s\n"," Agaci olusturmak icin 1'e");
printf("->%30s\n"," Agaca sayi eklemek icin 2'e");
printf("->%30s\n"," Agaci gostermek icin 3'e");
printf("->%30s\n"," Agaci silmek icin 4'e");
printf("->%30s\n"," Cikmak icin 0'a");
}
void loop(dal **agacim){
int x = 5;
while(x !=0){
menu();
/**
* Dipnot : Boşluk %c (" %c") yazılırsa, öncesinde basılan enter'ı veri olarak ("\n") görmez, hatalar engellenir.
* %d kullanımı için bir satır atlatma karakteri algılama durumu olmaz.
*/
scanf("%d", &x);
switch(x){
case 1:
create(agacim);
break;
case 2:
printf("\nLutfen eklemek istediginiz veriyi giriniz:\t");
int eklenecek_veri;
scanf(" %d",&eklenecek_veri);
insert(*agacim, eklenecek_veri);
break;
case 3:
printf("Agacin verilerinin siralanmis hali:\n");
sort_display(*agacim);
break;
case 4:
printf("\nAgac silindi.\n");
destroy_tree(agacim);
break;
default:
break;
}
}
}
void create(dal **agac){
if(*agac == NULL)
*agac =get_leaf();
printf("\nAgacin ilk verisini giriniz:\t");
int bas_veri;
scanf(" %d", &bas_veri);
(*agac)->veri = bas_veri;
(*agac)->sagindaki = NULL;
(*agac)->solundaki = NULL;
printf("\nAgac %d verisiyle olusturuldu.", bas_veri);
}
Yorumlar
Yorum Gönder