非递归遍历二叉树

先序遍历·

/*对于任一结点cur：
1)访问结点cur，并将结点cur入栈;
2)判断结点cur的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点cur，循环至1);
    若不为空，则将cur的左孩子置为当前的结点cur;
3)直到cur为NULL并且栈为空，则遍历结束。*/
void NonRecursive::PreTraverse(BinaryTree *T) {
    stack<BinaryTree *> s;
    BinaryTree *cur=T;
    while (cur!=nullptr||!s.empty()) {
        while (cur!=nullptr) {
            cout << cur->val <<" ";
            s.push(cur);
            cur = cur->leftchild;
        }
        //涉及到pop的操作所以判定条件是栈不为空
        if (!s.empty()) {
            cur = s.top();
            s.pop();
            cur = cur->rightchild;
        }
    }
}

中序遍历

/*cur的左孩子置为当前的cur，然后对当前结点cur再进行相同的处理；
2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的cur置为栈顶结点的右孩子；
3)直到cur为NULL并且栈为空则遍历结束
*/
void NonRecursive::MidTraverse(BinaryTree *T) {
    stack<BinaryTree *>s;
    BinaryTree *cur = T;
    while (cur!=nullptr||!s.empty()) {
        while (cur!=nullptr) {
            s.push(cur);
            cur = cur->leftchild;
        }
        if (cur==nullptr) {
            cur = s.top();
            cout << cur->val << " ";
            s.pop();
        }
        cur = cur->rightchild;

    }
    cout << endl;//回车换行
}

后序遍历

//思想： 一共有两种情况
//①节点同时没有左孩子和右孩子，说明是根节点，可以遍历然后出栈；
//②或者不是根节点但同时左孩子和右孩子被访问过，也可以遍历后出栈
void NonRecursive::EndTraverse(BinaryTree *T) {
    stack<BinaryTree *> s;
    BinaryTree *cur ;
    BinaryTree *pre = nullptr;
    s.push(T);
    while (!s.empty()) {
        cur = s.top();
        if ((cur->leftchild==nullptr&&cur->leftchild==nullptr)  //没有左孩子和右孩子了说明可以访问
            ||  (pre!=nullptr&&  (pre==cur->leftchild||pre==cur->rightchild)) //存在子树同时左孩子和右孩子都被访问过了
            ) {
            cout << cur->val<<" ";
            s.pop();
            pre = cur;
        }
        else {
            //右孩子先入栈  左孩子后入栈
            if (cur->rightchild!=nullptr) {
                s.push(cur->rightchild);
            }
            if (cur->leftchild!=nullptr) {
                s.push(cur->leftchild);
            }
        }
    }
}