// 二叉树的遍历

// 递归
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 InOrder2(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 PreOrder2(BiTree T){ // 先序非递归
    InitStack(S); BiTree p = T; // 遍历指针
    while(p || !IsEmpty(S)){
        if(p){
            visit(p); Push(S, p); // 访问并入栈 
            p = p -> lchild; // 左孩子不空，左拐
        } else{
            Pop(S, p);  // 出栈
            p = p -> rchild; // 往右走
        }
    }
}