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. }

advertisement
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
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn