Saturday, December 12, 2009

Iterative/Non-recursive version of pre order/in order traversal of a binary tree

struct node
{
int data;
int data1;
int data2;
struct node* left;
struct node* right;
};
struct node** stack;
int curr = -1;
void push(struct node* node)
{
++curr;
stack[curr] = node;
}

struct node* pop()
{
return stack[curr--];
}
void visit(struct node* curr)
{
printf("%d ",curr->data);
}

void preOrderiter(struct node* root)
{
printf("*************\n");
struct node* tmp = root;
while(curr != -1 || tmp)
{
while(tmp)
{
push(tmp);
visit(tmp);
tmp = tmp->left;
}
tmp = pop();
tmp = tmp->right;
}
printf("*************\n");
}


void inOrderiter(struct node* root)
{
printf("*************\n");
struct node* tmp = root;
while(curr != -1 || tmp)
{
while(tmp)
{
push(tmp);
tmp = tmp->left;
}
tmp = pop();
visit(tmp);
/*if(!tmp->right)
{
printStack();
}
else*/
tmp = tmp->right;
}
printf("*************\n");
}
int main()
{
stack = malloc(10*sizeof(struct node*));
}

No comments:

Blog Archive