İkili Arama Ağacı Arama Yapma İşlemi

Bir önceki yazımızda ikili arama ağacı yapısına dair genel bir bilgi vermiştik. Bu yazımızda ise BST (Binary Search Tree) yapısında nasıl aradığımız düğümü bulabiliriz ona bakacağız. Elbette bunu C kodu aracılığıyla yapacağız.

ikili arama ağacı adımları


Her şeyden önce ağaçtaki düğümlerin bilgilerini tutan bir struct yapısı oluşturmamız gerekli

İkili Arama Ağacı Oluşturma C Kodu

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};
Gördüğünü kod ikili arama ağacı yapısında bulunan tüm bilgileri tutmaktadır. Data bilgisi tuttuğumuz sayıdır, leftChild, sol çocuk, rightChild ise sağ çocuktur. Bu bilgiler sayesinde tüm ağacımızın yapısını tutabileceğiz.

İkili Arama Ağacı Arama Yapma C Kodu

struct node* search(int data){
   struct node *current = root;
   printf("Gezilen dugumler: ");
 
   while(current->data != data){
 
      if(current != NULL) {
         printf("%d ",current->data);
   
         //sol alt agaci tara
         if(current->data > data){
            current = current->leftChild;
         }//sag alt agaci tara
         else {                
            current = current->rightChild;
         }
   
         //bulunamadıgı durumda
         if(current == NULL){
            return NULL;
         }
      }   
   }
   return current;
}
Yukarıdaki kod ile rahatça arama yapabilirsiniz. Fonksiyona gönderilen veriyi, ağaç içerisinde arar. Peki nasıl arar? Öncelikli olarak bir tane current adında node oluşturuyoruz. Bu düğüme root düğümünü atıyoruz, yani aramaya root düğümünden başlayacağız.

while döngümüzü oluşturuyoruz, curtten->data != data olduğu müddetçe döngümüz dönecek.

Eğer gezilen düğüm boş değilse (NULL değilse daha doğrusu) ekrana yazdırıyoruz. Peki aramayı nasıl yapıyoruz?

Burada BST yapısının temel kuralını uyguluyoruz. Eğer current->data > data (current->data değeri data değerinden büyükse) current = current -> leftChild yapıyoruz. Yani sol alt ağacı tarıyoruz. Değilse sağ alt ağacı tarıyoruz. Bu işlem while döngümüz boyunca sürüyor, çünkü while döngümüz doğru datayı bulunca sona eriyor.

İkili Arama Ağaçlarında arama yapma işleminin temel şartı, mevcut değerimizin aradığımız değerden büyük olup olmamasıdır. Eğer büyükse sol çocuk, değilse sağ çocuk taranır.

Etiketler: , ,