内容：掌握建立二叉树的方法，实现先序、中序、后序三种遍历的递归算法和非递归算法。 题目：二叉树的遍历 使用C语言

在C语言中，二叉树的遍历主要是对每个节点及其左右子树进行访问。有三种常见的遍历方式：先序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）。以下是递归和非递归算法的实现：

**递归实现：**
1. **先序遍历(递归)：**

void preorder(struct TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->val); // 访问根节点
        preorder(root->left);     // 递归遍历左子树
        preorder(root->right);    // 递归遍历右子树
    }
}

2. **中序遍历(递归)：**

void inorder(struct TreeNode* root) {
    if (root != NULL) {
        inorder(root->left);   // 递归遍历左子树
        printf("%d ", root->val); // 访问根节点
        inorder(root->right);  // 递归遍历右子树
    }
}

3. **后序遍历(递归)：**

void postorder(struct TreeNode* root) {
    if (root != NULL) {
        postorder(root->left);   // 递归遍历左子树
        postorder(root->right);  // 递归遍历右子树
        printf("%d ", root->val); // 访问根节点
    }
}

**非递归实现（栈）：**
对于上述的中序和后序遍历，可以使用栈数据结构来实现非递归版本，这里仅提供中序遍历的例子，后序遍历类似：

struct TreeNode* lastVisited = NULL; // 初始化最后一个访问的节点

void inorderNonRecursive(struct TreeNode* root) {
    stack struct TreeNode* s;
    s = malloc(sizeof(stack struct TreeNode));

    while (root || !s->top) {
        while (root) {
            push(s, root);
            root = root->left;
        }
        root = pop(s);
        printf("%d ", root->val);
        root = root->right;
    }

    free(s);
}