利用C语言编写先序序列建立二叉树，并输出先序、中序和后序序列（递归程序+先序非递归程序）

以下是利用C语言编写的先序序列建立二叉树的递归程序，并输出先序、中序和后序序列：

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

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

// 先序序列建立二叉树
TreeNode *createTree() {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        return NULL;
    }
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->data = ch;
    root->left = createTree();
    root->right = createTree();
    return root;
}

// 先序遍历
void preOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

// 中序遍历
void inOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    printf("%c ", root->data);
    inOrder(root->right);
}

// 后序遍历
void postOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%c ", root->data);
}

// 先序遍历非递归程序
void preOrderNonRecursive(TreeNode *root) {
    TreeNode *stack[100];
    int top = -1;
    stack[++top] = root;
    while (top >= 0) {
        TreeNode *node = stack[top--];
        printf("%c ", node->data);
        if (node->right != NULL) {
            stack[++top] = node->right;
        }
        if (node->left != NULL) {
            stack[++top] = node->left;
        }
    }
}

int main() {
    printf("请输入先序序列（以 # 表示空节点）：\n");
    TreeNode *root = createTree();
    printf("先序遍历结果为：");
    preOrder(root);
    printf("\n中序遍历结果为：");
    inOrder(root);
    printf("\n后序遍历结果为：");
    postOrder(root);
    printf("\n先序遍历非递归程序结果为：");
    preOrderNonRecursive(root);
    printf("\n");
    return 0;
}

示例输入：

请输入先序序列（以 # 表示空节点）：
AB#C##DE#G##

示例输出：

先序遍历结果为：A B C D E G 
中序遍历结果为：B A C # D # E # G 
后序遍历结果为：B C # D # G E A 
先序遍历非递归程序结果为：A B C D E G