SHARE
TWEET

InorderWithoutRecursion

apl-mhd Apr 21st, 2017 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3.  
  4. using namespace std;
  5.  
  6. struct tree{
  7.     char data;
  8.     struct tree *left;
  9.     struct tree  *right;
  10.  
  11. };
  12.  int index=-1;
  13. typedef struct tree tree;
  14.  tree *stack[100];
  15. tree *insert(tree *root){
  16.      
  17.      char ch;
  18.      
  19.      printf("%c has any Left child: ", root->data);
  20.         cin>>ch;
  21.         if(ch == 'y'){
  22.             root->left = new tree();
  23.             cout<<"Enter left child\n";
  24.             cin>>root->left->data;
  25.             insert(root->left);
  26.             }
  27.         else
  28.             root->left =NULL;
  29.            
  30.         printf("%c has any Right child:", root->data);
  31.         cin>>ch;
  32.        
  33.         if(ch == 'y'){
  34.             root->right = new tree();
  35.             cout<<"Enter right child\n";
  36.             cin>>root->right->data;
  37.             insert(root->right);
  38.             }
  39.         else
  40.             root->right = NULL;
  41. return root;     
  42. }
  43.  
  44.  
  45.  
  46. void push(tree *x){
  47.    
  48.     index++;
  49.    
  50.     stack[index]  = x;
  51.    
  52. }
  53. void pop(){
  54.    
  55.     index -=1;
  56. }
  57.  
  58. tree *top(){
  59.    
  60.    
  61.     return stack[index];
  62. }
  63.  
  64. bool empty(){
  65.    
  66.     if(index <0)
  67.         return true;
  68.        
  69.     return false;
  70.  
  71. }
  72.  
  73. void inorder(tree *root){
  74.     tree *x;
  75.     while(true){
  76.        
  77.         if(root !=NULL){
  78.            
  79.             push(root);
  80.             root=root->left;
  81.            
  82.             }
  83.         else{
  84.             if(empty())
  85.                 break;
  86.             x = top();
  87.             cout<<x->data;
  88.             pop();
  89.             root = x->right;   
  90.            
  91.             }
  92.            
  93.        
  94.     }
  95.    
  96. }
  97.  
  98.  
  99. int main(int argc, char **argv)
  100. {
  101.  
  102.    
  103.     tree *root;
  104.     root = new tree();
  105.     root->data = 'A';  
  106.     insert(root);
  107.     inorder(root);
  108.    
  109.    
  110.    
  111.    
  112.     return 0;
  113. }
RAW Paste Data
Top