【练习】实现二叉树的前序 / 中序 / 后序非递归遍历

//实现二叉树的前序 / 中序 / 后序非递归遍历
#include <iostream>
#include <stack>
using namespace std;

struct BinaryTreeNode
{
    BinaryTreeNode* _left;
    BinaryTreeNode* _right;
    int _data;

    BinaryTreeNode(const int& x)
        : _data(x)
        , _left(NULL)
        , _right(NULL)
    {}
};

void PrevOderNoR(BinaryTreeNode* root)
{
    stack<BinaryTreeNode*> s;

    BinaryTreeNode* cur = root;

    while (cur || !s.empty())
    {
        while (cur)
        {
            cout << cur->_data << " ";
            s.push(cur);
            cur = cur->_left;
        }
        
        BinaryTreeNode* top = s.top();
        s.pop();
        cur = top->_right;
    }
    cout << endl;
}

void InOderNoR(BinaryTreeNode* root)
{
    stack<BinaryTreeNode*> s;

    BinaryTreeNode* cur = root;

    while (cur || !s.empty())
    {
        while (cur)
        {
            s.push(cur);
            cur = cur->_left;
        }

        BinaryTreeNode* top = s.top();
        s.pop();
        cout << top->_data << " ";
        cur = top->_right;
    }
    cout << endl;
}

void PostOderNoR(BinaryTreeNode* root)
{
    stack<BinaryTreeNode*> s;

    BinaryTreeNode* cur = root;
    BinaryTreeNode* visit = NULL;

    while (cur || !s.empty())
    {
        while (cur)
        {
            s.push(cur);
            cur = cur->_left;
        }

        BinaryTreeNode* top = s.top();
        s.pop();
        if (top->_right == NULL || top->_right == visit)//如果右为空或者右被访问了才访问当前节点
        {
            cout << top->_data << " ";
            visit = top;
        }
        else if (top->_left == visit) // 如果左刚被访问过，当前根节点再次入栈
        {
            s.push(top);
            cur = top->_right;
        }

    }
    cout << endl;
}