二叉树非递归遍历

先序遍历非递归实现

从根节点开始向左遍历，因为是先序遍历，所以每次刚遇到的节点直接输出就行，并把节点加入栈中。单次while (p != nullptr)内循环结束，就代表以开始节点为子树的左子树已经遍历完毕，接下来就需要遍历最底层子树的右节点，即从栈中取出栈顶，也就是之前遍历左子树的最后一个节点，指向其的右儿子，如果有右儿子，则开始遍历以右儿子为根节点的子树的左子树，开始循环，如果没有右儿子，也就是p == nullptr的情况下，则取出下一个栈顶，直到栈为空为止。

void goPreOrder(BintreeNode *& root) {
    stack<BintreeNode*> st;
    BintreeNode* p = root;
    while (!st.empty() || p != nullptr) {
        while (p != nullptr) {
            cout << p->data;
            st.push(p);
            p = p->child[0];
        }
        if (!st.empty()) {
            p = st.top()->child[1];
            st.pop();
        }
    }
    return;
}

中序遍历非递归实现

先遍历以开始节点为根节点的当前子树的左子树，一路遍历到底，期间把遍历到的节点加入栈中，而后每次取出栈顶，准备遍历以其节点为根节点的子树的右子树时，就把取出的栈顶节点输出，因为这个节点已经没有左儿子了，按中序遍历的规则，已然能输出。先遍历完左子树，遍历期间的节点加入栈顶，然后取出栈顶，并输出，再遍历以取出栈顶为根节点的子树的右子树，直到最后，期间按序输出的节点就是中序遍历的结果。

void goInOrder(BintreeNode*& root) {
    stack<BintreeNode*> st;
    BintreeNode* p = root;
    while (!st.empty() || p != nullptr) {
        while (p != nullptr) {
            st.push(p);
            p = p->child[0];
        }
        if (!st.empty()) {
            p = st.top();
            st.pop();
            cout << p->data;
            p = p->child[1];
        }
    }
}

后序遍历非递归实现

后序遍历的非递归实现，则需要先遍历完所有的儿孙才可，那么我们只需要在之前两个非递归遍历的基础上进行修改，即把栈顶取出的节点，不进行弹出，直到其儿孙节点都遍历结束，也就是第二次从栈顶取出节点的时候，再把它输出。这样输出的序列，即是后序遍历的结果。

void goPostOrder(BintreeNode*& root) {
    stack<pair<BintreeNode*, bool>> st;
    BintreeNode* p = root;
    while (!st.empty() || p != nullptr) {
        while (p != nullptr) {
            st.push(make_pair(p, false));
            p = p->child[0];
        }
        if (!st.empty()) {
            pair<BintreeNode*, bool> &nowNode = st.top();
            if (nowNode.first->child[1] == nullptr || nowNode.second) {
                cout << nowNode.first->data;
                st.pop();
            }
            else {
                nowNode.second = true;
                p = nowNode.first->child[1];
            }
        }
    }
}