遍历二叉树的递归与非递归算法

利用递归实现二叉树的先序，中序，后序遍历操作

/* 先序、中序、后序递归遍历二叉树算法  */

void PreOrder(BiTree T)              //先序遍历
{
    if(T != NULL) {
        visit(T);                   //访问根节点
        PreOrder(T -> lchild);      //递归遍历左子数
        PreOrder(T -> rchild);      //递归遍历右子数
    }

}

void InOrder(BiTree T)  //中序遍历
{
    if(T != NULL) {
        InOrder(T -> lchild);
        visit(T);
        InOrder(T -> rchild);
    }
}

void PostOrder(BiTree T)  //后序遍历
{
    if(T != NULL) {
        PostOrder(T -> lchild);
        PostOrder(T -> rchild);
        visit(T);
    }
}

 

利用栈实现二叉树的先序，中序，后序遍历的非递归操作

/* 先序、中序、后序非递归遍历二叉树算法  */

void PreOrder(BiTree T)
{
    InitStack(s);
    BiTree p = T;
    while(p || !IsEmpty(S)) {
        while(p) {
            visit(p);
            push(S, p);
            p = p -> lchild;
        }
        if(IsEmpty(S)) {
            p = Pop(S);
            p = p -> rchild;
        }
    }

}

void InOrder(BiTree T)
{
    InitStack(S);
    BiTree p = T;
    while(p || !IsEmpty(S)) {
        if(p) {
            Push(S, p);
            p = p -> lchild;
        } else {
            Pop(S, p);
            visit(p);
            p = p -> rchild;
        }
    }
}

void PostOrder(BiTree T)
{
    InitStack(S);
    BiTree p, r;
    p = T;
    r = NULL;
    while(p || !IsEmpty(S)) {
        if(p) {
            Push(S, p);
            p = p -> lchild;
        } else {
            GetTop(S, p);
            if(p -> rchild && p -> rchild != r) {
                p = p -> rchild;
                push(S, p);
                p = p -> lchild;
            } else {
                Pop(S, p);
                visit(p);
                r = p;
                p = NULL;
            }
        }
    }
}