用C语言建立一棵二叉树，并用递归或非递归的算法分别用先序、中序和后序遍历之。实验要求：(1) 应用先序遍历法建立任意一棵二叉树；(2) 实现二叉树先序、中序、后序遍历的递归算法；(3) 选择一种遍历方法实现其非递归算法（选做）；

在C语言中建立一棵二叉树并进行遍历，首先需要定义二叉树节点结构以及相应的创建函数。这里是一个简单的二叉树节点定义： ```c typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right; } TreeNode; ``` **应用先序遍历法建立任意棵二叉树** (递归实现) 先序遍历顺序是：根 -> 左 -> 右。我们可以这样构建树： ```c TreeNode* buildTreePreorder(int arr[], int start, int end) { if (start > end) return NULL; // 树为空，返回NULL TreeNode* root = malloc(sizeof(TreeNode)); root->val = arr[start]; root->left = buildTreePreorder(arr, start + 1, end); root->right = buildTreePreorder(arr, start + 2, end); // 假设数组元素是从0开始计数 return root; } ``` **二叉树的三种遍历算法** (递归实现) 1. **先序遍历** (根 -> 左 -> 右) ```c void preorderTraversal(TreeNode* root) { if (root != NULL) { printf("%d ", root->val); preorderTraversal(root->left); preorderTraversal(root->right); } } ``` 2. **中序遍历** (左 -> 根 -> 右) ```c void inorderTraversal(TreeNode* root) { if (root != NULL) { inorderTraversal(root->left); printf("%d ", root->val); inorderTraversal(root->right); } } ``` 3. **后序遍历** (左 -> 右 -> 根) ```c void postorderTraversal(TreeNode* root) { if (root != NULL) { postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ", root->val); } } ``` **非递归实现** (选做部分，通常通过栈来辅助完成) 你可以使用栈数据结构来实现非递归遍历，例如对前序遍历的非递归版本： ```c // 非递归先序遍历 void nonRecursivePreorder(TreeNode* root, Stack* stack) { if (!stack.isEmpty() && root == stack.peek()) { // 如果栈顶元素为当前节点，弹出并访问 TreeNode* node = stack.pop(); printf("%d ", node->val); if (node->right) stack.push(node->right); // 先右子树 if (node->left) stack.push(node->left); // 再左子树 } else if (root->left) { // 否则将左子树入栈 stack.push(root); root = root->left; } else if (root->right) { // 同理处理右子树 stack.push(root); root = root->right; } else { // 当左右子树都访问完，跳出循环 return; } } ```