(PreOder | InOrder | PostOrder Traverse Using Non Recursive Calls) Binary Search Tree In Data Structure Using C++

on

Data Structure Using C++

Tree Data Structure

Binary Search Tree

(PreOder | InOrder | PostOrder Traverse Using Non Recursive Calls) Binary Search Tree

#include "treeNode.cpp"
#include "StackTemplate.cpp"
void insert(treeNode* root, int info);
void inorder(treeNode* root);
void preorder(treeNode* root);
void postorder(treeNode* root);
int main()
{
 int x[] = { 14, 15, 4, 9, 7, 18, 3, 5, 16,4, 20, 17, 9, 14, 5, -1};
 treeNode *root = new treeNode();
 root->setInfo(x[0]);
 for(int i=1; x[i]>0; i++ )
 {
  insert(root, x[i] );
 } 
 cout<<endl<< "inorder: "<<endl;   
 inorder(root);
 cout<<endl<<"preorder"<<endl;
 preorder(root);
 cout<<endl<<"postorder"<<endl;
 postorder(root);
}
void inorder(treeNode* root)
{
    stack<treeNode* > s; 
    treeNode* p;
    p = root;
    do
    {
        while( p != NULL )
        {
            s.push( p );
            p = p->getLeft();
        }
        // at this point, left tree is empty 
        if( !s.isEmpty() )
  {
        p = s.pop();
        cout << p->getInfo() << " ";
  // go back & traverse right subtree
        p = p->getRight(); 
  }
  } while ( !s.isEmpty() || p != NULL );
}
void preorder(treeNode* root)
{
 stack<treeNode*> s;
 s.push(root);
 while(!s.isEmpty())
 {
  treeNode *p=s.pop();
  cout<<p->getInfo()<<" ";
  
  if(p->getRight())
  {
   s.push(p->getRight());
  }
  if(p->getLeft())
  {
   s.push(p->getLeft());
  }
 }
}
void postorder(treeNode* root)
{
 stack<treeNode*> s;
 s.push(root); 
 stack<int> output;
 while(!s.isEmpty())
 {
  treeNode *p=s.pop();
  output.push(p->getInfo());
  
  if(p->getLeft())
  {
   s.push(p->getLeft());
  }
  if(p->getRight())
  {
   s.push(p->getRight());
  }
 }
 while(!output.isEmpty())
 {
  cout<<output.pop()<<" ";
 }
}

Let me know in the comment section if you have any question.

Previous Post:
(LevelOrder Traverse Using Non Recursive Calls) Binary Search Tree In Data Structure Using C++

Comments

Post a Comment