C++ Program to Implement Cartesian Tree

Code:

#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 "<
        cin>>a[i];
    }
    node *root = ct.buildTree(a, 0, n - 1);
    cout<<"Cartesian tree Structure: "<
    ct.display(root,1);
    cout<
    cout<<"\n Inorder traversal of the constructed tree \n"<
    ct.printInorder(root);
    cout<
    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<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<
        for (i = 0;i < level;i++)
            cout<<"       ";
        cout<data;
        display(ptr->left, level + 1);
    }
}


Output:

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



More C++ Programs: