：输入字符序列，建立二叉树；按先序、中序、后序遍历二叉树（三种递归算法和中序遍历的非递归算法）的c语言代码

以下是C语言代码实现：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树结构体
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;

// 递归建立二叉树
TreeNode* buildTree(char* preorder, char* inorder, int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) {
if (preorderLeft > preorderRight) return NULL;

// 找到根节点在中序遍历中的位置
int inorderRoot = inorderLeft;
while (inorder[inorderRoot] != preorder[preorderLeft]) inorderRoot++;

// 创建当前子树根节点并分别递归构造左右子树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preorder[preorderLeft];
root->left = buildTree(preorder, inorder, preorderLeft + 1, preorderLeft + inorderRoot - inorderLeft, inorderLeft, inorderRoot - 1);
root->right = buildTree(preorder, inorder, preorderLeft + inorderRoot - inorderLeft + 1, preorderRight, inorderRoot + 1, inorderRight);

return root;
}

// 先序遍历（递归）
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;

printf("%c ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}

// 中序遍历（递归）
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;

inorderTraversal(root->left);
printf("%c ", root->val);
inorderTraversal(root->right);
}

// 后序遍历（递归）
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;

postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c ", root->val);
}

// 中序遍历（非递归）
void inorderTraversalNonRecursion(TreeNode* root) {
TreeNode* stack[100]; // 定义一个栈
int top = -1; // 栈顶指针
TreeNode* p = root;
while (p != NULL || top != -1) {
while (p != NULL) {
stack[++top] = p;
p = p->left;
}
if (top != -1) {
p = stack[top--];
printf("%c ", p->val);
p = p->right;
}
}
}

int main() {
char preorder[] = {'A', 'B', 'D', 'E', 'C', 'F', 'G'};
char inorder[] = {'D', 'B', 'E', 'A', 'F', 'C', 'G'};
int length = sizeof(preorder) / sizeof(char);

// 建立二叉树
TreeNode* root = buildTree(preorder, inorder, 0, length - 1, 0, length - 1);

// 先序遍历
printf("Preorder Traversal: ");
preorderTraversal(root);
printf("\n");

// 中序遍历
printf("Inorder Traversal: ");
inorderTraversal(root);
printf("\n");

// 后序遍历
printf("Postorder Traversal: ");
postorderTraversal(root);
printf("\n");

// 中序遍历（非递归）
printf("Inorder Traversal (Non-Recursion): ");
inorderTraversalNonRecursion(root);
printf("\n");

return 0;
}