数据结构-二叉树遍历非递归

前序遍历

void preorder(BTNODE BT)
{
    BTNODE STACK[100];
    int top = -1;
    STACK[++top] = BT;
    BTNODE p = null;

    while(top!=-1)
    {
        BTNODE p=STACK[top--];
        visit(p);
        if(p->right!=null)
        {
            STACK[++top] = p->right;
        }
        if(p->left!=null)
        {
            STACK[++top] = p->left;
        }
    }
}

中序遍历

void inorder(BTNODE BT)
{
    BTNODE STACK[100];
    BTNODE p = BT;
    int top=-1;

    while(top!=-1 || p!=null)
    {
        while(p!=null)
        {
            STACK[++top] = p;
            p=p->left;
        }
        if(top!=-1)
        {
            p = STACK[top--];
            visit(p);
            p=p->right;
        }
    }
}

后续遍历

void postorder(BTNODE BT)
{
    BTNODE STACK1[100];    // 遍历
    BTNODE STACK2[100];    // 逆后续
    int top1 = -1;
    int top2 = -1;
    STACK1[++top] = BT;
    BTNODE p = null;

    while(top1!=-1)
    {
        p=STACK1[top1--];
        STACK2[++top2]=p;
        if(p->left!=null)
        {
            STACK1[++top]=p->left;
        }
        if(p->right!=null)
        {
            STACK1[++top]=p->right;
        }
    }
    while(top2!=-1)
    {
        p=STACK1[top2--];
        visit(p);
    }
}