fork download
copy 
  1. #include <iostream>
  2. #include <functional>
  3. #include <stack>
  4.  
  5. struct tNode {
  6.   char data;
  7.   struct tNode *left;
  8.   struct tNode *right;
  9. };
  10.  
  11. // Function to create a new node
  12. tNode *newNode(char data) {
  13.   tNode *node = new tNode;
  14.   node->data = data;
  15.   node->left = NULL;
  16.   node->right = NULL;
  17.   return node;
  18. }
  19.  
  20. // Function to insert nodes in level order
  21. tNode *insertLevelOrder(char arr[], tNode *root, int i, int n) {
  22.   // Base case for recursion
  23.   if (i < n) {
  24.     tNode *temp = newNode(arr[i]);
  25.     root = temp;
  26.  
  27.     // insert left child
  28.     root->left = insertLevelOrder(arr, root->left, 2 * i + 1, n);
  29.  
  30.     // insert right child
  31.     root->right = insertLevelOrder(arr, root->right, 2 * i + 2, n);
  32.   }
  33.   return root;
  34. }
  35.  
  36. // Function to delete the given tree
  37. void deleteTree(tNode *node) {
  38.   if (node == NULL)
  39.     return;
  40.  
  41.   /* first delete both subtrees */
  42.   deleteTree(node->left);
  43.   deleteTree(node->right);
  44.  
  45.   /* then delete the node */
  46.   // std::cout << "Deleting node: " << node->data << std::endl;
  47.   delete node;
  48. }
  49. void in_order(tNode* node, const std::function<void(tNode*)>& visitor) {
  50.     if (node == nullptr) {
  51.     	return;
  52.     };
  53.     in_order(node->left, visitor);
  54.     visitor(node);
  55.     in_order(node->right, visitor);
  56. }
  57. void pre_order_stack(tNode* root, const std::function<void(tNode*)>& visitor) {
  58.     std::stack<tNode*> stack;
  59.     stack.push(root);
  60.     while (!stack.empty()) {
  61.         tNode *curr = stack.top();
  62.         stack.pop();
  63.         visitor(curr);
  64.         // With this approach we visit "null" nodes, which can be useful.
  65.         // Alternatively we could move the condition to the push:
  66.         //if (curr->right != nullptr) stack.push(curr->right);
  67.         if (curr == nullptr) continue;
  68.  
  69.         if (curr->right!=NULL) {
  70.             stack.push(curr->right);
  71.         }
  72.         if (curr->left!=NULL) {
  73.             stack.push(curr->left);
  74.         }
  75.  
  76.     }
  77. }
  78. void post_order_nonrecursive(tNode *root, const std::function<void(tNode*)>& visitor) {
  79.     std::stack<tNode*> s;
  80.     tNode *current = root;
  81.     while (true) {
  82.         // Explore left, but remember node & right child
  83.         if (current != nullptr) {
  84.             if (current->right != nullptr)
  85.                 s.push(current->right);
  86.             s.push(current);
  87.             current = current->left;
  88.             continue;
  89.         }
  90.         // current == nullptr
  91.         if (s.empty()) return;
  92.         current = s.top();
  93.         s.pop();
  94.         // If we have the right child remembered, 
  95.         // it would be on the top of the stack.
  96.         if (current->right && !s.empty() && current->right == s.top()) {
  97.             // if it is, we must visit it (and it's children) first
  98.             s.pop();
  99.             s.push(current);
  100.             current = current->right;
  101.         } else {
  102.             visitor(current);
  103.             current = nullptr;
  104.         }
  105.     }
  106. }
  107. // Driver program to test above function
  108. int main() {
  109.   char arr[]={'+','2','+',NULL,NULL,'2','*',NULL,NULL,NULL,NULL,NULL,NULL,'2','+',NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,'2','2'};
  110.   tNode *root = insertLevelOrder(arr, root, 0, 31);
  111.   in_order(root, [](tNode* node){std::cout << node->data << " ";});
  112.   std::cout<<"\n";
  113.   pre_order_stack(root, [](tNode* node){std::cout << node->data << " ";});
  114.   std::cout<<"\n";
  115.   post_order_nonrecursive(root, [](tNode* node){std::cout << node->data << " ";});
  116.   deleteTree(root);
  117.   root = NULL;
  118.  
  119.   return 0;
  120. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
       2        +    2    +  2  * 2 + 2 
+ 2               + 2       * 2   + 2 2 
              2       2   2 2 2 + * + +
https://ideone.com/66QPWE
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!