#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

#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;
}

//Quick sort alghoritması ortalama zamanda n(log n)
//de çalışan büyük arrayler için çok iyi sonuçlar
//veren bir sıralama algoritmasıdır.
public static void quicksort(int array[],int left,int right){
   	//Başta verilen left ve right değerlerini geçici olarak 
   	//tutabilmek için l ve r'ye atıyoruz. Aynı zamanda array'
   	//in içinde yer değiştirmeler içinde temp adlı değişkeni
   	//kullanıyoruz.
   	int l = left,r=right,temp;
   	//pivot olarak baştaki elemanı seçiyoruz
   	int pivot = array[left];
   	//partition algorithm
   	//Bu bölümde arrayimizi 2 ye ayırıyoruz
   	//Birinci bölümde pivottan küçük olanları,
   	//ikinci bölümde ise pivottan büyük elemanları
   	//tutuyoruz. 
   	while(r>=l){
   		//l değişkenini pivottan daha büyük bir eleman
   		//karşımıza çıkana kadar artırıyoruz.
   		while(pivot>array[l])
   			l++;
   		//r değişkenini pivottan daha küçük bir eleman
   		//karşımıza çıkana kadar azaltıyoruz.
   		while(pivot<array[r])
   			r--;
   		//Eğer sol tarafta pivottan daha büyük ve sağ
   		//tarafta pivottan daha küçük bir elemanla
   		//karşılaşırsak bunları temp değişkeni 
   		//yardımıyla yer değiştiriyoruz.
   		if(r>=l){
   			temp = array[r];
   			array[r] = array[l];
   			array[l] = temp;
   			//arrayin bir sonraki elamanına 
   			//ulaşabilmek için sol tarafta l'yi 
   			//artırırken  r'yi de azaltıyoruz.
   			l++;r--;
   		}
   		//En dıştaki loop sayesinde birinci grupta hep
   		//pivottan küçükleri ikinci grupta da pivottan
   		//hep büyükleri toplamış oluyoruz.
   	}
   	//Eğer l right kadar büyük olmuşsa veya right'tan 
   	//küçükse bu büyük grupta sıralanabilecek sayılar
   	//olabileceğini gösterir. Dolayısıyla 2. grup için
   	//quick sort tekrar çağrılır. 1. grup için se l değiş
   	//keninin solunda kalan kısım kullanılır. Onun için de
   	//aynı şekilde quick sort çağrılır.
   	if(right>=l){
   		quicksort(array,l,right);
   		quicksort(array,left,l-1);
   	}
}