C++ প্রোগ্রাম: বাইনারি ট্রির ডাবল অর্ডার ট্রভার্সাল বাস্তবায়ন

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

ডাবল অর্ডার ট্রভার্সালে, সাবট্রির রুট দুবার ট্রভার্স করা হবে।

শুরু
  BST ক্লাসে নিম্নলিখিত ফাংশন থাকে:
    insert() = ট্রিতে আইটেম ইনসার্ট করতে:
      রুট লিখুন।
      নোডের মান লিখুন, যদি রুটের চেয়ে বড় হয় তবে ডান পাশে অন্যথায় বাম পাশে।
    doubleOrder() = ইনঅর্ডার করতে:
      যদি রুট = null হয়, "Tree is empty" প্রিন্ট করুন।
      অন্যথায় নিম্নলিখিত ক্রমে অপারেশন করুন:
        (সাব)ট্রির রুট ভিজিট করুন।
        বাম সাব-ট্রি ভিজিট করুন।
        (সাব)ট্রির রুট পুনরায় ভিজিট করুন।
        ডান সাব-ট্রি ভিজিট করুন।
শেষ

#include 
#include 
using namespace std;

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

class BST {
public: // ফাংশন ঘোষণা
    void insert(nod *, nod *);
    void doubleOrder(nod *);
    void show(nod *, int);
    BST() { r = NULL; }
};

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::doubleOrder(nod *ptr) {
    if (r == NULL) { cout << "Tree is empty" << endl; return; }
    if (ptr != NULL) {
        cout << ptr->info << " ";
        doubleOrder(ptr->l);
        cout << ptr->info << " ";
        doubleOrder(ptr->r);
    }
}

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; BST bst; nod *t;
    while (1) {
        cout << "1.Insert Element " << endl;
        cout << "2.Double-Order Traversal" << endl;
        cout << "3.Show" << endl;
        cout << "4.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: cout << "Double-Order Traversal of BST:" << endl; bst.doubleOrder(r); cout << endl; break;
            case 3: cout << "Print BST:" << endl; bst.show(r, 1); cout << endl; break;
            case 4: exit(1);
            default: cout << "Wrong choice" << endl;
        }
    }
}

1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit
Enter your choice : 1
Enter the number to be inserted : 7
Root Node is Added
1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit
Enter your choice : 1
Enter the number to be inserted : 6
Node Added To Left
1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit
Enter your choice : 1
Enter the number to be inserted : 4
Node Added To Left
1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit
Enter your choice : 1
Enter the number to be inserted : 2
Node Added To Left
1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit
Enter your choice : 1
Enter the number to be inserted : 10
Node Added To Right
1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit
Enter your choice : 3
Print BST:
        10
Root->: 7
        6
        4
        2
1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit
Enter your choice : 2
Double-Order Traversal of BST:
7 6 4 2 2 4 6 7 10 10
1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit
Enter your choice : 4