二叉树遍历
二叉树链式存储结构定义

typedef struct BiTNode
{
    int data;
    struct BitTNode *lchild, *rchild;
}BitTNode, *BiTree;

1.先序遍历

void pre_order(BiTree)
{
    if(T != NULL)
    {
        visit(T);
        pre_order(T -> lchild);
        pre_order(T -> rchild);
    }
}

先序遍历（迭代）

void pre_order(BiTree T)
{
    init_stack(st);
    Bitree p = T;

    while(p || !stack_empty(st))
    {
        if(p)
        {
            visit(p);
            push(st, p);
            p = p -> lchild;
        }
        else
        {
            pop(st, p);
            p = p -> rchild;
        }
    }
}

2.中序遍历

void in_order(BiTree)
{
    if(T != NULL)
    {
        visit(T);
        in_order(T -> lchild);
        in_order(T -> rchild);
    }
}

中序遍历(迭代)

void in_order(BiTree T)
{
    init_stack(st);
    BiTree p = T;

    while(p || !stack_empty(st))
    {
        if(p)
        {
            push(st, p);
            p = p -> lchild;
        }
        else
        {
            pop(st, p);
            visit(p);
            p = p ->rchild;
        }
    }
}

3.后序遍历

void post_order(BiTree)
{
    if(T != NULL)
    {
        visit(T);
        post_order(T -> lchild);
        post_order(T -> rchild);
    }
}

后序遍历(迭代)

void post_order(BiTree T)
{
    init_stack(st);
    BiTree p = T, r = NULL;

    while(p || !stack_empty(st))
    {
        if(p)
        {
            push(st, p);
            p = p -> lchild;
        }
        else
        {
            get(st, p);

            if(p -> rchild && p -> rchild != r) 
            {
                p = p -> rchild;
            }
            else 
            {
                pop(st, p);
                visit(p);
                r = p;
                p = NULL;
            }

        }
    }

}

4.层序遍历

void level_order(BiTree T)
{
    init_queue(que);
    BiTree p;
    en_queue(que, T);

    while(!queue_empty(que))
    {
        de_queue(que, p);
        visit(p);
        if(p -> lchild != NULL) en_queue(que, p -> lchild);
        if(p -> rchild != NNLL) en_queue(que, p -> rchild);
    }

}