C++ Program to Implement B-Tree

This C++ program implements the B-Tree data structure. B-tree is a tree data structure that keeps data sorted and allows searches, sequential access and insertions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children

Here is the source code of the C++ program to display a B-Tree with a degree of 6. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

```
/*
```
```
 * C++ Program to Implement B-Tree
```
```
 */
```
```
#include<stdio.h>
```
```
#include<conio.h>
```
```
#include<iostream>
```
```
using namespace std;
```
```
struct BTreeNode
```
```
{
```
```
    int *data;
```
```
    BTreeNode **child_ptr;
```
```
    bool leaf;
```
```
    int n;
```
```
}*root = NULL, *np = NULL, *x = NULL;
```
```
BTreeNode * init()
```
```
{
```
```
    int i;
```
```
    np = new BTreeNode;
```
```
    np->data = new int[5];
```
```
    np->child_ptr = new BTreeNode *[6];
```
```
    np->leaf = true;
```
```
    np->n = 0;
```
```
    for (i = 0; i < 6; i++)
```
```
    {
```
```
        np->child_ptr[i] = NULL;
```
```
    }
```
```
    return np;
```
```
}
```
```
void traverse(BTreeNode *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(BTreeNode *x, int i)
```
```
{
```
```
    int j, mid;
```
```
    BTreeNode *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 element\n";
```
```
          cin>>t;
```
```
          insert(t);
```
```
    }
```

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

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

Output
 
enter the no of elements to be inserted
8
enter the element
10
enter the element
20
enter the element
5
enter the element
6
enter the element
12
enter the element
30
enter the element
7
enter the element
17
traversal of constructed tree
 5 6 7
 10
 12 17 20 30

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

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

« Prev Page - C++ program to Solve Tower of Hanoi Problem using Binary Value

» Next Page - C++ program to Solve Tower of Hanoi Problem using Stacks

Deep Dive @ Sanfoundry: