用c语言实现二叉树的中序遍历和后序遍历的递归和非递归算法

在C语言中，我们可以使用递归和非递归的方式分别实现二叉树的中序遍历（左-根-右）和后序遍历（左-右-根）。这里我会给出递归和非递归版本的示例。

**递归实现：**

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

// 中序遍历（递归）
void inorderTraversalRec(TreeNode* root) {
    if (root != NULL) {
        inorderTraversalRec(root->left);
        printf("%d ", root->val); // 访问当前节点
        inorderTraversalRec(root->right);
    }
}

// 后序遍历（递归）
void postorderTraversalRec(TreeNode* root) {
    if (root != NULL) {
        postorderTraversalRec(root->left);
        postorderTraversalRec(root->right);
        printf("%d ", root->val); // 最后访问当前节点
    }
}

**非递归实现（栈辅助）：**

// 使用栈实现中序遍历（非递归）
void inorderTraversalNonRec(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* curr = root;
    
    while (curr != NULL || !s.empty()) {
        while (curr != NULL) {
            s.push(curr);
            curr = curr->left;
        }
        
        curr = s.top();
        s.pop();
        printf("%d ", curr->val);
        curr = curr->right;
    }
}

// 同理，使用栈实现后序遍历（非递归）
void postorderTraversalNonRec(TreeNode* root) {
    stack<TreeNode*> s1, s2;
    s1.push(root);
    
    while (!s1.empty()) {
        TreeNode* node = s1.top();
        s1.pop();
        
        s2.push(node);
        if (node->left) s1.push(node->left);
        if (node->right) s1.push(node->right);
    }
    
    while (!s2.empty()) {
        printf("%d ", s2.top()->val);
        s2.pop();
    }
}