Binary tree creating and traversals

Program Description

The program shows creation and traversal of binary tree in preorder,inorder and postorder sequence using recursive and non recursive algorithms.

Recursive procedure for traversal of binary tree is very easy to implement and is defined within the btree class itself.

For non-recursive procedures stack data structure is used to keep track of the visited nodes and path to backtrack.

Stack class takes care of stack operations used in the traversal algorithm.

Class node is created for representing the nodes in the binary tree.

Program
/********************************************
*    Binary tree creating and traversals
* 
*    code.cheraus.com
*
*********************************************/


#include<iostream>
using namespace std;


/*

node class

This class defines the properties of the "nodes" in the binary tree.
Each node can store:
1) one integer data
2) Two pointers for left and right childs
3) integer flag (only used for postorder traversal)

While creating a new node,if no parameter is passed,
 its data is initialized with "-1", flag=0  and left and right pointers point to NULL.
 
If node is initialized with a parameter,its data is given the value of the parameter,
flag=0 and pointers point to NULL.

*/
class node
{
  public:
     int data;
     node *left;
     node *right;
     int flag; //used for postorder traversal


    //constructor without parameter
     node()
    {
       left=right=NULL;
       data=-1;
       flag=0;
    } 

    //constructor with parameter
    node(int x)
    { 
      data=x;
      left=NULL;
      right=NULL;
      flag=0;
   }

};



/*

stack class

This class implements the stack operations such as push,pop,show and empty.
These are used in non-recursive traversal of the binary tree.


*/  
class stack
{

  public: 
     int top;
     node *elements[100];

     stack()
     {
        top=-1;   //stack empty
     }

    void push(node *T)
    {
      elements[++top]=T; 
    }     

  
    node* pop()
   {
      return elements[top--];
   }

   void show()
   {
     cout<<"The stack is: ";
     int i=top;
     while(i>=0)
     {
        cout<<elements[i]->data<<",";
        i--;
     }
   }    
     
   int empty()
   {
      if(top==-1)
        return 1 ;   //stack is empty
 
      else
        return 0;   //stack is not empty
   }
           
};




/*
btree class

This class implements the "binary tree" data structure. Any object instantiated from 
this class is a binary tree.

The class only supports creation and traversal of the binary tree data structure.
Traversals in all three sequence i.e; preoder,inorder and postorder sequence with
recusive and non-recursive methods is implemented in this class.

*/
class btree
{
  public: 
    node *root;
    
     btree()
     {
          root=NULL;
      }
 

   //function for creation of binary tree   
   node *create()
   {
      int x;
      cout<<"Enter the data(-1 for NULL link): ";
      cin>>x;
      
      if(x==-1)
         return NULL;
        
     node *t;
     t=new node(x);

     cout<<"Enter the left child of "<<x<<": ";
     t->left=create();

     cout<<"Enter the right child of "<<x<<": ";
     t->right=create();
       
      root=t;
      return t;
   }


   
  // function for preorder recursive traversal of the binary tree
  void preorder(node *T)
   {
     
     if(T!=NULL)
     {
       cout<<T->data<<",";
       preorder(T->left);
       preorder(T->right);
 
     }
  }   


  // function for inorder recursive traversal of the binary tree
  void inorder(node *T)
  {
     if(T!=NULL)
     {
        inorder(T->left);
        cout<<T->data<<",";
        inorder(T->right);
     }
 } 
  

 // function for postorder recursive traversal of the binary tree
  void postorder(node *T)
   {
      if(T!=NULL)
      {
         postorder(T->left);
         postorder(T->right);
         cout<<T->data<<",";
       }  
   } 


   //function declarations for non-recursive traversal in preoder,inorder and post-order sequence
   void preorder_nr(node* T);
   void inorder_nr(node *T);
   void postorder_nr(node *T); 
};



//function definition for non-recursive preorder traversal
void btree::preorder_nr(node *T)
{
   stack s;
   
   while(T!=NULL)
   {
     cout<<T->data<<",";
     s.push(T);
     T=T->left;
   }
  
   while(!s.empty())
   {
      T=s.pop();
      T=T->right;
  

    while(T!=NULL)
     {
        cout<<T->data<<",";
        s.push(T);
        T=T->left;
     }       

  }
}

//function definition for non-recursive inorder traversal
void btree::inorder_nr(node *T)
{
 
  stack s;
  while(T!=NULL)
  {
    s.push(T);
    T=T->left;
  }
  
  while(!s.empty())
  {
    T=s.pop();
    cout<<T->data<<",";
    
    T=T->right;
   
    while(T!=NULL)
    {
      s.push(T);
      T=T->left;
    }  
   
 }

}   


//function definition for non-recursive post-order traversal
void btree::postorder_nr(node *T)
{
  stack s;
  
  while(T!=NULL)
  {
      T->flag=0; 
      s.push(T);
      T=T->left;
   }

  while(!s.empty())
  {
    T=s.pop();

    if(T->flag==0)   
     {
       T->flag=1; 
       s.push(T);
       T=T->right;
     }
    else
     {
       cout<<T->data<<",";
       continue;
      }

    while(T!=NULL)
    {
       T->flag=0;
       s.push(T);
       T=T->left;
    }

 }

}

int main()
{

 btree a;
  cout<<"\n\nCreating tree........\n\n";
  node *temp= a.create();
  cout<<"\n\nTree created\n\n";
  cout<<"Preorder Sequence: ";
  a.preorder(temp);

   cout<<"\nInorder sequence: ";
   a.inorder(temp);

   cout<<"\nPost Order sequence: ";
   a.postorder(temp);
  
   cout<<"\n\n";

  cout<<"Non recursive traversal: \n\n";
  cout<<"Preorder Sequence: ";
  a.preorder_nr(a.root);

  cout<<"\nInorder Sequence: ";
  a.inorder_nr(a.root);

  cout<<"\nPost Order Sequence: ";
  a.postorder_nr(a.root);
  cout<<"\n";
 
 return 0;

}

Output



Creating tree........

Enter the data(-1 for NULL link): 1
Enter the left child of 1: Enter the data(-1 for NULL link): 2
Enter the left child of 2: Enter the data(-1 for NULL link): 4
Enter the left child of 4: Enter the data(-1 for NULL link): 8
Enter the left child of 8: Enter the data(-1 for NULL link): -1
Enter the right child of 8: Enter the data(-1 for NULL link): -1
Enter the right child of 4: Enter the data(-1 for NULL link): 9
Enter the left child of 9: Enter the data(-1 for NULL link): -1
Enter the right child of 9: Enter the data(-1 for NULL link): -1
Enter the right child of 2: Enter the data(-1 for NULL link): 5
Enter the left child of 5: Enter the data(-1 for NULL link): -1
Enter the right child of 5: Enter the data(-1 for NULL link): -1
Enter the right child of 1: Enter the data(-1 for NULL link): 3
Enter the left child of 3: Enter the data(-1 for NULL link): 6
Enter the left child of 6: Enter the data(-1 for NULL link): -1
Enter the right child of 6: Enter the data(-1 for NULL link): -1
Enter the right child of 3: Enter the data(-1 for NULL link): 7
Enter the left child of 7: Enter the data(-1 for NULL link): -1
Enter the right child of 7: Enter the data(-1 for NULL link): -1


Tree created

Preorder Sequence: 1,2,4,8,9,5,3,6,7,
Inorder sequence: 8,4,9,2,5,1,6,3,7,
Post Order sequence: 8,9,4,5,2,6,7,3,1,

Non recursive traversal:

Preorder Sequence: 1,2,4,8,9,5,3,6,7,
Inorder Sequence: 8,4,9,2,5,1,6,3,7,
Post Order Sequence: 8,9,4,5,2,6,7,3,1,

ΓΏ

Comments
comments powered by Disqus