中序遍历非递归算法笔试题

中序遍历非递归算法

#define maxsize 100

typedef struct

{

    Bitree Elem[maxsize];

    int top;

}SqStack;

void InOrderUnrec(Bitree t)

{

    SqStack s;

    StackInit(s);

    p=t;

    while (p!=null || !StackEmpty(s))

    {

        while (p!=null)            //遍历左子树

        {

            push(s,p);

            p=p->lchild;

        }//endwhile

       

        if (!StackEmpty(s))

        {

            p=pop(s);

            visite(p->data);       //访问根结点

            p=p->rchild;           //通过下一次循环实现右子树遍历

        }//endif     

    }//endwhile

}//InOrderUnrec