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.

  1. /*
  2.  * C++ Program To Implement Cartesian Tree
  3.  */
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. using namespace std;
  8. /*
  9.  * Node Declaration
  10.  */
  11. struct node
  12. {
  13.     int data;
  14.     struct node* left;
  15.     struct node* right;
  16. };
  17. /*
  18.  * Class Declaration
  19.  */
  20. class CTree
  21. {
  22.     public:
  23.         node *newNode (int);
  24.         int mini(int [], int, int);
  25.         node *buildTree (int [], int, int);
  26.         void printInorder (node* node);
  27.         void display(node *, int);
  28.         CTree()
  29.         {}
  30. };
  31.  
  32. /*
  33.  * Main Contains Menu
  34.  */
  35. int main()
  36. {
  37.     CTree ct;
  38.     int i, n;
  39.     cout<<"Enter number of elements to be inserted: ";
  40.     cin>>n;
  41.     int a[n];
  42.     for (i = 0; i < n; i++)
  43.     {
  44.         cout<<"Enter Element "<<i + 1<<" : ";
  45.         cin>>a[i];
  46.     }
  47.     node *root = ct.buildTree(a, 0, n - 1);
  48.     cout<<"Cartesian tree Structure: "<<endl;
  49.     ct.display(root,1);
  50.     cout<<endl;
  51.     cout<<"\n Inorder traversal of the constructed tree \n"<<endl;
  52.     ct.printInorder(root);
  53.     cout<<endl;
  54.     return 0;
  55. }
  56.  
  57. /*
  58.  * Creating New Node
  59.  */
  60. node *CTree::newNode (int data)
  61. {
  62.     node* temp = new node;
  63.     temp->data = data;
  64.     temp->left = NULL;
  65.     temp->right = NULL;
  66.     return temp;
  67. }
  68.  
  69. /*
  70.  * Finding index of minimum element
  71.  */
  72. int CTree::mini(int arr[], int strt, int end)
  73. {
  74.     int i, min = arr[strt], minind = strt;
  75.     for (i = strt + 1; i <= end; i++)
  76.     {
  77.         if (arr[i] < min)
  78.         {
  79.             min = arr[i];
  80.             minind = i;
  81.         }
  82.     }
  83.     return minind;
  84. }
  85.  
  86. /*
  87.  * Function for Building Tree
  88.  */
  89. node *CTree::buildTree (int inorder[], int start, int end)
  90. {
  91.     if (start > end)
  92.         return NULL;
  93.     int i = mini(inorder, start, end);
  94.     node *root = newNode(inorder[i]);
  95.     if (start == end)
  96.         return root;
  97.     root->left  = buildTree(inorder, start, i - 1);
  98.     root->right = buildTree(inorder, i + 1, end);
  99.     return root;
  100. }
  101.  
  102. /*
  103.  * InOrder Traversal
  104.  */
  105. void CTree::printInorder (struct node* node)
  106. {
  107.     if (node == NULL)
  108.         return;
  109.     printInorder (node->left);
  110.     cout<<node->data<<" ";
  111.     printInorder (node->right);
  112. }
  113.  
  114. /*
  115.  * Display Tree
  116.  */
  117. void CTree::display(node *ptr, int level)
  118. {
  119.     int i;
  120.     if(ptr == NULL)
  121.         return;
  122.     if (ptr != NULL)
  123.     {
  124.         display(ptr->right, level + 1);
  125.         cout<<endl;
  126.         for (i = 0;i < level;i++)
  127.             cout<<"       ";
  128.         cout<<ptr->data;
  129.         display(ptr->left, level + 1);
  130.     }
  131. }

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

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.