非递归后序遍历二叉树C语言

非递归后序遍历二叉树通常使用栈数据结构来实现。这个过程可以分为三个步骤：

1. **初始化**：创建一个空栈，并将根节点压入栈中。
2. **循环**：当栈不为空时，继续执行以下操作：
- 弹出栈顶元素，检查是否为空，如果为空则结束循环；
- 否则，将其右孩子（如果存在）压入栈，然后将其左孩子（如果存在）压入栈。这样确保了在后序遍历时先访问左子树再访问右子树。
3. **访问节点**：在弹出当前节点后，对其进行相应的操作，比如打印节点值或做其他处理。

以下是简单的C语言代码实现非递归后序遍历：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 后序遍历函数
void postorderTraversal(TreeNode* root) {
    if (root == NULL) return; // 如果节点为空，直接返回

    stack<TreeNode*> s;
    TreeNode* curr = root; // 初始化当前节点
    TreeNode* lastVisited = NULL; // 上一次访问的节点

    while (curr != NULL || !s.empty()) { // 循环条件
        while (curr != NULL) { // 先处理当前节点
            s.push(curr);
            curr = curr->left;
        }
        
        curr = s.top(); // 取栈顶未访问的节点
        s.pop();

        // 确保当前节点是最后一个访问的右子节点
        while (lastVisited != NULL && curr == lastVisited->right)
            curr = lastVisited = s.top();

        printf("%d ", curr->val); // 访问节点
        lastVisited = curr; // 更新上一次访问的节点
        curr = curr->right; // 转向右子节点
    }
}

int main() {
    // 示例：构建二叉树...
    TreeNode* root = ...;
    
    postorderTraversal(root);

    return 0;
}