Binary Search Tree

Binary Search Tree (BST), bilgisayar biliminde arama, ekleme ve silme işlemlerini ortalama O(log n) zamanla gerçekleştirebildiği için temel veri yapılarından biridir. BST’nin gücü, her düğümün solunda kendisinden küçük, sağında ise büyük değerlerin bulunması prensibinden gelir. Böylece ağaç dengeli kaldığı sürece işlemler dizilere kıyasla çok daha verimli yapılabilir. Bu örnekte, düğüm ekleme, silme, üç farklı dolaşım yöntemi (preorder, inorder, postorder), yaprak sayısı ve yüksekliği hesaplama gibi BST’nin temel operasyonlarını içeren sade ama işlevsel bir C++ uygulaması bulunmaktadır. Kod, klasik recursive yaklaşımı takip eder ve her işlem, ilgili yardımcı fonksiyonlarla temiz bir mantıkla ayrılmıştır.

Bu BinarySearchTree.h

#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

// bst'yi (binary search tree) temsil eden sinifimiz.
class BinarySearchTree {
public:
    BinarySearchTree();  // Yapici metot
    ~BinarySearchTree(); // Yikici metot
    bool addItem(const int &item);  // Yeni eleman ekleme
    bool deleteItem(const int &item);  // Eleman silme
    void preOrderTraversal();  // Preorder dolasim
    void postOrderTraversal();  // Postorder dolasim
    void inOrderTraversal();  // Inorder dolasim
    int numberOfLeaves();  // Yaprak sayisini dondurur
    int getHeight();  // Agacin yuksekligini dondurur

private:
    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);

    Node *head;  // bst'nin ilk elemani
};

#endif

Bu da BinarySearchTree.cpp

#include "BinarySearchTree.h"
#include <iostream>

// Constructor
BinarySearchTree::BinarySearchTree() {
    head = NULL;  // Baslangicta head'i NULL olarak ayarliyoruz
}

// Yeni bir eleman eklemek icin kullanilan metot
bool BinarySearchTree::addItem(const int &item) {
    return addNodeItem(item, head);
}

// bst'deki bir elemani silmek icin kullanilan metot
bool BinarySearchTree::deleteItem(const int &item) {
    return deleteNodeItem(item, head);
}

// bst'nin preOrder gezintisini gerceklestirir
void BinarySearchTree::preOrderTraversal() {
    preOrder(head);
}

// bst'nin postOrder gezintisini gerceklestirir
void BinarySearchTree::postOrderTraversal() {
    postOrder(head);
}

// bst'nin inOrder gezintisini gerceklestirir
void BinarySearchTree::inOrderTraversal() {
    inOrder(head);
}

// Agactaki yaprak sayisini dondurur
int BinarySearchTree::numberOfLeaves() {
    return countLeaves(head);
}

// Agacin yuksekligini hesaplar ve dondurur
int BinarySearchTree::getHeight() {
    return getHeight(head);
}

// Destructure
BinarySearchTree::~BinarySearchTree() {
    // Agaci temizleme islemi burada yapilabilir
}

// Yeni eleman ekleyen yardimci metot
bool BinarySearchTree::addNodeItem(const int &item, Node *&node) {
    if(node == NULL) {
        node = new Node();
        node->item = item;
        node->left = node->right = NULL;
        return true;
    }
    else if(item < node->item)
        return addNodeItem(item, node->left);
    else if(item > node->item)
        return addNodeItem(item, node->right);
    else
        return false;  // Dublicate elemanlar eklenmiyor
}

// Eleman silen yardimci metot
bool BinarySearchTree::deleteNodeItem(const int &item, Node *&node) {
    if(node == NULL)
        return false;  // Eleman bulunamadi
    if(item < node->item)
        return deleteNodeItem(item, node->left);
    else if(item > node->item)
        return deleteNodeItem(item, node->right);
    else {
        if(node->left == NULL && node->right == NULL) {
            delete node;
            node = NULL;
        }
        else if(node->left == NULL) {
            Node *temp = node;
            node = node->right;
            delete temp;
        }
        else if(node->right == NULL) {
            Node *temp = node;
            node = node->left;
            delete temp;
        }
        else
            exchange(node, node->right);
        return true;
    }
}

// Node degistirme yardimci metot
void BinarySearchTree::exchange(Node *&dNode, Node *&fNode) {
    if(fNode->left == NULL) {
        dNode->item = fNode->item;
        Node *temp = fNode;
        fNode = fNode->right;
        delete temp;
    }
    else
        exchange(dNode, fNode->left);
}

// Preorder dolasim
void BinarySearchTree::preOrder(Node *&node) {
    if(node != NULL) {
        std::cout << node->item << std::endl;
        preOrder(node->left);
        preOrder(node->right);
    }
}

// Postorder dolasim
void BinarySearchTree::postOrder(Node *&node) {
    if(node != NULL) {
        postOrder(node->left);
        postOrder(node->right);
        std::cout << node->item << std::endl;
    }
}

// Inorder dolasim
void BinarySearchTree::inOrder(Node *&node) {
    if(node != NULL) {
        inOrder(node->left);
        std::cout << node->item << std::endl;
        inOrder(node->right);
    }
}

// Yaprak sayisini sayan metot
int BinarySearchTree::countLeaves(Node *&node) {
    if(node == NULL)
        return 0;
    else if(node->left == NULL && node->right == NULL)
        return 1;
    else
        return countLeaves(node->left) + countLeaves(node->right);
}

// Agacin yuksekligini hesaplayan metot
int BinarySearchTree::getHeight(Node *&node) {
    if(node == NULL)
        return 0;
    else {
        int leftHeight = getHeight(node->left);
        int rightHeight = getHeight(node->right);
        return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
    }
}