C++ Program to Implement Cartesian Tree

This C++ Program demonstrates operations on Cartesian Tree.

Here is source code of the C++ Program to demonstrate Cartesian Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C++ Program To Implement Cartesian Tree

```
 */
```
```
#include <iostream>
```
```
#include <cstdio>
```
```
#include <cstdlib>
```
```
using namespace std;
```
```
/*
```
```
 * Node Declaration
```
```
 */
```
```
struct node
```
```
{
```
```
    int data;
```
```
    struct node* left;
```
```
    struct node* right;
```
```
};
```
```
/*
```
```
 * Class Declaration
```
```
 */
```
```
class CTree
```
```
{
```
```
    public:
```
```
        node *newNode (int);
```
```
        int mini(int [], int, int);
```

        node *buildTree (int [], int, int);

```
        void printInorder (node* node);
```
```
        void display(node *, int);
```
```
        CTree()
```
```
        {}
```
```
};
```
```
 
```
```
/*
```
```
 * Main Contains Menu
```
```
 */
```
```
int main()
```
```
{
```
```
    CTree ct;
```
```
    int i, n;
```

    cout<<"Enter number of elements to be inserted: ";

```
    cin>>n;
```
```
    int a[n];
```
```
    for (i = 0; i < n; i++)
```
```
    {
```

        cout<<"Enter Element "<<i + 1<<" : ";

```
        cin>>a[i];
```
```
    }
```

    node *root = ct.buildTree(a, 0, n - 1);

    cout<<"Cartesian tree Structure: "<<endl;

```
    ct.display(root,1);
```
```
    cout<<endl;
```

    cout<<"\n Inorder traversal of the constructed tree \n"<<endl;

```
    ct.printInorder(root);
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```
```
 
```
```
/*
```
```
 * Creating New Node
```
```
 */
```
```
node *CTree::newNode (int data)
```
```
{
```
```
    node* temp = new node;
```
```
    temp->data = data;
```
```
    temp->left = NULL;
```
```
    temp->right = NULL;
```
```
    return temp;
```
```
}
```
```
 
```
```
/*
```
```
 * Finding index of minimum element
```
```
 */
```

int CTree::mini(int arr[], int strt, int end)

```
{
```

    int i, min = arr[strt], minind = strt;

```
    for (i = strt + 1; i <= end; i++)
```
```
    {
```
```
        if (arr[i] < min)
```
```
        {
```
```
            min = arr[i];
```
```
            minind = i;
```
```
        }
```
```
    }
```
```
    return minind;
```
```
}
```
```
 
```
```
/*
```
```
 * Function for Building Tree
```
```
 */
```

node *CTree::buildTree (int inorder[], int start, int end)

```
{
```
```
    if (start > end)
```
```
        return NULL;
```
```
    int i = mini(inorder, start, end);
```
```
    node *root = newNode(inorder[i]);
```
```
    if (start == end)
```
```
        return root;
```

    root->left  = buildTree(inorder, start, i - 1);

    root->right = buildTree(inorder, i + 1, end);

```
    return root;
```
```
}
```
```
 
```
```
/*
```
```
 * InOrder Traversal
```
```
 */
```

void CTree::printInorder (struct node* node)

```
{
```
```
    if (node == NULL)
```
```
        return;
```
```
    printInorder (node->left);
```
```
    cout<<node->data<<" ";
```
```
    printInorder (node->right);
```
```
}
```
```
 
```
```
/*
```
```
 * Display Tree
```
```
 */
```

void CTree::display(node *ptr, int level)

```
{
```
```
    int i;
```
```
    if(ptr == NULL)
```
```
        return;
```
```
    if (ptr != NULL)
```
```
    {
```
```
        display(ptr->right, level + 1);
```
```
        cout<<endl;
```
```
        for (i = 0;i < level;i++)
```
```
            cout<<"       ";
```
```
        cout<<ptr->data;
```
```
        display(ptr->left, level + 1);
```
```
    }
```
```
}
```

$ g++ Ctree.cpp
$ a.out
Enter number of elements to be inserted: 11
Enter Element 1 : 8
Enter Element 2 : 4
Enter Element 3 : 9
Enter Element 4 : 3
Enter Element 5 : 5
Enter Element 6 : 0
Enter Element 7 : 11
Enter Element 8 : 2
Enter Element 9 : 6
Enter Element 10 : 7 
Enter Element 11 : 12
Cartesian tree Structure: 
 
                                   12
                            7
                     6
              2
                     11
       0
                     5
              3
                            9
                     4
                            8
 
 Inorder traversal of the constructed tree 
 
8 4 9 3 5 0 11 2 6 7 12 
 
 
------------------
(program exited with code: 0)
Press return to continue

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 - Self Balancing Binary Search Tree in C++

» Next - C++ Program to Implement Expression Tree

Related Posts:

Check Computer Science Books
Apply for Computer Science Internship
Practice Design & Analysis of Algorithms MCQ
Practice Computer Science MCQs
Practice Programming MCQs

Recommended Articles: