目录

先序遍历

中序遍历

后序遍历

先序遍历

//8、二叉树的非递归遍历---先序遍历
void PreOrderN(BiTree T){
    BiTree stack[MaxSize],p = T;
    int top = -1;
    while(p || top != -1){
        if(p){
            Visit(p);
            stack[++top] = p;//压栈
            p = p -> lchild;
        }else{
            p = stack[top--];//此时左子树是遍历结束的，所以栈顶元素直接出栈
            p = p -> rchild;
        }
    }
}

中序遍历

//9、二叉树的非递归遍历---中序遍历
void InOrderN(BiTree T){
    BiTree stack[MaxSize],p = T;
    int top = -1;
    while(p || top != -1){
        if(p){
            stack[++top] = p;//压栈
            p = p -> lchild;
        }else{
            p = stack[top--];//此时左子树是遍历结束的，所以栈顶元素直接出栈
            Visit(p);
            p = p -> rchild;
        }
    }
}

后序遍历

//10、二叉树的非递归遍历---后序遍历
//void PostOrderN(BiTree T){
//    BiTree stack[MaxSize],p = T;
//    int top = -1;
//    while(p || top != -1){
//        if(p){
//            stack[++top] = p;//压栈
//            p = p -> lchild;
//        }else{
//            p = stack[top];//注意这边不能出栈，因为栈顶的元素还没有访问过
//            p = p -> rchild;
//Visit(p);如果Visit直接在这边写的话那么是不对的，因为并不能保证此时p节点是“叶子节点”，
//        }
//    }
//}

void PostOrderN(BiTree T){
    BiTree stack[MaxSize],p = T;
    int top = -1;
    while(p || top != -1){
        if(p){
            stack[++top] = p;//压栈
            p -> tag = 1;
            p = p -> lchild;
        }else{
            p = stack[top];//注意这边不能出栈，因为栈顶的元素还没有访问过
            if(p -> tag == 1){
                p -> tag = 2;
                p = p -> rchild;
            }else{
                Visit(p);
                top--;
                p = NULL;//让p为空后才能继续取栈顶新元素进行下一步
            }
        }
    }
}
//11、二叉树的非递归遍历---中序遍历(当结构体不能改变时---也就是不能自己添加tag时）
typedef struct BiTreeNode{
    int data;
    struct BiTreeNode *lchild,*rchild;
}BiTreeNode,*BiTree;

void PostOrderN(BiTree T){
    BiTree stack[MaxSize],p = T;
    int top = -1,tag[MaxSize] = {0};
    while(p || top != -1){
        if(p){
            stack[++top] = p;//压栈
            tag[top] = 1;
            p = p -> lchild;
        }else{
            p = stack[top];//注意这边不能出栈，因为栈顶的元素还没有访问过
            if(tag[top] == 1){
                tag[top] = 2;//改成 2 是因为下面要p = p -> rchild
                p = p -> rchild;
            }else{
                Visit(p);
                top--;
                p = NULL;//让p为空后才能继续取栈顶新元素进行下一步
            }
        }
    }
}