C++ program that uses non-recursive functions to traverse a binary tree in Post-order

2 Responses to “C++ program that uses non-recursive functions to traverse a binary tree in Post-order”

1. Rizoan Toufiq says:

   May 16, 2010 at 6:05 pm

   more easy code :
   file : a.in
   _____________________________
   10
   LR 6
   L 3
   RL 5
   RR 8
   R 7
   LLL 4
   _____________________________

   code :
   /***********************************
   Algorithm: Create and Traverse a Binary Tree
   implementation: Link List[non recursively]
   Copy right @ rizoan toufiq
   ************************************/
   #include
   #include
   #include
   #include
   #include
   using namespace std;
   #define s 100
   typedef struct tree{
   int data;
   struct tree *right;
   struct tree *left;
   }node;
   node *root=NULL;
   /******creat a root of tree***************/
   void makeroot(int v){
   root=(node *)malloc(sizeof(node));
   (root)->right=NULL;
   (root)->left=NULL;
   (root)->data=v;
   }
   /****** create tree ********************/
   void creattree(char path[],int v){
   //path sent by value
   node *r=NULL,*t=NULL;
   int i;
   r=root;
   for(i=0;ileft==NULL){//no node
   t=(node *)malloc(sizeof(node));
   t->right=NULL;
   t->left=NULL;
   t->data=-1;
   r->left=t;
   r=r->left;
   }
   else//move left
   r= r->left;
   }
   else{
   if(r->right==NULL){//no node
   t=(node *)malloc(sizeof(node));
   t->right=NULL;
   t->left=NULL;
   t->data=-1;
   r->right=t;
   r=r->right;
   }
   else//move left
   r= r->right;
   }
   }
   r->data = v;//set value of empty node
   }
   /************ inorder traverse ***************/
   void inorder(struct tree *r){//call by value
   stackstk;
   while(1){
   //push left most path
   if(r!=NULL){
   stk.push(r);
   r=r->left;
   }
   else{
   //no node for back track
   if(stk.empty())
   break;
   else{//backtracking
   r=stk.top();
   stk.pop();
   //process data
   if(r->data==-1)
   printf(“NULL_NODE “);
   else
   printf(“%d “,r->data);
   r=r->right;
   }
   }
   }
   }
   /************preorder traverse*****************/
   void preorder(struct tree *r){
   stackstk;
   stk.push(NULL);
   while(r!=NULL){
   if(r->data==-1)
   printf(“NULL_NODE “);
   else
   printf(“%d “,r->data);

   if(r->right!=NULL)
   stk.push(r->right);
   if(r->left!=NULL)
   r=r->left;
   else{
   r=stk.top();
   stk.pop();
   }
   }
   }
   /***********postorder traverse*****************/
   void postorder(struct tree *r){
   stackstk;
   bool a[s]={true};//identify left node
   int c = 0;// for break/count stack data
   stk.push(NULL);
   while(1){
   //Push left most path on stack
   while(r!=NULL){
   stk.push(r);
   c++;
   a[c] = true;
   if(r->right!=NULL){
   stk.push(r->right);
   c++;
   a[c]=false;
   }
   r= r->left;
   }
   //pop node from stack
   r=stk.top();
   stk.pop();
   while(a[c]==true){
   //process in data
   if(r->data==-1)
   printf(“NULL_NODE “);
   else
   printf(“%d “,r->data);
   c–;
   if(c<=0)
   break;
   r=stk.top();
   stk.pop();
   if(stk.empty())
   break;
   }
   c–;
   if(c<=0)
   break;
   }
   }
   /************* main **************************/
   int main(){
   int value;
   char str[s];
   FILE *F=freopen("a.in","r",stdin);
   if(F==NULL){
   printf("Ops!\n");
   return 1;
   }
   scanf("%d\n",&value);
   makeroot(value);
   while(scanf("%s %d\n",str,&value)!=EOF){
   creattree(str,value);
   }

   printf("\nInorder BT:\n———–\n\t");
   inorder(root);
   printf("\n\n");

   printf("\npreorder BT:\n———–\n\t");
   preorder(root);
   printf("\n\n");

   printf("\npostorder BT:\n———–\n\t");
   postorder(root);
   printf("\n\n");
   return 0;
   }
   /******************** end *******************/
2. Assassin says:

   May 10, 2012 at 2:13 pm

   Rizoan Toufiq your code is excellent. tanx

Leave a Reply