二叉树前、中、后遍历的非递归实现。

1.前序遍历
利用栈，访问顺序为根，左，右，压栈是先压右，左边后进就可以先访问。

void _PrevOrder_NoR(BinaryTreeNode<T> *root)
    {
        if(root == NULL)
        {
            return;
        }
        stack<BinaryTreeNode<T>*> s;
        s.push(root);
        while(!s.empty())
        {
            BinaryTreeNode<T> *top = s.top();
            s.pop();
            if(top)
            {
                cout<<top->_data<<" ";
            }
            if(top->_right)
            {
                s.push(top->_right);
            }
            if(top->_left)
            {
                s.push(top->_left);
            }
        }
    }

2.中序遍历

void _InOrder_NoR(BinaryTreeNode<T> *root)
    {
        if(root == NULL)
        {
            return;
        }
        stack<BinaryTreeNode<T>*> s;
        BinaryTreeNode<T> *cur = root;
        while(cur || !s.empty())
        {
            if(cur)
            {
                s.push(cur);
                cur = cur->_left;
            }
            else
            {
                cur = s.top();
                s.pop();
                cout<<cur->_data<<" ";
                cur = cur->_right;
            }
        }
    }

3.后序遍历
从左上到右下斜着遍历的。依然利用栈。

void _PostOrder_NoR(BinaryTreeNode<T> *root)
    {
        if(root == NULL)
        {
            return;
        }
        stack<BinaryTreeNode<T>*> s;
        BinaryTreeNode<T> *cur = root;
        BinaryTreeNode<T> *PreVisited = NULL;
        while(cur)
        {
            s.push(cur);
            cur = cur->_left;
        }
        while(!s.empty())
        {
            BinaryTreeNode<T> *top = s.top();
            s.pop();
            //根节点想要被访问，必须右孩子被访问过，或者没有有孩子
            if(top->_right == NULL || PreVisited == top->_right)
            {
                cout<<top->_data<<" ";
                PreVisited = top;
            }
            else
            {
                s.push(top);
                top = top->_right;
                while(top)
                {
                    s.push(top);
                    top = top->_left;
                }
            }
        }
    }