Binary Tree

Kategori: C , 05 Temmuz 2019 , JanFranco


Binary tree ağaç yapısı bir kökten(root) ve yapraklardan(leaves/leaf) oluşur. Ağaca ilk eklenen veri, köktür. Daha sonra eklenecek veriler kökteki değere göre saklanır. Genellikle daha büyük veriler sağda, daha küçükler solda saklanır. Büyüklükten kasıt kaplanan yer değildir. Örneğin ağaca ilk gönderilen değer 5 olsun. 5 değeri kökte saklanır. Bir sonraki gönderilen değer 7 olsun. 7 değeri sağ tarafta saklanır. Bir sonraki gönderilen değer 1 olsun. 1 değeri sol tarafta saklanır. Böylece aşağıdaki yapı oluşur:

        5
       / \
     1   7

 

Ağaç yapısını implemente edelim. İlk olarak yaprakların node'larının verilerini tutacak bir struct yazalım:

struct node{
    int value;
    struct node *left;
    struct node *right;
};
Ağaca veri ekleyen fonksiyon yazalım. Recursive mantığı ile kodlarsak, eğer eklenecek verinin değeri kökten büyükse fonksiyon tekrar çağırılacak ancak parametre olarak ağaç değil ağacın sağ tarafı gönderilecek. Eğer büyük değilse aynı işlemler ağacın sol tarafı için yapılacak. Fonksiyonların da sonlanması için bir NULL kontrolü yapılacak:

struct node *insert_to_tree(struct node *tree, int value){
    if(tree == NULL){
        struct node *root = malloc(sizeof(struct node));
        root->left = NULL;
        root->right = NULL;
        root->value = value;
        return root;
    }

    if(value > tree->value){
        tree->right = insert_to_tree(tree->right, value);
        return tree;
    }

    tree->left = insert_to_tree(tree->left, value);
    return tree;
}
Ağaçtan veri silmek için yazacağımız fonksiyonda, ağaçtaki maksimum ve minimum değerleri kullanacağız. Bu değerleri hesaplayan iki fonksiyon yazalım:

int find_max(struct node *tree){
   if(tree == NULL){
        return;
    }
    while(tree->right != NULL){
        tree = tree->right;
    }
    return tree->value;
}

int find_min(struct node *tree){
   if(tree == NULL){
        return;
    }
    while(tree->left != NULL){
        tree = tree->left;
    }
    return tree->value;
}
Şimdi ağaçtan veri silen fonksiyon yazalım. Fonksiyonda bir çok durumun kontrolünü yapacağız. Eğer sileceğimiz veri kökte ise ve ağacın sağ tarafı boş ise sol taraftaki maksimum değeri köke koyacağız. Eğer sağ tarafta veri var ise sağ taraftaki minimum veriyi köke koyacağız. Eğer sileceğimiz değer kökte değilse ve kökten büyükse ağacın sağ tarafı için delete_from_tree fonksiyonunu tekrar çağıracağız. Eğer büyük değilse küçük tarafı için için fonsiyonu tekrar çağıracağız.

struct node *delete_from_tree(struct node *tree, int value){
    if(tree == NULL){
        return;
    }

    if(tree->value == value){
        if(tree->left == NULL && tree->right == NULL){
            return;
        }
        if(tree->right != NULL){
            tree->value = find_min(tree->right);
            tree->right = delete_from_tree(tree->right, find_min(tree->right));
            return tree;
        }
        tree->value = find_max(tree->left);
        tree->left = delete_from_tree(tree->left, find_max(tree->left));
        return tree;
    }

    if(value > tree->value){
        tree->right = delete_from_tree(tree->right, value);
        return tree;
    }

    tree->left = delete_from_tree(tree->left, value);
    return tree;
}
Ağaçta veri aramak için bir fonksiyon yazalım:

struct node *search_in_tree(struct node *tree, int value){
    if(tree == NULL || tree->value == value){
        return tree;
    }
    if(value > tree->value){
        return search_in_tree(tree->right, value);
    }
    return search_in_tree(tree->left, value);
}
Ağaçtaki verileri konsola bastırmak için bir fonksiyon yazalım. Ağaçtaki verileri bastırmanın 3 yolu vardır: Inorder, preorder, postorder. Bu yollardan data structures bölümündeki binary tree konusunda daha ayrıntılı bahsedilecektir. Burada kullanılan yöntem ise inorder traverse'dür:

void traverse(struct node *tree){
    if(tree == NULL){
        return;
    }
    traverse(tree->left);
    printf("%d\n", tree->value);
    traverse(tree->right);
}
Son olarak fonksiyonları main fonksiyonunda kullanalım:

int main() {
    int i, searched_value;
    struct node *myTree = NULL;
    struct node *searched = NULL;

    myTree = insert_to_tree(myTree, 10);

    for(i=0; i<10; i++){
        insert_to_tree(myTree, rand() % 20);
    }
    traverse(myTree);

    searched_value = 9;
    searched = search_in_tree(myTree, searched_value);

    if(searched != NULL){
        printf("%d found!\n", searched->value);
    }
    else{
        printf("%d not found!\n", searched_value);
    }

    delete_from_tree(myTree, 9);
    searched_value = 9;
    searched = search_in_tree(myTree, searched_value);

    if(searched != NULL){
        printf("%d found!\n", searched->value);
    }
    else{
        printf("%d not found!\n", searched_value);
    }

    traverse(myTree);

    return 0;
}
Tüm kodlar:

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

struct node{
    int value;
    struct node *left;
    struct node *right;
};

struct node *insert_to_tree(struct node *tree, int value){
    if(tree == NULL){
        struct node *root = malloc(sizeof(struct node));
        root->left = NULL;
        root->right = NULL;
        root->value = value;
        return root;
    }

    if(value > tree->value){
        tree->right = insert_to_tree(tree->right, value);
        return tree;
    }

    tree->left = insert_to_tree(tree->left, value);
    return tree;
}

int find_max(struct node *tree){
   if(tree == NULL){
        return;
    }
    while(tree->right != NULL){
        tree = tree->right;
    }
    return tree->value;
}

int find_min(struct node *tree){
   if(tree == NULL){
        return;
    }
    while(tree->left != NULL){
        tree = tree->left;
    }
    return tree->value;
}

struct node *delete_from_tree(struct node *tree, int value){
    if(tree == NULL){
        return;
    }

    if(tree->value == value){
        if(tree->left == NULL && tree->right == NULL){
            return;
        }
        if(tree->right != NULL){
            tree->value = find_min(tree->right);
            tree->right = delete_from_tree(tree->right, find_min(tree->right));
            return tree;
        }
        tree->value = find_max(tree->left);
        tree->left = delete_from_tree(tree->left, find_max(tree->left));
        return tree;
    }

    if(value > tree->value){
        tree->right = delete_from_tree(tree->right, value);
        return tree;
    }

    tree->left = delete_from_tree(tree->left, value);
    return tree;
}

struct node *search_in_tree(struct node *tree, int value){
    if(tree == NULL || tree->value == value){
        return tree;
    }
    if(value > tree->value){
        return search_in_tree(tree->right, value);
    }
    return search_in_tree(tree->left, value);
}

void traverse(struct node *tree){
    if(tree == NULL){
        return;
    }
    traverse(tree->left);
    printf("%d\n", tree->value);
    traverse(tree->right);
}


int main() {
    int i, searched_value;
    struct node *myTree = NULL;
    struct node *searched = NULL;

    myTree = insert_to_tree(myTree, 10);

    for(i=0; i<10; i++){
        insert_to_tree(myTree, rand() % 20);
    }
    traverse(myTree);

    searched_value = 9;
    searched = search_in_tree(myTree, searched_value);

    if(searched != NULL){
        printf("%d found!\n", searched->value);
    }
    else{
        printf("%d not found!\n", searched_value);
    }

    delete_from_tree(myTree, 9);
    searched_value = 9;
    searched = search_in_tree(myTree, searched_value);

    if(searched != NULL){
        printf("%d found!\n", searched->value);
    }
    else{
        printf("%d not found!\n", searched_value);
    }

    traverse(myTree);

    return 0;
}
Output:

0
1
2
4
4
7
9
10
14
18
18
9 found!
9 not found!
0
1
2
4
4
7
10
14
18
18


Sonraki Yazı: Bank Customer Management Project
Yorumlar

Henüz bir yorum bulunmuyor.
Yorum bırakın