后序遍历非递归算法c++的完整代码实现

下面是后序遍历的非递归算法的完整代码实现，使用栈来实现：

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

// 二叉树结点的数据结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 后序遍历的非递归算法
void postorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    stack<TreeNode*> s;
    TreeNode* cur = root;
    TreeNode* pre = NULL;
    while (cur != NULL || !s.empty()) {
        while (cur != NULL) {
            s.push(cur);
            cur = cur->left;
        }
        cur = s.top();
        if (cur->right == NULL || cur->right == pre) {
            cout << cur->val << " ";
            s.pop();
            pre = cur;
            cur = NULL;
        } else {
            cur = cur->right;
        }
    }
}

// 测试
int main() {
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);
    cout << "后序遍历结果：";
    postorderTraversal(root);
    cout << endl;
    return 0;
}

其中，每次遍历结点时，需要判断其右子树是否已经遍历过，如果已经遍历过，则可以输出该结点。否则，需要遍历其右子树。使用一个`pre`指针记录上一个被遍历的结点，如果当前结点的右子树被遍历过，则将当前结点弹出栈，并更新`pre`指针。