Solved

Stack to simulate recursion

Posted on 1997-11-12
8
444 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);
}

 
0
Comment
Question by:blackbeauty
  • 4
  • 2
  • 2
8 Comments
 

Author Comment

by:blackbeauty
Comment Utility
Edited text of question
0
 

Author Comment

by:blackbeauty
Comment Utility
Edited text of question
0
 
LVL 4

Accepted Solution

by:
emmons earned 100 total points
Comment Utility
First, it is not that nothing happens. It prints the top entry on the stack and then exits, right?
The array you declared does not do what you think.
Instead, up at the typedef, add another def for pointer to node, something like...
typedef struct Node
{
  struct Node *left;
  struct Node *right;
  struct Node *parent;
  int data;
}node, *pnode;

and then change the declaration to be...
      pnode stack[MAX_STACK_SIZE];
see if that helps
0
 

Author Comment

by:blackbeauty
Comment Utility
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.
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 4

Expert Comment

by:emmons
Comment Utility
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.
0
 
LVL 2

Expert Comment

by:wpinto
Comment Utility
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

0
 

Author Comment

by:blackbeauty
Comment Utility
Thank you Emmons for trying to answer my question. Bravo to
wpinto for answering my question completely. you get an A++.
0
 
LVL 2

Expert Comment

by:wpinto
Comment Utility
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
0

Featured Post

Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now