Home / Veri Yapıları / İkili Arama Ağacı (BST) Eleman Ekleme İşlemi

İkili Arama Ağacı (BST) Eleman Ekleme İşlemi

BST üzerinde eleman ekleme işlemi de İkili Arama Ağacı Search işlemine benzer bir şekilde yapılır. Eklemenin doğru konumda olması önemlidir. Zira İkili Arama Ağacı yapısını bozmamız gerektiğinden doğru konumu bulmak için Search işlemi yaparız, ancak bu arama işleminde aranan düğüm değil, NULL değerdir. Zira ancak boş olan konuma ekleme yapabiliriz.

İkili Arama Ağacı (BST) Eleman Ekleme Örneği

İçerik

Arama örneğinde kullandığımız yapıyı kullanarak ekleme yapalım;

ikili arama ağacı örneği

Yukarıdaki yapıya 19 sayısını eklemek isteyelim.

  1. Adım: Kökten başlarız. 19 sayısı 25’ten küçük olduğu için sol çocuğa (15) gideriz.
  2. Adım: 19 sayısı 15’den büyüktür bu yüzden sağ çocuğa (22) gideriz.
  3. Adım: 19 sayısı 22’den küçüktür. Bu yüzden sol çocuğa (18) gideriz.
  4. Adım: 19 sayısı 18’den büyüktür. Sağ alt çocuğa bakarız, olmadığını NULL olduğunu görürüz. Bu yüzden 19 sayısını 18’in sağ alt çocuğu olacak şekilde yerleştiririz.

İkili Arama Ağacı Eleman Ekleme C Kodu

BST eleman ekleme C kodu paylaşılmıştır. Gerekli yerlere Türkçe yorum eklenmiştir.


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

//İkili arama ağacı düğüm yapısı aşağıdaki şekildedir.
//key değeri düğümün alacağı değerdir.
//Her düğümün 2 çocuğu olabileceği için left ve right işaretçilerini almıştır
struct node
{
    int key;
    struct node *left, *right;
};
  
// Bu fonksiyon verilen değerde düğüm oluşturur.
struct node *newNode(int item)
{
    struct node *temp =  (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    //Her yeni eklenen düğüm leaf durumunda olduğundan sol ve sağ işaretçiler null değerini gösterir
    temp->left = temp->right = NULL;
    return temp;
}
  
//BST'yi traverse eden fonksiyon
//özyinelemelidir.
void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d \n", root->key);
        inorder(root->right);
    }
}
  
// ekleme yapan esas fonksiyonumuz bu
struct node* insert(struct node* node, int key)
{
    /* Eğer düğüm NULL ise doğru konum demektir ve insert işlemi burada yapılır */
    if (node == NULL) return newNode(key);
 
    /* NULL değeri bulunamadıysa aşağıdaki kısım çalışır */
    if (key < node->key)
        node->left  = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);   
 
    /* değiştirilmemiş düğümü return eder */
    return node;
}
  
// test etme kısmı istediğiniz gibi değerileri değiştirebilirsiniz
int main()
{
    /* aşağıdaki ağaç yapısını oluşturalım
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
    struct node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
  
    // Ağacı yazdırıyoruz
    inorder(root);
  
    return 0;
}

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir