树的非递归遍历——后序

后序遍历较为复杂，没有想出来，参考了 二叉树的非递归遍历 原理如下
1、对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。
2、若非上述两种情况，则将P的右孩子和左孩子依次入栈

//后序遍历
void postorder(Node *root)
{
    if (root == NULL)
        return;
    postorder(root->left);
    postorder(root->right);
    cout<<root->val<<" ";
}

//非递归实现
/*对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；
或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。
若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，
左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。*/
void postorderloop(Node *root)
{
    if (root == NULL)
        return;
    stack<Node *> sn;
    Node *cur = NULL;
    Node *pre = NULL;
    sn.push(root);
    while(sn.size())
    {
        cur = sn.top();
        if ((cur->left==NULL&&cur->right==NULL) ||
            (pre!=NULL&&(pre==cur->left||pre==cur->right)))
        {
            cout<<cur->val<<" ";
            sn.pop();
            pre = cur;
        }
        else
        {
            if (cur->right)
                sn.push(cur->right);
            if (cur->left)
                sn.push(cur->left);
        }
    }
}