C++ প্রোগ্রাম: কার্টেশিয়ান ট্রি বাস্তবায়ন

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

শুরু
  CarTree ক্লাসে ফাংশনগুলো ঘোষণা:
    min() = অ্যারেতে ন্যূনতম এলিমেন্টের ইন্ডেক্স খুঁজে বের করতে:
      if (arr[i] < min) min = arr[i]; minind = i
    inorder() = ট্রির ইনঅর্ডার ট্রভার্সালের জন্য:
      যদি ট্রি খালি হয়, রিটার্ন করুন
      inorder(node->l)
      রুট প্রিন্ট করুন as node->d
      inorder(node->r)
শেষ

#include 
#include 
#include 
using namespace std;

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

class CarTree {
public: // ফাংশন ঘোষণা
    nod *newNode(int);
    int min(int[], int, int);
    nod *buildTree(int[], int, int);
    void inorder(nod* node);
    void show(nod*, int);
    CarTree() {}
};

int CarTree::min(int arr[], int s, int e) {
    int i, min = arr[s], minind = s;
    for (i = s + 1; i <= e; i++) {
        if (arr[i] < min) { min = arr[i]; minind = i; }
    }
    return minind;
}

nod* CarTree::buildTree(int inorder[], int s, int e) { // কার্টেশিয়ান ট্রি বিল্ড
    if (s > e) return NULL;
    int i = min(inorder, s, e);
    nod *r = newNode(inorder[i]);
    if (s == e) return r;
    r->l = buildTree(inorder, s, i - 1); // বাম চাইল্ডের জন্য রিকার্সিভ কল
    r->r = buildTree(inorder, i + 1, e); // ডান চাইল্ডের জন্য রিকার্সিভ কল
    return r;
}

void CarTree::inorder(struct nod* node) {
    if (node == NULL) return;
    inorder(node->l);
    cout << node->d << " ";
    inorder(node->r);
}

void CarTree::show(nod* ptr, int level) { // ট্রি দেখানো
    int i;
    if (ptr == NULL) return;
    if (ptr != NULL) {
        show(ptr->r, level + 1);
        cout << endl;
        for (i = 0; i < level; i++) cout << " ";
        cout << ptr->d;
        show(ptr->l, level + 1);
    }
}

nod* CarTree::newNode(int d) { // নতুন নোড তৈরি
    nod* t = new nod; t->d = d; t->l = NULL; t->r = NULL; return t;
}

int main() {
    CarTree ct; int i, n;
    cout << "Enter number of elements to be inserted: "; cin >> n;
    int a[n];
    for (i = 0; i < n; i++) { cout << "Enter Element " << i + 1 << " : "; cin >> a[i]; }
    nod *r = ct.buildTree(a, 0, n - 1);
    cout << "Cartesian tree Structure: " << endl; ct.show(r, 1); cout << endl;
    cout << "\n Inorder traversal of the tree \n" << endl; ct.inorder(r); cout << endl;
    return 0;
}

Enter number of elements to be inserted: 10
Enter Element 1 : 10
Enter Element 2 : 30
Enter Element 3 : 20
Enter Element 4 : 40
Enter Element 5 : 50
Enter Element 6 : 70
Enter Element 7 : 60
Enter Element 8 : 80
Enter Element 9 : 100
Enter Element 10 : 112
Cartesian tree Structure:
                                        112
                                    100
                                80
                            60
                        70
                    50
                40
            20
        30
    10
Inorder traversal of the tree
10 30 20 40 50 70 60 80 100 112