Skip to content

Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H
#include <cstdlib>
#include <iostream>
using namespace std;
//bst yi binary search tree derken kullanicam
//Yeni bir bst olusturuyoruz
class BinarySearchTree{
public  :
        //Constructor ve diger methodlarin tanimlanmasi 
        BinarySearchTree();
        bool addItem(const int &item);
        bool deleteItem(const int &item);
        void preOrderTraversal();
        void postOrderTraversal();
        void inOrderTraversal();
        int numberOfLeaves();
        int getHeight();
private :
        //Node adinda yeni bir yapi(struct) olusturuyoruz
        struct Node{
            int item;
            Node *right;
            Node *left;
        };
        bool addNodeItem(const int &item,Node *&node);
        bool deleteNodeItem(const int &item,Node *&node);
        void exchange(Node *&dNode,Node *&fNode);
        void preOrder(Node *&node);
        void postOrder(Node *&node);
        void inOrder(Node *&node);
        int countLeaves(Node *&node);
        int getHeight(Node *&node);
        //bst nin ilk elemani
        Node *head;
};
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include "BinarySearchTree.h"
//Constructor 
BinarySearchTree::BinarySearchTree(){
   head = NULL;
}
//yeni bir eleman eklemek icin kullacagimiz method
bool BinarySearchTree::addItem(const int &item){
     return addNodeItem(item,head);
}
//bst tedeki bir elamani silmek icin kulacagimiz method
bool BinarySearchTree::deleteItem(const int &item){
     return deleteNodeItem(item,head);
}
//bst nin preOrder traversalini dönderir
void BinarySearchTree::preOrderTraversal(){
     preOrder(head);
}
//bst nin postOrder traversalini dönderir
void BinarySearchTree::postOrderTraversal(){
     postOrder(head);
}
//bst nin inOrder traversalini dönderir
void BinarySearchTree::inOrderTraversal(){
     inOrder(head);
}
//agactaki yaprak sayisini donderir
int BinarySearchTree::numberOfLeaves(){
     return countLeaves(head);
}
int BinarySearchTree::getHeight(){
     return getHeight(head);
}
bool BinarySearchTree::addNodeItem(const int &item,Node *&node){
     //Eger node nullsa yeni bir node olusturup bunu null olan
     //node ile degistiriyoruz
     if(node==NULL){
         Node *newNode = new Node();
         newNode->item = item;
         node = newNode;
         return true;
     }
     //eger gelen item node daki itemden küçükse bunu
     //agacin sol elemanina yolluyoruz büyüksede agacin 
     //sag elemanina gonderiyoruz
     else if(item<node->item)
         return addNodeItem(item,node->left);
     else
         return addNodeItem(item,node->right);
}
bool BinarySearchTree:: deleteNodeItem(const int &item,Node *&node){
     //Eger node Null sa bu demek oluyor ki agactaki uygun eleman
     //lari gezmis ama istedigimiz nodu bulamamisizdir
     if(node == NULL)
         return false;
     //eger gelen item node daki itemden küçükse bunu
     //agacin sol elemanina yolluyoruz büyüksede agacin 
     //sag elemanina gonderiyoruz
     else if(item < node->item)
         return deleteNodeItem(item,node->left);
     else if(item > node->item)
         return deleteNodeItem(item,node->right);
     //bu durum nodu buldugumuz durum yani itemlerin esit olmasi
     else{
         //eger sag ve sol yaprak bossa direk siliyoruz cunku
         //bizi zora sokabilecek yaprak yok
         if(node->right==NULL&&node->left==NULL){
              node = NULL;
              delete node;
         }
         //eger sag ve ya soldan birisi doluysa oradaki sag elaman
         //ile bizim nodumuza esitleyerek kurtulmus oluyoruz
         else if(node->left==NULL)
              node = node->right;
         else if(node->right==NULL)
              node = node->left;
         //eger her ikiside doluysa exchange methodu bizim node ile
         //nodun sagindaki node a gidiyoruz.Burda sebep bizim node dan
         //buyuk olan ilk eleman sagdaki ilk node olmasi
         else
              exchange(node,node->right);
         return true;
     }
}
void BinarySearchTree:: exchange(Node *&dNode,Node *&fNode){
     //burada bize verilen sag nodun null olup olmadigina bakiyoruz
     //eger null deilse sol node ala ala en son sol nodu bulana kadar
     //asagi iniyoruz. Bunun sebebi en solda bulacagimiz sol nodu
     //tree nin dengesini bozmayacaktir. Cunku en son buldugumuz sol node
     //dnode dan asagida bulunan diger butun nodelardan kucuk olmasidir
     //en sonunda sagdaki elemanla degistirme nedenimizse agacin sag 
     //tarafinin korunmasini saglamak istedigimizdir.
     if(fNode->left == NULL){
         dNode->item = fNode->item;
         fNode = fNode->right;
     }
     else
         exchange(dNode,fNode->left);         
}
void BinarySearchTree:: preOrder(Node *&node){
     //burada preOrderi cagiriyoruz bu ilk once
     //kendi nodumuzu sonra left ve right nodu cagirmak demektir
     //preorderla agacimizi yeni bastan olusturabiliriz.
     if(node != NULL){
         cout<<node->item<<endl;
         preOrder(node->left);
         preOrder(node->right);
     }
}
void BinarySearchTree:: postOrder(Node *&node){
     //burada postOrderi cagiriyoruz bu ilk once
     //left ve right nodu sonra kendi nodumuzu cagirmak demektir
     //preorderla agacimizi yeni bastan olusturabiliriz.
     if(node != NULL){
         postOrder(node->left);
         postOrder(node->right);
         cout<<node->item<<endl;
     }
}
void BinarySearchTree:: inOrder(Node *&node){
     //burada inOrderi cagiriyoruz bu ilk once left yapragi
     //daha sonra nodun kendisini en sondada nodun sag elemanini
     //cagirmak demektir 
     //inorderla agacimizin sirali bir sekilde bastirilmasini saglariz.
     if(node != NULL){
         inOrder(node->left);
         cout<<node->item<<endl;
         inOrder(node->right);
     }
}
int BinarySearchTree:: countLeaves(Node *&node){
    //eger nodu nullsa 0 donder sayilacak yaprak yok demektir
    //degilse sag ve sol elamanlarda kac tane yaprak olduguna bak
    //onlari toplayip sonucu donmesi.
    if(node==NULL)
        return 0;
    else
        return countLeaves(node->left)+countLeaves(node->right)+1;
}
int BinarySearchTree:: getHeight(Node *&node){
    //eger node null sa boyu sifira esit demektir dolayisiyla
    //0 donuyoruz
    int right,left;
    if(node==NULL)
        return 0;
    //eger null degilse nodu un boyu sol ve sag cocugundan hangisinin
    //boyu daha uzunsa onun bir fazlasina esittir.
    else if((left=getHeight(node->left)+1)>(right=getHeight(node->right)+1))
        return left;
    else
        return right;
}

3 Comments

  1. Good for people to know.

  2. mali mali

    yusuf sen naptın be yiğeni neler olmus sana özunden koptunmu noldu 🙂

  3. Awesome content you got here! You can earn some
    extra money from your website, don’t miss this opportunity, for more info just search in google –
    omgerido monetize website

Leave a Reply

Your email address will not be published. Required fields are marked *