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

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

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

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn