C语言先序中序后序用递归非递归实现

在C语言中，树的遍历通常分为先序遍历（Preorder Traversal）、中序遍历（Inorder Traversal）和后序遍历（Postorder Traversal）。这里我们分别给出三种遍历方法的递归和非递归实现。

1. **递归实现**:

### 先序遍历（根-左-右）

// 递归函数
void preorder_traversal(struct TreeNode* node) {
    if (node != NULL) {
        printf("%d ", node->val); // 输出当前节点值
        preorder_traversal(node->left);  // 遍历左子树
        preorder_traversal(node->right);  // 遍历右子树
    }
}

### 中序遍历（左-根-右）

// 递归函数
void inorder_traversal(struct TreeNode* node) {
    if (node != NULL) {
        inorder_traversal(node->left);   // 遍历左子树
        printf("%d ", node->val);         // 输出当前节点值
        inorder_traversal(node->right);   // 遍历右子树
    }
}

### 后序遍历（左-右-根）

// 递归函数
void postorder_traversal(struct TreeNode* node) {
    if (node != NULL) {
        postorder_traversal(node->left);    // 遍历左子树
        postorder_traversal(node->right);    // 遍历右子树
        printf("%d ", node->val);           // 输出当前节点值
    }
}

2. **非递归实现**（利用栈数据结构）:

由于递归实现涉及大量的函数调用，对于大型树可能导致堆栈溢出。非递归版本使用栈来存储访问顺序：

// 声明必要的辅助结构体
typedef struct {
    struct TreeNode* node;
    int mode; // 0代表前序，1代表中序，2代表后序
} NodeStack;

void non_recursive_preorder(struct TreeNode* root) {
    stack<NodeStack> s;
    NodeStack curr = {root, 0};
    
    while (!s.empty() || curr.node) {
        while (curr.node) {
            printf("%d ", curr.node->val);
            s.push(curr);
            curr.node = curr.node->left;
        }

        curr = s.top();
        s.pop();

        curr.node = curr.mode == 0 ? curr.node->right : NULL;
    }
}

// 对于中序和后序，只需改变初始化时的mode即可

以上代码是非递归实现，适用于处理任意大小的树。