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.

```
/*
```

 * C++ Program to Implement Fusion Tree

```
 */
```
```
#include<stdio.h>
```
```
#include<conio.h>
```
```
#include<iostream>
```
```
using namespace std;
```
```
int k = 0;
```
```
struct FusionTreeNode
```
```
{
```
```
    int *data;
```
```
    FusionTreeNode **child_ptr;
```
```
    bool leaf;
```
```
    int n;
```
```
}*root = NULL, *np = NULL, *x = NULL;
```
```
FusionTreeNode * init()
```
```
{
```
```
    int i;
```
```
    np = new FusionTreeNode;
```
```
    np->data = new int[5];
```

    np->child_ptr = new FusionTreeNode *[6];

```
    np->leaf = true;
```
```
    np->n = 0;
```
```
    for (i = 0; i < 6; i++)
```
```
    {
```
```
        np->child_ptr[i] = NULL;
```
```
    }
```
```
    return np;
```
```
}
```
```
void traverse(FusionTreeNode *p)
```
```
{
```
```
    cout<<endl;
```
```
    int i;
```
```
    for (i = 0; i < p->n; i++)
```
```
    {
```
```
        if (p->leaf == false)
```
```
        {
```
```
            traverse(p->child_ptr[i]);
```
```
        }
```
```
        cout << " " << p->data[i];
```
```
    } 
```
```
    if (p->leaf == false)
```
```
    {
```
```
        traverse(p->child_ptr[i]);
```
```
    }
```
```
    cout<<endl;
```
```
}
```
```
void sort(int *p, int n)
```
```
{
```
```
    int i, j, temp;
```
```
    for (i = 0; i < n; i++)
```
```
    {
```
```
        for (j = i; j <= n; j++)
```
```
        {
```
```
            if (p[i] > p[j])
```
```
            {
```
```
                temp = p[i];
```
```
                p[i] = p[j];
```
```
                p[j] = temp;
```
```
            }
```
```
        }
```
```
    }
```
```
}
```

int split_child(FusionTreeNode *x, int i)

```
{
```
```
    int j, mid;
```
```
    FusionTreeNode *np1, *np3, *y;
```
```
    np3 = init();
```
```
    np3->leaf = true;
```
```
    if (i == -1)
```
```
    {
```
```
        mid = x->data[2];
```
```
        x->data[2] = 0;
```
```
        x->n--;
```
```
        np1 = init();
```
```
        np1->leaf = false;
```
```
        x->leaf = true;
```
```
        for (j = 3; j < 5; j++)
```
```
        {
```

            np3->data[j - 3] = x->data[j];

            np3->child_ptr[j - 3] = x->child_ptr[j];

```
            np3->n++;
```
```
            x->data[j] = 0;
```
```
            x->n--;
```
```
        }
```
```
        for(j=0;j<6;j++)
```
```
        {
```
```
            x->child_ptr[j] = NULL;
```
```
        }
```
```
        np1->data[0] = mid;
```
```
        np1->child_ptr[np1->n] = x;
```

        np1->child_ptr[np1->n + 1] = np3;

```
        np1->n++;
```
```
        root = np1;
```
```
    }
```
```
    else
```
```
    {
```
```
        y = x->child_ptr[i];
```
```
        mid = y->data[2];
```
```
        y->data[2] = 0;
```
```
        y->n--;
```
```
        for (j = 3; j < 5; j++)
```
```
        {
```

            np3->data[j - 3] = y->data[j];

```
            np3->n++;
```
```
            y->data[j] = 0;
```
```
            y->n--;
```
```
        }
```
```
        x->child_ptr[i + 1] = y;
```
```
        x->child_ptr[i + 1] = np3; 
```
```
    }
```
```
    return mid;
```
```
}
```
```
void insert(int a)
```
```
{
```
```
    int i, temp;
```
```
    x = root;
```
```
    if (x == NULL)
```
```
    {
```
```
        root = init();
```
```
        x = root;
```
```
    }
```
```
    else
```
```
    {
```

        if (x->leaf == true && x->n == 5)

```
        {
```
```
            temp = split_child(x, -1);
```
```
            x = root;
```

            for (i = 0; i < (x->n); i++)

```
            {
```

                if ((a > x->data[i]) && (a < x->data[i + 1]))

```
                {
```
```
                    i++;
```
```
                    break;
```
```
                }
```

                else if (a < x->data[0])

```
                {
```
```
                    break;
```
```
                }
```
```
                else
```
```
                {
```
```
                    continue;
```
```
                }
```
```
            }
```
```
            x = x->child_ptr[i];
```
```
        }
```
```
        else
```
```
        {
```
```
            while (x->leaf == false)
```
```
            {
```

            for (i = 0; i < (x->n); i++)

```
            {
```

                if ((a > x->data[i]) && (a < x->data[i + 1]))

```
                {
```
```
                    i++;
```
```
                    break;
```
```
                }
```

                else if (a < x->data[0])

```
                {
```
```
                    break;
```
```
                }
```
```
                else
```
```
                {
```
```
                    continue;
```
```
                }
```
```
            }
```

                if ((x->child_ptr[i])->n == 5)

```
                {
```

                    temp = split_child(x, i);

                    x->data[x->n] = temp;

```
                    x->n++;
```
```
                    continue;
```
```
                }
```
```
                else
```
```
                {
```

                    x = x->child_ptr[i];

```
                }
```
```
            }
```
```
        }
```
```
    }
```
```
    x->data[x->n] = a;
```
```
    sort(x->data, 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 binary element\n";

```
          cin>>t;
```
```
          insert(t);
```
```
    }
```

    cout<<"traversal of constructed fusion tree\n";

```
    traverse(root);
```
```
    getch();
```
```
}
```

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.

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

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Implement Expression Tree

» Next - C++ Program to Implement Range Tree

Related Posts:

Recommended Articles: