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

前言

在二叉树的数据结构中，后序遍历是指先遍历左子树，再遍历右子树，最后访问根节点。非递归后序遍历二叉树是一种迭代的方式，通过使用栈来模拟递归过程，将左子树和右子树的节点先入栈，然后进行处理。在本文中，我们将使用C语言实现非递归后序遍历二叉树的算法。

算法实现

#include 
#include 

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败");
        exit(1);
    }
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void push(struct TreeNode** stack, int* top, struct TreeNode* node) {
    (*top)++;
    stack[*top] = node;
}

struct TreeNode* pop(struct TreeNode** stack, int* top) {
    struct TreeNode* node = stack[*top];
    (*top)--;
    return node;
}

void postorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    
    struct TreeNode** stack = (struct TreeNode**)malloc(1000 * sizeof(struct TreeNode*));
    int top = -1;
    struct TreeNode* prev = NULL;
    
    do {
        while (root != NULL) {
            push(stack, &top, root);
            root = root->left;
        }
        
        struct TreeNode* node = stack[top];
        
        if (node->right == NULL || node->right == prev) {
            printf("%d ", node->val);
            prev = node;
            pop(stack, &top);
        } else {
            root = node->right;
        }
        
    } while (top >= 0);
    
    free(stack);
}

代码解释

代码中定义了一个二叉树的节点结构体TreeNode，并且使用指针left和right分别指向左子节点和右子节点。在createNode函数中，我们分配了一个新的节点，并初始化其值和左右指针。push函数和pop函数分别用于将节点压入栈或从栈中弹出。postorderTraversal函数实现了非递归后序遍历，通过迭代的方式遍历二叉树的所有节点。

在主函数中，我们可以创建一个二叉树并调用postorderTraversal函数来进行后序遍历。

总结

通过使用栈来模拟递归过程，我们可以实现非递归后序遍历二叉树的算法。这种算法的时间复杂度为O(n)，其中n是二叉树节点的数量。由于采用了迭代的方式，我们可以避免使用递归的额外空间，使得算法更加高效。