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

ফিউশন ট্রি হল একটি ট্রি ডেটা স্ট্রাকচার যা w-বিট পূর্ণসংখ্যার ওপর একটি অ্যাসোসিয়েটিভ অ্যারে বাস্তবায়ন করে। এটি একটি C++ প্রোগ্রাম যা একটি বাইনারি ট্রি ইনপুট হিসেবে নিয়ে 6-বিট পূর্ণসংখ্যার একটি অ্যারে জেনারেট করে।

শুরু
  ট্রির এলিমেন্ট সংখ্যা এবং এলিমেন্টগুলো ইনপুট নিন।
  FusionTree স্ট্রাকচার তৈরি করে ভেরিয়েবল ঘোষণা করুন।
  init() ফাংশন তৈরি করুন নোড তৈরির জন্য।
  traverse() ফাংশন তৈরি করুন ট্রি ট্রভার্সালের জন্য।
  sort() ফাংশন তৈরি করুন ট্রির নোড সর্ট করার জন্য।
  split_child() ফাংশন তৈরি করুন নোড বিভাজনের জন্য।
  insert() ফাংশন তৈরি করুন ট্রিতে নোড ইনসার্ট করার জন্য।
  main() ফাংশনে insert() কল করে ফিউশন ট্রি তৈরি করুন এবং traverse() কল করে ফলাফল দেখান।
শেষ

#include 
using namespace std;

struct FusionTree { // নোড ঘোষণা
    int *d;
    FusionTree **child_ptr;
    bool l;
    int n;
} *r = NULL, *np = NULL, *x = NULL;

FusionTree* init() { // নতুন নোড তৈরি
    int i;
    np = new FusionTree;
    np->d = new int[6];
    np->child_ptr = new FusionTree*[7];
    np->l = true;
    np->n = 0;
    for (i = 0; i < 7; i++) np->child_ptr[i] = NULL;
    return np;
}

void traverse(FusionTree *p) { // ট্রি ট্রভার্সাল
    cout << endl;
    int i;
    for (i = 0; i < p->n; i++) {
        if (p->l == false) traverse(p->child_ptr[i]);
        cout << " " << p->d[i];
    }
    if (p->l == false) traverse(p->child_ptr[i]);
    cout << endl;
}

void sort(int *p, int n) { // ট্রি সর্ট
    int i, j, t;
    for (i = 0; i < n; i++) {
        for (j = i; j <= n; j++) {
            if (p[i] > p[j]) {
                t = p[i]; p[i] = p[j]; p[j] = t;
            }
        }
    }
}

int split_child(FusionTree *x, int i) { // চাইল্ড বিভাজন
    int j, mid;
    FusionTree *np1, *np3, *y;
    np3 = init(); np3->l = true;
    if (i == -1) {
        mid = x->d[2]; x->d[2] = 0; x->n--;
        np1 = init(); np1->l = false; x->l = true;
        for (j = 3; j < 6; j++) {
            np3->d[j-3] = x->d[j];
            np3->child_ptr[j-3] = x->child_ptr[j];
            np3->n++; x->d[j] = 0; x->n--;
        }
        for (j = 0; j < 6; j++) x->child_ptr[j] = NULL;
        np1->d[0] = mid;
        np1->child_ptr[np1->n] = x;
        np1->child_ptr[np1->n+1] = np3;
        np1->n++; r = np1;
    } else {
        y = x->child_ptr[i];
        mid = y->d[2]; y->d[2] = 0; y->n--;
        for (j = 3; j < 6; j++) {
            np3->d[j-3] = y->d[j];
            np3->n++; y->d[j] = 0; y->n--;
        }
        x->child_ptr[i+1] = y;
        x->child_ptr[i+1] = np3;
    }
    return mid;
}

void insert(int a) {
    int i, t; x = r;
    if (x == NULL) { r = init(); x = r; }
    else {
        if (x->l == true && x->n == 6) {
            t = split_child(x, -1); x = r;
            for (i = 0; i < (x->n); i++) {
                if ((a > x->d[i]) && (a < x->d[i+1])) { i++; break; }
                else if (a < x->d[0]) break;
                else continue;
            }
            x = x->child_ptr[i];
        } else {
            while (x->l == false) {
                for (i = 0; i < (x->n); i++) {
                    if ((a > x->d[i]) && (a < x->d[i+1])) { i++; break; }
                    else if (a < x->d[0]) break;
                    else continue;
                }
                if ((x->child_ptr[i])->n == 6) {
                    t = split_child(x, i);
                    x->d[x->n] = t; x->n++; continue;
                } else x = x->child_ptr[i];
            }
        }
    }
    x->d[x->n] = a; sort(x->d, x->n); x->n++;
}

int main() {
    int i, n, t;
    cout << "enter the no of elements to be inserted\n"; cin >> n;
    for (i = 0; i < n; i++) {
        cout << "enter the element\n"; cin >> t; insert(t);
    }
    cout << "traversal of constructed fusion tree\n"; traverse(r);
}

enter the no of elements to be inserted 7
enter the element 10
enter the element 20
enter the element 30
enter the element 40
enter the element 50
enter the element 60
enter the element 70
traversal of constructed fusion tree
10 20 30 40 50 60 70