Non Recursive Traversal
// Non-recursive Inorder/Preorder Print 
 
typedef struct {
    Tnode *stack[100];
    int cnt;
} Stack;
 
void push(Stack *s, Tnode *node)
{
    s->stack[s->cnt] = node; 
    s->cnt++;
}
 
Tnode* pop(Stack *s)
{
    if (s->cnt == 0) {
        printf("stack empty!\n");
        return NULL;
    }
    else 
        return s->stack[--(s->cnt)];
}
 
int empty(Stack *s)
{
    return (!s->cnt)?1:0;
}
 
void NR_Inorder2(Node *root)
{
    Stack s;
    s.cnt = 0;
 
    while (1) {
        while (root) {            // Push all left predecessors into Stack
            push(&s, root);
            root = root->left;
        }
 
        Node *tmp = pop(&s);        // Once no left child == NULL, pop one node and output it.
        if (!tmp)
            return;
        printf("%d ", tmp->data);
        root = tmp->right;          // Repeat previous steps. This time, start to push all
    }         //  left predecessors of the poped out node (ie. the node which is just outputed.)
}
 
void NR_Inorder(Tnode *head)
{
    if (head == NULL)
        return;
 
    Stack my_s, visit_s;
    my_s.cnt = visit_s.cnt = 0;
    push(&my_s, head);
    push(&visit_s, NULL);
 
    Tnode *p, *visit;
    while (!empty(&my_s)) {
        p = pop(&my_s);
        visit = pop(&visit_s);
 
        if (visit == NULL && (p->right != NULL || p->left != NULL)) {
            if (p->right != NULL) {
                push(&my_s, p->right);
                push(&visit_s, (Tnode*)0);
            }
 
            push(&my_s, p);
            push(&visit_s, (Tnode*)1);
 
            if (p->left != NULL) {
                push(&my_s, p->left);
                push(&visit_s, (Tnode*)0);
            }
        }
        else 
            printf("%d ", p->data);
    }
}
 
void NR_Postorder(Tnode *head)
{
    if (head == NULL)
        return;
 
    Stack my_s, visit_s;
    my_s.cnt = visit_s.cnt = 0;
    push(&my_s, head);
    push(&visit_s, NULL);
 
    Tnode *p, *visit;
    while (!empty(&my_s)) {
        p = pop(&my_s);
        visit = pop(&visit_s);
 
        if (visit == NULL && (p->right != NULL || p->left != NULL)) {
            push(&my_s, p);
            push(&visit_s, (Tnode*)1);
 
            if (p->right != NULL) {
                push(&my_s, p->right);
                push(&visit_s, (Tnode*)0);
            }
 
            if (p->left != NULL) {
                push(&my_s, p->left);
                push(&visit_s, (Tnode*)0);
            }
        }
        else 
            printf("%d ", p->data);
    }
}
 
void NR_Preorder(Tnode *head)
{
    if (head == NULL)
        return;
 
    Stack my_stack;
    my_stack.cnt = 0;
    Tnode *p;
    push(&my_stack, head);
 
    while (!empty(&my_stack)) {
        p = pop(&my_stack);
        printf("%d ", p->data);
 
        if (p->right != NULL)
            push(&my_stack, p->right);
        if (p->left != NULL)
            push(&my_stack, p->left);
    }
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License