We help IT Professionals succeed at work.

Check out this week's podcast, "Dairy Farms to Databases: Community's Hand in Technology"Listen Now

x

Stack to simulate recursion

blackbeauty
blackbeauty asked
on
479 Views
Last Modified: 2010-05-18
Hi,
I need help on my program. The program is to write an iterative version (using stack )of a postorder traversal on a binary tree.
The function for inserting tree works perfectly but when i call on the function iter_postorder()...nothing happens. Please tell me where I went wrong.

#define CompLT(a,b) (a<b)
#define CompEQ(a,b) (a==b)
#define MAX_STACK_SIZE 100

typedef struct
{
      char name [5];
      struct Node *link;
} tree;
tree tree1;

typedef struct Node
{
      struct Node *left;
      struct Node *right;
      struct Node *parent;
      int data;
}node;


void iter_postorder(node *a)
{
      int top=-1;
      node *stack[MAX_STACK_SIZE];
      for(;;)
      {
            for(;a;a=a->left)
            {
                  if(top>=MAX_STACK_SIZE-1)
                  {
                  fprintf(stderr,"\nStack is full\n");
                        return;
                  }
                  stack[++top]=a;
            }
            if (top==-1)
            {
            fprintf(stderr,"\nStack is empty\n");
                  return;
            }
            a=stack[top--];
            if(!a->right)
            {
                  printf("%d ",a->data);
                  a=NULL;
            }
            else
                  a=a->right;

      }
}




void tread (tree *a)
{
      int key;
      node *x, *current, *parent;
      printf("\nWhat is the name of this tree? ");
      fgets(a->name,5,stdin);
      printf("\nInput the keys of this tree (-1 to end): \n");
      scanf("%d",&key);
      while (key!=-1)
      {
            x=(node*)malloc(sizeof(node));
            x->data=key;
            x->left=NULL;
            x->right=NULL;
            current=a->link;
            parent=0;
            while(current)
            {
                  parent=current;
                  current=CompLT(x->data,current->data) ? current->left:current->right;
            }
            if(parent)
            {
                  if(CompLT(x->data,parent->data))
                        parent->left=x;
                  else
                        parent->right=x;
            }
            else
                  a->link=x;
            scanf("%d",&key);
  }
}

int main(void)
{                /*calling functions*/
 tread(&tree1);
 iter_postorder(tree1.link);
}

 
Comment
Watch Question

Author

Commented:
Edited text of question

Author

Commented:
Edited text of question
Commented:
This one is on us!
(Get your first solution completely free - no credit card required)
UNLOCK SOLUTION

Author

Commented:
I ran the program using the pnode but it only prints out half of the tree and then it says the stack is empty. So not all the number inserted into the tree are printed out...just half of the keys.

Commented:
You only ever print out the right nodes. When you print out half the tree, it is the half that lies in the right nodes.

Commented:
emmons, how is 'node* stack[];' different from 'pnode stack[];'. They look the same since 'pnode stack[];' will get translated to 'struct Node* stack[];'.

The other observation here is that only the leaf nodes get displayed on the screen. The reason is simple - all the non-leaf nodes get popped from the stack but do not get displayed. The solution is to push them back onto the stack. This brings us to one more question - if they are pushed back onto the stack, then the next time they are popped they will still have a right node & hence it will translate into an infinite loop!

This infinite loop can be avoided by checking if the popped out node's right child has already been processed. So when you are printing the popped out node, check if this node is the right child of the next node on the stack. If yes the next node has been completely processed & hence needs to be popped & printed.

BlackBeauty, note that I arrived at the following solution based on your code. My objective was to work on your code not to rewrite it. Hence this may not be the most elegant solution but it works

Also I apologize if my explanation has not been very clear

Replace the following code
a=stack[top--];
if(!a->right)
{
  printf("%d ",a->data);
  a=NULL;
}
else
  a=a->right;


with the following code
a=stack[top--];
if(!a->right)
{
  printf("%d ",a->data);
  // Print out all the non-leaf nodes whose right child has been processed
  while (top >= 0 && stack[top]->right == a){
      a = stack[top--];
      printf("%d ",a->data);
  }

  a=NULL;
}
else {
  // Not a leaf node, so push it back
  stack[++top] = a;
  a=a->right;
}

Hope this helps

Wilfred

Author

Commented:
Thank you Emmons for trying to answer my question. Bravo to
wpinto for answering my question completely. you get an A++.

Commented:
But unfortunately I didn't get a single point for this answer. I also lost 10 points trying to read your response.

Regardless, I am glad to be of some help

Cheers,
Wilfred

Gain unlimited access to on-demand training courses with an Experts Exchange subscription.

Get Access
Why Experts Exchange?

Experts Exchange always has the answer, or at the least points me in the correct direction! It is like having another employee that is extremely experienced.

Jim Murphy
Programmer at Smart IT Solutions

When asked, what has been your best career decision?

Deciding to stick with EE.

Mohamed Asif
Technical Department Head

Being involved with EE helped me to grow personally and professionally.

Carl Webster
CTP, Sr Infrastructure Consultant
Empower Your Career
Did You Know?

We've partnered with two important charities to provide clean water and computer science education to those who need it most. READ MORE

Ask ANY Question

Connect with Certified Experts to gain insight and support on specific technology challenges including:

  • Troubleshooting
  • Research
  • Professional Opinions
Unlock the solution to this question.
Join our community and discover your potential

Experts Exchange is the only place where you can interact directly with leading experts in the technology field. Become a member today and access the collective knowledge of thousands of technology experts.

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.