输入字符序列,建立二叉树;按先序、中序、后序遍历二叉树(非递归各实现一次)c语言程序

以下是建立二叉树并进行先序、中序、后序遍历的 C 语言程序：

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

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

// 递归建立二叉树
struct TreeNode* createTree() {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        return NULL;
    }
    struct TreeNode *node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = ch;
    node->left = createTree();
    node->right = createTree();
    return node;
}

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

// 非递归中序遍历
void inOrder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    struct TreeNode *stack[100];
    int top = -1;
    struct TreeNode *p = root;
    while (top >= 0 || p != NULL) {
        while (p != NULL) {
            stack[++top] = p;
            p = p->left;
        }
        if (top >= 0) {
            struct TreeNode *node = stack[top--];
            printf("%c ", node->val);
            p = node->right;
        }
    }
    printf("\n");
}

// 非递归后序遍历
void postOrder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    struct TreeNode *stack[100];
    int top = -1;
    struct TreeNode *p = root;
    struct TreeNode *r = NULL;
    while (top >= 0 || p != NULL) {
        while (p != NULL) {
            stack[++top] = p;
            p = p->left;
        }
        struct TreeNode *node = stack[top];
        if (node->right == NULL || node->right == r) {
            printf("%c ", node->val);
            top--;
            r = node;
        } else {
            p = node->right;
        }
    }
    printf("\n");
}

int main() {
    printf("请输入字符序列，以 '#' 表示空节点:\n");
    struct TreeNode *root = createTree();
    printf("先序遍历结果：");
    preOrder(root);
    printf("中序遍历结果：");
    inOrder(root);
    printf("后序遍历结果：");
    postOrder(root);
    return 0;
}

输入示例：AB#C##D##
输出示例：
先序遍历结果：A B C D
中序遍历结果：B A C D
后序遍历结果：B D C A