C++ Program to Implement Fusion Tree

This C++ program implements the fusion tree. A fusion tree is a type of tree data structure that implements an associative array on w-bit integers.

Here is the source code of the C++ program to display the constructed tree and thus generated associated array of 5 bit integers on giving binary digits as input. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

  1. /*
  2.  * C++ Program to Implement Fusion Tree
  3.  */
  4. #include<stdio.h>
  5. #include<conio.h>
  6. #include<iostream>
  7. using namespace std;
  8. int k = 0;
  9. struct FusionTreeNode
  10. {
  11.     int *data;
  12.     FusionTreeNode **child_ptr;
  13.     bool leaf;
  14.     int n;
  15. }*root = NULL, *np = NULL, *x = NULL;
  16. FusionTreeNode * init()
  17. {
  18.     int i;
  19.     np = new FusionTreeNode;
  20.     np->data = new int[5];
  21.     np->child_ptr = new FusionTreeNode *[6];
  22.     np->leaf = true;
  23.     np->n = 0;
  24.     for (i = 0; i < 6; i++)
  25.     {
  26.         np->child_ptr[i] = NULL;
  27.     }
  28.     return np;
  29. }
  30. void traverse(FusionTreeNode *p)
  31. {
  32.     cout<<endl;
  33.     int i;
  34.     for (i = 0; i < p->n; i++)
  35.     {
  36.         if (p->leaf == false)
  37.         {
  38.             traverse(p->child_ptr[i]);
  39.         }
  40.         cout << " " << p->data[i];
  41.     } 
  42.     if (p->leaf == false)
  43.     {
  44.         traverse(p->child_ptr[i]);
  45.     }
  46.     cout<<endl;
  47. }
  48. void sort(int *p, int n)
  49. {
  50.     int i, j, temp;
  51.     for (i = 0; i < n; i++)
  52.     {
  53.         for (j = i; j <= n; j++)
  54.         {
  55.             if (p[i] > p[j])
  56.             {
  57.                 temp = p[i];
  58.                 p[i] = p[j];
  59.                 p[j] = temp;
  60.             }
  61.         }
  62.     }
  63. }
  64. int split_child(FusionTreeNode *x, int i)
  65. {
  66.     int j, mid;
  67.     FusionTreeNode *np1, *np3, *y;
  68.     np3 = init();
  69.     np3->leaf = true;
  70.     if (i == -1)
  71.     {
  72.         mid = x->data[2];
  73.         x->data[2] = 0;
  74.         x->n--;
  75.         np1 = init();
  76.         np1->leaf = false;
  77.         x->leaf = true;
  78.         for (j = 3; j < 5; j++)
  79.         {
  80.             np3->data[j - 3] = x->data[j];
  81.             np3->child_ptr[j - 3] = x->child_ptr[j];
  82.             np3->n++;
  83.             x->data[j] = 0;
  84.             x->n--;
  85.         }
  86.         for(j=0;j<6;j++)
  87.         {
  88.             x->child_ptr[j] = NULL;
  89.         }
  90.         np1->data[0] = mid;
  91.         np1->child_ptr[np1->n] = x;
  92.         np1->child_ptr[np1->n + 1] = np3;
  93.         np1->n++;
  94.         root = np1;
  95.     }
  96.     else
  97.     {
  98.         y = x->child_ptr[i];
  99.         mid = y->data[2];
  100.         y->data[2] = 0;
  101.         y->n--;
  102.         for (j = 3; j < 5; j++)
  103.         {
  104.             np3->data[j - 3] = y->data[j];
  105.             np3->n++;
  106.             y->data[j] = 0;
  107.             y->n--;
  108.         }
  109.         x->child_ptr[i + 1] = y;
  110.         x->child_ptr[i + 1] = np3; 
  111.     }
  112.     return mid;
  113. }
  114. void insert(int a)
  115. {
  116.     int i, temp;
  117.     x = root;
  118.     if (x == NULL)
  119.     {
  120.         root = init();
  121.         x = root;
  122.     }
  123.     else
  124.     {
  125.         if (x->leaf == true && x->n == 5)
  126.         {
  127.             temp = split_child(x, -1);
  128.             x = root;
  129.             for (i = 0; i < (x->n); i++)
  130.             {
  131.                 if ((a > x->data[i]) && (a < x->data[i + 1]))
  132.                 {
  133.                     i++;
  134.                     break;
  135.                 }
  136.                 else if (a < x->data[0])
  137.                 {
  138.                     break;
  139.                 }
  140.                 else
  141.                 {
  142.                     continue;
  143.                 }
  144.             }
  145.             x = x->child_ptr[i];
  146.         }
  147.         else
  148.         {
  149.             while (x->leaf == false)
  150.             {
  151.             for (i = 0; i < (x->n); i++)
  152.             {
  153.                 if ((a > x->data[i]) && (a < x->data[i + 1]))
  154.                 {
  155.                     i++;
  156.                     break;
  157.                 }
  158.                 else if (a < x->data[0])
  159.                 {
  160.                     break;
  161.                 }
  162.                 else
  163.                 {
  164.                     continue;
  165.                 }
  166.             }
  167.                 if ((x->child_ptr[i])->n == 5)
  168.                 {
  169.                     temp = split_child(x, i);
  170.                     x->data[x->n] = temp;
  171.                     x->n++;
  172.                     continue;
  173.                 }
  174.                 else
  175.                 {
  176.                     x = x->child_ptr[i];
  177.                 }
  178.             }
  179.         }
  180.     }
  181.     x->data[x->n] = a;
  182.     sort(x->data, x->n);
  183.     x->n++;
  184. }
  185. int main()
  186. {
  187.     int i, n, t;
  188.     cout<<"enter the no of elements to be inserted\n";
  189.     cin>>n;
  190.     for(i = 0; i < n; i++)
  191.     {
  192.           cout<<"enter the binary element\n";
  193.           cin>>t;
  194.           insert(t);
  195.     }
  196.     cout<<"traversal of constructed fusion tree\n";
  197.     traverse(root);
  198.     getch();
  199. }

Output
enter the no of elements to be inserted
13
enter the binary element
0
enter the binary element
0
enter the binary element
1
enter the binary element
1
enter the binary element
0
enter the binary element
0
enter the binary element
0
enter the binary element
0
enter the binary element
1
enter the binary element
1
enter the binary element
0
enter the binary element
1
enter the binary element
1
traversal of constructed fusion tree
 
 
 0 0
 0
 0 0
 0
 0 1
 1
 1 1 1 1

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.