1）、以链表为存储结构创建二叉树； （2）、分别用递归和非递归方式实现二叉树的中序遍历； c语言 大写字母

一、以链表为存储结构创建二叉树：

在链表的基础上构建二叉树，通常会采用类似于“左根右”或“前序遍历”的模式，即根节点作为链表的第一个元素，其左孩子是链表的第二个元素，右孩子是第三个元素，以此类推。每个节点包含一个指向其左孩子的指针和一个指向其右孩子的指针，对于空节点，这两个指针通常是NULL。

例如，如果有一个已排序的链表，我们可以这样建立二叉搜索树：

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

// 创建函数
struct TreeNode* buildTreeFromList(struct ListNode* list) {
    if (!list) return NULL;
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = list->data;
    root->left = buildTreeFromList(list->next);
    root->right = buildTreeFromList(list->next->next); // 如果链表还有剩余，继续处理
    return root;
}

这里假设链表的每个节点都有一个整数值，并且链表本身已经按照升序排列。

二、二叉树的中序遍历：

1. **递归方式**：
中序遍历的顺序是先左子树，然后根节点，最后右子树。递归版代码如下：

   void inorderTraversal(struct TreeNode* root) {
       if (root == NULL) return;
       inorderTraversal(root->left);
       printf("%d ", root->val); // 输出节点值
       inorderTraversal(root->right);
   }

2. **非递归方式**（使用栈）：
非递归版本通常通过栈来辅助完成。首先将根节点压入栈，然后循环进行以下操作直到栈为空：
- 弹出栈顶节点，访问该节点
- 将右子节点（未访问）压入栈
- 将左子节点（未访问）压入栈

   void inorderTraversalNonRecursive(struct TreeNode* root) {
       struct TreeNode* stack[100];
       int top = 0;
       while (root || top != 0) {
           while (root) {
               stack[top++] = root;
               root = root->left;
           }
           root = stack[--top]; // 取出栈顶元素
           printf("%d ", root->val);
           root = root->right;
       }
   }

这里假设数组大小足够大，能容纳整个二叉树的所有节点。