后序遍历的非递归算法c语言

后序遍历的非递归算法可以使用栈来实现，具体步骤如下：

1. 创建一个栈，将二叉树的根节点压入栈中。
2. 创建一个指针p，指向上一次访问的节点，初始值为NULL。
3. 当栈不为空时，进行如下操作：
- 从栈顶弹出一个节点，并将其压入辅助栈中。
- 如果该节点的左右子树都为空，或者上一次访问的节点是该节点的左右子树中的一个，则可以访问该节点，并将其弹出辅助栈，将p指向该节点。
- 否则，将该节点的右子树和左子树依次压入栈中。
4. 重复步骤3，直到栈为空。

以下是使用C语言实现后序遍历的非递归算法的代码：

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

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

// 定义栈类型
typedef struct StackNode {
    TreeNode* node;
    struct StackNode* next;
} StackNode;

typedef struct Stack {
    StackNode* top;
} Stack;

// 初始化栈
void initStack(Stack* stack) {
    stack->top = NULL;
}

// 判断栈是否为空
int isStackEmpty(Stack* stack) {
    return stack->top == NULL;
}

// 获取栈顶元素
TreeNode* getStackTop(Stack* stack) {
    if (isStackEmpty(stack)) {
        return NULL;
    }
    return stack->top->node;
}

// 入栈
void push(Stack* stack, TreeNode* node) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    newNode->node = node;
    newNode->next = stack->top;
    stack->top = newNode;
}

// 出栈
TreeNode* pop(Stack* stack) {
    if (isStackEmpty(stack)) {
        return NULL;
    }
    TreeNode* node = stack->top->node;
    StackNode* temp = stack->top;
    stack->top = stack->top->next;
    free(temp);
    return node;
}

// 后序遍历（非递归）
void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack stack1, stack2;
    initStack(&stack1);
    initStack(&stack2);
    push(&stack1, root);
    while (!isStackEmpty(&stack1)) {
        TreeNode* node = pop(&stack1);
        push(&stack2, node);
        if (node->left != NULL) {
            push(&stack1, node->left);
        }
        if (node->right != NULL) {
            push(&stack1, node->right);
        }
    }
    while (!isStackEmpty(&stack2)) {
        TreeNode* node = pop(&stack2);
        printf("%d ", node->val);
    }
}

// 测试
int main() {
    // 构造二叉树
    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));
    node1->val = 1;
    node2->val = 2;
    node3->val = 3;
    node4->val = 4;
    node5->val = 5;
    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = NULL;
    node3->left = node5;
    node3->right = NULL;
    node4->left = NULL;
    node4->right = NULL;
    node5->left = NULL;
    node5->right = NULL;

    // 后序遍历
    postorderTraversal(node1);

    return 0;
}