Solved
Stack to simulate recursion
Posted on 1997-11-12
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);
}