C’de İkili Arama Ağacı

Bu yazıda ikili arama ağacının C dilinde nasıl kodlanabileceğine dair basit bir örnek göreceksiniz. Yazmış olduğum program ikili bir arama ağacı oluşturur. Daha sonra kullanıcıdan bir değer alarak, bu değer kadar rastgele sayı oluşturur ve bunları arama ağacına ekler. Ekleme tamamlandıktan sonra ağacı inorder (kök ortada) dolaşarak rastgele yaratıp ağaca eklediği tüm sayıları listeler.

Kullanıcı daha sonra ağaçta bu sayıları arayabilir. Eğer sayı bulunursa ve bulunan sayı yaprak düğümdeyse (leaf node) girdi silinir. Eğer yaprak düğümde değilse sadece ekrana sayının bulunduğunu belirten bir yazı yazdırılır.

Bu kod ağaç yapısının C’de nasıl modellenebileceğini gösteren basit bir koddur. İkili arama ağacı hakkında daha gelişmiş bir örnek arıyorsanız şuradaki programın içinde JAVA dilinde kodlanmış bir ikili arama ağacı geçmektedir. (dengeleme işlemi yoktur)

Ağaç nedir ne değildir, bunu öğrenmek için kutsal bilgi kaynağımız Wikipedia’ya buradan gidebilirsiniz.

#include <stdio.h>
#include <stdlib.h>

struct tree_el {
   int deger;
   char karakter;
   struct tree_el * sag, * sol;
};

typedef struct tree_el dugum;

void beklet();
void ekle(dugum**,dugum*);
void inorder(dugum*);
void preorder(dugum*);
void postorder(dugum*);
int ara(int,dugum*,dugum*);
void ikili_agac();
int main();

void beklet() {
    /* Bu fonksiyonun tek amaci kullaniciyi bir tusa basana kadar
       bekletmek, ve sonra ekrani silmektir. */
    printf("\nDevam etmek icin bir tusa basin.");
    getche();
    system ("cls");
}

void ekle(dugum **tree, dugum *item) {
   if(!(*tree)) {
      *tree = item;
      return;
   }
   if(item->deger<(*tree)->deger)
      ekle(&(*tree)->sol, item);
   else if(item->deger>(*tree)->deger)
      ekle(&(*tree)->sag, item);
}

void inorder(dugum *tree) {
    if(tree == NULL) {
        printf("Agac bos.");
        return;
    }
    if(tree->sol) inorder(tree->sol);
    printf("%d\n",tree->deger);
    if(tree->sag) inorder(tree->sag);
}

void preorder(dugum *tree) {
    if(tree == NULL) {
        printf("Agac bos.");
        return;
    }
    printf("%d\n",tree->deger);
    if(tree->sol) preorder(tree->sol);
    if(tree->sag) preorder(tree->sag);
}

void postorder(dugum *tree) {
    if(tree == NULL) {
        printf("Agac bos.");
        return;
    }
    if(tree->sol) postorder(tree->sol);
    if(tree->sag) postorder(tree->sag);
    printf("%d\n",tree->deger);
}

int ara(int aranacak, dugum *d, dugum *onceki) {
    if(d->deger == aranacak) {
        printf("Buldum.\n");
        if(d->sol == NULL && d->sag ==  NULL) {
            if(onceki) {
                if (onceki->sol == d) {
                    onceki->sol = NULL;
                }
                if (onceki->sag == d) {
                    onceki->sag = NULL;
                }
            } else {
                printf("Kok dugumu de sildim, her sey bitti!\n");
                free(d);
                return -1;
            }
            free(d);
            printf("Bulunan deger yaprakta. Sildim.\n");
        } else {
            printf("Bulunan deger yaprakta degil.\n");
        }
        return 1;
    } else if (d->deger > aranacak) {
        onceki = d;
        d = d->sol;
    } else {
        onceki = d;
        d = d->sag;
    }

    if (d == NULL) {
        printf("Bulamadim.\n");
        return;
    } else {
        ara(aranacak, d, onceki);
    }

    return 1;
}

void ikili_agac() {
    srand((unsigned) time(NULL));

    /* Agac icin gerekli tanimlamalar */
    dugum *simdiki, *kok;
    int i, aranacak,durum = 1;
    int agactaki_eleman_sayisi;

    printf("Agaca kac tane rastgele sayi yerlesmesini isterseniz? ");
    scanf("%d",&agactaki_eleman_sayisi);

    kok = NULL;
    /* Boylece bos bir agac tanimlanir. */

    /* Agaca rastgele sayilar eklenir. */
    for(i=1;i<=agactaki_eleman_sayisi;i++) {
      simdiki = (dugum*)malloc(sizeof(dugum)); /* Bellekte dugume yer acilir. */
      simdiki->sol = simdiki->sag = NULL; /* Dugumun yaprak olmasi saglanir. */
      simdiki->deger = rand()%100; /* Dugume rastgele bir deger atanir. */
      ekle(&kok, simdiki); /* Dugum eklenir. */
    }

    if (kok == NULL) {
        printf("Agaca eleman eklenmedi.");
        return;
    }
    /* Agac ekrana yazdirilir. (inorder gezilerek) */
    while(durum == 1) {
        if (durum != 1) {
            printf("Agac bos");
            return;
        }
        inorder(kok);

        /* Aranacak bir deger ister. -1 ile programi sonlandirabilirsiniz. */
        printf("Yukaridaki degerler rastgele yaratildi ve agactalar.\nCikis icin -1 yazabilirsiniz.\nAranacak bir deger giriniz: ");
        scanf("%d",&aranacak);
        if(aranacak == -1) {
            return;
        }
        system("cls");

        /* Elelani arar ve gerekli islemleri yapar. Eger agac bosalmisa -1 dondurur. */
        durum = ara(aranacak, kok, NULL);
    }
}

int main() {
    ikili_agac();
    beklet();
    return 0;
}