C++ প্রোগ্রাম: র‍্যান্ডমাইজড বাইনারি সার্চ ট্রি বাস্তবায়ন

বাইনারি সার্চ ট্রি (BST) হল একটি সাজানো বাইনারি ট্রি যেখানে সব নোড নিম্নলিখিত বৈশিষ্ট্যগুলো রক্ষা করে:

• একটি নোডের ডান সাব-ট্রির কী তার পেরেন্ট নোডের কী থেকে বড়।
• একটি নোডের বাম সাব-ট্রির কী তার পেরেন্ট নোডের কী থেকে ছোট বা সমান।
• প্রতিটি নোডের সর্বোচ্চ দুটি চাইল্ড থাকতে পারে।

নিচে র‍্যান্ডমাইজড বাইনারি সার্চ ট্রি বাস্তবায়নের জন্য একটি C++ প্রোগ্রাম দেওয়া হলো।

শুরু 
  ক্লাস BST ঘোষণা করে নিম্নলিখিত ফাংশনগুলো:
    search() = BST-এ একটি আইটেম অনুসন্ধান করতে।
    temp = root দিয়ে শুরু করুন।
    যতক্ষণ (temp != NULL)
      গভীরতা বাড়ান
      যদি (temp->info == data)
        ডেটা এবং গভীরতা প্রিন্ট করুন
      অন্যথায় যদি (temp->info > data)
        temp = temp->l
      অন্যথায়
        temp = temp->r
    insert() = ট্রিতে আইটেম যোগ করতে:
      যদি ট্রি খালি হয়, ডেটাকে রুট হিসেবে যোগ করুন।
      যদি ট্রি খালি না হয়
        ডেটা < রুট হলে বাম চাইল্ড হিসেবে যোগ করুন।
        অন্যথায় ডান চাইল্ড হিসেবে যোগ করুন।
    del() = ট্রি থেকে একটি আইটেম মুছে ফেলতে।
      casea() = del()-এর থেকে কল করা হয় যদি l = r = null।
      caseb() = del()-এর থেকে কল করা হয় যদি l != null, r = null।
      caseb() = del()-এর থেকে কল করা হয় যদি l = null, r != null।
      casec() = del()-এর থেকে কল করা হয় যদি l != null, r != null।
      inorder() = নোডগুলো ইনঅর্ডার ট্রভার্স করতে: বাম – রুট – ডান।
      preorder() = নোডগুলো প্রिअর্ডার ট্রভার্স করতে: রুট – বাম – ডান।
      postorder() = নোডগুলো পোস্টঅর্ডার ট্রভার্স করতে: বাম – ডান – রুট
শেষ

# include 
# include 
using namespace std;

struct nod { // নোড ঘোষণা
    int info;
    struct nod *l;
    struct nod *r;
} *r;

class BST {
public:
    // ফাংশনগুলোর ঘোষণা
    void search(nod *, int);
    void find(int, nod **, nod **);
    void insert(nod *, nod *);
    void del(int);
    void casea(nod *, nod *);
    void caseb(nod *, nod *);
    void casec(nod *, nod *);
    void preorder(nod *);
    void inorder(nod *);
    void postorder(nod *);
    void show(nod *, int);
    BST() { r = NULL; }
};

void BST::find(int i, nod **par, nod **loc) { // এলিমেন্টের পজিশন খুঁজে বের করা
    nod *ptr, *ptrsave;
    if (r == NULL) {
        *loc = NULL;
        *par = NULL;
        return;
    }
    if (i == r->info) {
        *loc = r;
        *par = NULL;
        return;
    }
    if (i < r->info) ptr = r->l;
    else ptr = r->r;
    ptrsave = r;
    while (ptr != NULL) {
        if (i == ptr->info) {
            *loc = ptr;
            *par = ptrsave;
            return;
        }
        ptrsave = ptr;
        if (i < ptr->info) ptr = ptr->l;
        else ptr = ptr->r;
    }
    *loc = NULL;
    *par = ptrsave;
}

void BST::search(nod *root, int data) {
    int depth = 0;
    nod *temp = new nod;
    temp = root;
    while (temp != NULL) {
        depth++;
        if (temp->info == data) {
            cout << "\nData found at depth: " << depth << endl;
            return;
        } else if (temp->info > data)
            temp = temp->l;
        else
            temp = temp->r;
    }
    cout << "\n Data not found" << endl;
    return;
}

void BST::insert(nod *tree, nod *newnode) {
    if (r == NULL) {
        r = new nod;
        r->info = newnode->info;
        r->l = NULL;
        r->r = NULL;
        cout << "Root Node is Added" << endl;
        return;
    }
    if (tree->info == newnode->info) {
        cout << "Element already in the tree" << endl;
        return;
    }
    if (tree->info > newnode->info) {
        if (tree->l != NULL) insert(tree->l, newnode);
        else {
            tree->l = newnode;
            (tree->l)->l = NULL;
            (tree->l)->r = NULL;
            cout << "Node Added to Left" << endl;
            return;
        }
    } else {
        if (tree->r != NULL) insert(tree->r, newnode);
        else {
            tree->r = newnode;
            (tree->r)->l = NULL;
            (tree->r)->r = NULL;
            cout << "Node Added to Right" << endl;
            return;
        }
    }
}

void BST::del(int i) {
    nod *par, *loc;
    if (r == NULL) {
        cout << "Tree empty" << endl;
        return;
    }
    find(i, &par, &loc);
    if (loc == NULL) {
        cout << "Item not present in tree" << endl;
        return;
    }
    if (loc->l == NULL && loc->r == NULL) { casea(par, loc); cout << "item deleted" << endl; }
    if (loc->l != NULL && loc->r == NULL) { caseb(par, loc); cout << "item deleted" << endl; }
    if (loc->l == NULL && loc->r != NULL) { caseb(par, loc); cout << "item deleted" << endl; }
    if (loc->l != NULL && loc->r != NULL) { casec(par, loc); cout << "item deleted" << endl; }
    free(loc);
}

void BST::casea(nod *par, nod *loc) {
    if (par == NULL) r = NULL;
    else { if (loc == par->l) par->l = NULL; else par->r = NULL; }
}

void BST::caseb(nod *par, nod *loc) {
    nod *child;
    if (loc->l != NULL) child = loc->l;
    else child = loc->r;
    if (par == NULL) r = child;
    else { if (loc == par->l) par->l = child; else par->r = child; }
}

void BST::casec(nod *par, nod *loc) {
    nod *ptr, *ptrsave, *suc, *parsuc;
    ptrsave = loc;
    ptr = loc->r;
    while (ptr->l != NULL) { ptrsave = ptr; ptr = ptr->l; }
    suc = ptr; parsuc = ptrsave;
    if (suc->l == NULL && suc->r == NULL) casea(parsuc, suc);
    else caseb(parsuc, suc);
    if (par == NULL) r = suc;
    else { if (loc == par->l) par->l = suc; else par->r = suc; }
    suc->l = loc->l; suc->r = loc->r;
}

void BST::preorder(nod *ptr) {
    if (r == NULL) { cout << "Tree is empty" << endl; return; }
    if (ptr != NULL) { cout << ptr->info << " "; preorder(ptr->l); preorder(ptr->r); }
}

void BST::inorder(nod *ptr) {
    if (r == NULL) { cout << "Tree is empty" << endl; return; }
    if (ptr != NULL) { inorder(ptr->l); cout << ptr->info << " "; inorder(ptr->r); }
}

void BST::postorder(nod *ptr) {
    if (r == NULL) { cout << "Tree is empty" << endl; return; }
    if (ptr != NULL) { postorder(ptr->l); postorder(ptr->r); cout << ptr->info << " "; }
}

void BST::show(nod *ptr, int level) {
    int i;
    if (ptr != NULL) {
        show(ptr->r, level + 1);
        cout << endl;
        if (ptr == r) cout << "Root->: ";
        else { for (i = 0; i < level; i++) cout << " "; }
        cout << ptr->info;
        show(ptr->l, level + 1);
    }
}

int main() {
    int c, n, item;
    BST bst;
    nod *t;
    while (1) {
        cout << "1.Insert Element " << endl;
        cout << "2.Delete Element " << endl;
        cout << "3.Search Element" << endl;
        cout << "4.Inorder Traversal" << endl;
        cout << "5.Preorder Traversal" << endl;
        cout << "6.Postorder Traversal" << endl;
        cout << "7.Display the tree" << endl;
        cout << "8.Quit" << endl;
        cout << "Enter your choice : "; cin >> c;
        switch (c) {
            case 1:
                t = new nod;
                cout << "Enter the number to be inserted : "; cin >> t->info;
                bst.insert(r, t);
                break;
            case 2:
                if (r == NULL) { cout << "Tree is empty, nothing to delete" << endl; continue; }
                cout << "Enter the number to be deleted : "; cin >> n;
                bst.del(n);
                break;
            case 3:
                cout << "Search:" << endl; cin >> item;
                bst.search(r, item);
                break;
            case 4:
                cout << "Inorder Traversal of BST:" << endl; bst.inorder(r); cout << endl;
                break;
            case 5:
                cout << "Preorder Traversal of BST:" << endl; bst.preorder(r); cout << endl;
                break;
            case 6:
                cout << "Postorder Traversal of BST:" << endl; bst.postorder(r); cout << endl;
                break;
            case 7:
                cout << "Display BST:" << endl; bst.show(r, 1); cout << endl;
                break;
            case 8: exit(1);
            default: cout << "Wrong choice" << endl;
        }
    }
}

1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit
Enter your choice : 1
Enter the number to be inserted : 6
Root Node is Added
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit
Enter your choice : 1
Enter the number to be inserted : 7
Node Added to Right
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit
Enter your choice : 1
Enter the number to be inserted : 5
Node Added to Left
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit
Enter your choice : 1
Enter the number to be inserted : 4
Node Added to Left
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit
Enter your choice : 3
Search: 7
Data found at depth: 2
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit
Enter your choice : 3
Search: 1
Data not found
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit
Enter your choice : 4
Inorder Traversal of BST: 4 5 6 7
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit
Enter your choice : 5
Preorder Traversal of BST: 6 5 4 7
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit
Enter your choice : 6
Postorder Traversal of BST: 4 5 7 6
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit
Enter your choice : 7
Display BST:
        7
Root->: 6
        5
        4
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit
Enter your choice : 2
Enter the number to be deleted : 1
Item not present in tree
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit
Enter your choice : 5
Preorder Traversal of BST: 6 5 4 7
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit
Enter your choice : 2
Enter the number to be deleted : 5
item deleted
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit
Enter your choice : 7
Display BST:
        7
Root->: 6
        4
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit
Enter your choice : 8