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

关于C语言非递归后序遍历二叉树的完整攻略，我们可以从以下几点进行讲解：

1. 非递归后序遍历二叉树原理

非递归后序遍历二叉树的原理是通过使用栈来模拟函数调用栈的过程，从而遍历二叉树。具体步骤如下：

• 首先将根节点入栈；
• 接着对于当前节点：
• 若其左右子节点都为空，即为叶子节点，直接将其弹出并输出；
• 若其右子节点非空，将其入栈；
• 若其左子节点非空，将其入栈；
• 重复以上步骤，直到栈空。

2. C语言代码实现

下面是C语言实现非递归后序遍历二叉树的代码

void PostOrderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }

    TreeNode *stack[SIZE];
    int top = -1; // 初始化栈顶

    TreeNode *p = root, *lastVisit = NULL; // p指向当前节点，lastVisit表示上一次访问的节点

    // 向左走到底，并将路径上的所有节点入栈
    while (p != NULL) {
        stack[++top] = p;
        p = p->left;
    }

    while (top >= 0) {
        p = stack[top--]; // 出栈一个节点，表示要访问它

        if (p->right == NULL || p->right == lastVisit) {
            // 如果当前节点没有右子节点，或者右子节点已经被访问过了，那么可以访问当前节点
            printf("%d ", p->val);
            lastVisit = p; // 标记当前节点已经被访问
        } else {
            // 如果当前节点有右子节点，并且右子节点没有被访问过，那么需要将当前节点重新入栈，并向右走到底
            stack[++top] = p;
            p = p->right;
            while (p != NULL) {
                stack[++top] = p;
                p = p->left;
            }
        }
    }
}

3. 示例说明

我们来看一下如何使用上面的代码进行遍历。假设现在有以下二叉树：

     1
   /   \
  2     3
 / \   / \
4   5 6   7

我们可以先定义这颗二叉树：

TreeNode* node1 = (TreeNode*)malloc(sizeof(TreeNode));
TreeNode* node2 = (TreeNode*)malloc(sizeof(TreeNode));
TreeNode* node3 = (TreeNode*)malloc(sizeof(TreeNode));
TreeNode* node4 = (TreeNode*)malloc(sizeof(TreeNode));
TreeNode* node5 = (TreeNode*)malloc(sizeof(TreeNode));
TreeNode* node6 = (TreeNode*)malloc(sizeof(TreeNode));
TreeNode* node7 = (TreeNode*)malloc(sizeof(TreeNode));

node1->val = 1;
node2->val = 2;
node3->val = 3;
node4->val = 4;
node5->val = 5;
node6->val = 6;
node7->val = 7;

node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;
node3->left = node6;
node3->right = node7;

node4->left = NULL;
node4->right = NULL;
node5->left = NULL;
node5->right = NULL;
node6->left = NULL;
node6->right = NULL;
node7->left = NULL;
node7->right = NULL;

然后调用PostOrderTraversal(node1);，就能够得到后序遍历的结果：4 5 2 6 7 3 1。

再比如现在有以下二叉树：

  1
   \
    2
     \
      3

我们可以定义它：

TreeNode* node1 = (TreeNode*)malloc(sizeof(TreeNode));
TreeNode* node2 = (TreeNode*)malloc(sizeof(TreeNode));
TreeNode* node3 = (TreeNode*)malloc(sizeof(TreeNode));

node1->val = 1;
node2->val = 2;
node3->val = 3;

node1->left = NULL;
node1->right = node2;
node2->left = NULL;
node2->right = node3;
node3->left = NULL;
node3->right = NULL;

然后调用PostOrderTraversal(node1);，就能够得到后序遍历的结果：3 2 1。

总之，通过上述的代码和示例，相信你已经完全掌握了如何使用C语言非递归方式实现二叉树的后序遍历了。