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

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

অ্যালগরিদম

প্রয়োজনীয় ফাংশন এবং ইনপুট -

Begin
   Take the no of elements of the tree and take the elements.
   Create a structure FusionTree to declare variables.
   Create a function init() for creating the nodes.
   Create a function traverse() to traverse the tree.
   Create a function sort() to sort the nodes of the tree.
   Create a function split_child() to split the nodes.
   Create a function insert() to insert the nodes into the tree.
   Create a function main(), to call insert() to create the fusion tree and then call the function traverse to display the result.
End

উদাহরণ কোড

#include<iostream>
using namespace std;

struct FusionTree//declaration of nodes {
   int *d;
   FusionTree **child_ptr;
   bool l;
   int n;
}*r = NULL, *np = NULL, *x = NULL;

FusionTree* init()//cretae new node {
   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)//traverse the tree {
   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)//sort the tree {
   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)//split the child {
   int j, mid;
   FusionTree *np1, *np3, *y;
   np3 = init();// initialize new node
   np3->l = true;
   if (i == -1) {
      mid = x->d[2];//calculate mid
      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