【基础题】--实现二叉树的前序 / 中序 / 后序非递归遍历

       二叉树的递归遍历，我们知道是很简单的，而非递归遍历则需要利用栈的先进后出特性来实现。

1、前序非递归遍历

       利用双重循环，内部循环将左孩子要入栈中直到左孩子为空，并且压一个输出一个数据，再判断栈顶的右孩子。若右孩子不为空，则再循环将其压入栈中，若右孩子为空，则pop栈顶数据。直到栈为空，遍历完成。

2、中序非递归遍历

       中序遍历与前序遍历是异曲同工的，只是应先将左孩子全部压入栈中，然后输出一个数据pop一个数据，并进行判断其右孩子是否存在。

3、后序非递归遍历

（1）单栈实现
       后序遍历与前序、中序遍历不同，即使找到最左孩子，也要记住其父节点，因为输出左孩子之后需要输出右孩子。这里利用prev记住当前输出数据。
（2）双栈实现
       建立两个栈，栈s1用来周转，先将根压入栈1再转入栈s2，之后将右树压入s1再转入s2，最后将左树压入s1再转入s2。

代码：

#include<iostream>
#include<stack>
using namespace std;

struct Node
{
    int _data;
    Node* _leftchild;
    Node* _rightchild;

    Node(int x)
        :_data(x)
        , _leftchild(NULL)
        , _rightchild(NULL)
    {}
};

class BinaryTree
{
public:
    BinaryTree(const int a[], int size, int invalide)
    {
        int index = 0;
        _root = _CreateBinaryTree(a, size, index, invalide);
    }

    Node* _CreateBinaryTree(const int a[], int size, int &index, int invalide)//二叉树的创建
    {
        Node* root = NULL;
        if (index < size && a[index] != invalide)
        {
            root = new Node(a[index]);
            root->_leftchild = _CreateBinaryTree(a, size, ++index, invalide);
            root->_rightchild = _CreateBinaryTree(a, size, ++index, invalide);
        }
        return root;
    }

    void PrevOrder()//前序遍历
    {
        if (_root == NULL)
            return;
        Node* cur = _root;
        stack<Node*> s;

        while (cur || !s.empty())
        {
            while (cur)
            {
                s.push(cur);
                cout << cur->_data << " ";
                cur = cur->_leftchild;
            }

            Node* top = s.top();
            s.pop();
            cur = top->_rightchild;
        }
    }


    void InOrder()//中序遍历
    {
        if (_root == NULL)
            return;
        Node* cur = _root;
        stack<Node*> s;

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

            Node* top = s.top();
            cout << top->_data << " ";
            s.pop();
            cur = top->_rightchild;
        }

    }

    void PostOrder()//后序遍历
    {
        if (_root == NULL)
            return;
        Node* cur = _root;
        Node* prev = cur;
        stack<Node*> s;

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

            cur = s.top();
            if (cur->_rightchild == NULL || cur->_rightchild == prev)
            {
                cout << cur->_data << " ";
                prev = cur;
                s.pop();
                cur = NULL;
            }
            else
                cur = cur->_rightchild;
        }
    }

    void PostOrder1()//双栈实现后序遍历
    {
        stack<Node*> s1, s2;
        Node* curr;             
        s1.push(_root);

        while (!s1.empty())  
        {   
            curr = s1.top();
            s1.pop();
            s2.push(curr);

            if (curr->_leftchild)
                s1.push(curr->_leftchild);

            if (curr->_rightchild)
                s1.push(curr->_rightchild);
        }

        while (!s2.empty())
        {
            cout<<s2.top()->_data<<" ";
            s2.pop();
        }
    }

private:
    Node* _root;
};

int main()
{
    int a[] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6, '#', '#' };
    BinaryTree tr(a, 12, '#');
    tr.PostOrder1();
    system("pause");
    return 0;
}