先序遍历（根--左--右）

递归法

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

非递归法

void PreOrder(BiTree T){
    InitStack(S);                //使用栈存储二叉树的节点
    BiTree p = T;                //p为遍历二叉树的指针
    while(p || !IsEmpty(S)){    //二叉树不为空或栈不空是继续循环
        if(p != NULL){
            vist(p)                //访问拍p
            Push(S,p);            //p节点入栈
            p = p->lchild;        //继续向左遍历
        }
        else{
            Pop(S,p);            //p出栈
            p = p->rchild;        //转向右子树遍历
        }
    }
}

中序遍历（左--根--右）

递归法

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

非递归法

void InOrder(BiTree T){
    InitStack(S);                //使用栈存储二叉树的节点
    BiTree p = T;                //p为遍历二叉树的指针
    while(p || !IsEmpty(S)){    //二叉树不为空或栈不空是继续循环
        if(p != NULL){
            Push(S,p);            //p节点入栈
            p = p->lchild;        //继续向左遍历
        }
        else{
            Pop(S,p);            //p出栈
            visit(p);            //访问p
            p = p->rchild;        //转向右子树遍历
        }
    }
}

后序遍历（左--右--根）

递归法

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

非递归法

void PostOrder(BiTree T){
    InitStack(S);                    //使用栈存储二叉树的节点
    BiTree p = T;                    //p为遍历二叉树的指针
    BiTree r = NULL;                //记录最近访问的节点
    while(p || !IsEmpty(S)){        //二叉树不为空或栈不空是继续循环
        if(p != NULL){
            Push(S,p);                //p节点入栈
            p = p->lchild;            //继续向左遍历
        }
        else{
            GetTop(S,p);            //读取栈顶节点，不出栈
            if(p->rchild && p->rchild != r){    //右子树存在，且未被访问
                p = p->rchild;
                Push(S,p);                        //p节点入栈
                p = p->lchild;                    //转左遍历
            }
            else{
                Pop(S,p);                        //p出栈
                visit(p);                        //访问p
                r = p;                            //记录最近一次访问的节点
                p = NULL;
            }
        }
    }
}

层序遍历

void LevelOrder(BiTree T){
    InitQueue(Q);                //使用队列存储二叉树节点
    BiTree p;
    EnQueue(Q,T);                //根节点入队
    while(!IsEmpty(Q)){            //队列不空继续循环
        DeQueue(Q,p);            //队头节点出队
        vist(p);                //访问队头节点
        if(p->lchild != NULL){
            EnQueue(Q,p->lchild);    //左孩子入队
        }
        if(p->rchild != NULL){
            EnQueue(Q,p->rchild);    //右孩子入队
        }
    }            
}