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);

}