सी ++ प्रोग्राम फ्यूजन ट्री को लागू करने के लिए

फ़्यूज़न ट्री एक ट्री डेटा संरचना है जो w-बिट पूर्णांकों पर एक सहयोगी सरणी को लागू करता है। यह फ़्यूज़न ट्री को लागू करने के लिए एक 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