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

以下是输入字符序列建立二叉树、按先序、中序、后序遍历二叉树的非递归实现的 C 语言程序：

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

typedef struct TreeNode {
    char data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 栈结构
typedef struct Stack {
    int top;
    int capacity;
    TreeNode** array;
} Stack;

// 创建一个栈
Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->top = -1;
    stack->capacity = capacity;
    stack->array = (TreeNode**)malloc(capacity * sizeof(TreeNode*));
    return stack;
}

// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == -1;
}

// 判断栈是否已满
int isFull(Stack* stack) {
    return stack->top == stack->capacity - 1;
}

// 入栈
void push(Stack* stack, TreeNode* item) {
    if (isFull(stack)) {
        return;
    }
    stack->array[++stack->top] = item;
}

// 出栈
TreeNode* pop(Stack* stack) {
    if (isEmpty(stack)) {
        return NULL;
    }
    return stack->array[stack->top--];
}

// 获取栈顶元素
TreeNode* peek(Stack* stack) {
    if (isEmpty(stack)) {
        return NULL;
    }
    return stack->array[stack->top];
}

// 创建一个新的二叉树节点
TreeNode* createNode(char data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 根据输入的字符序列建立二叉树
TreeNode* buildTree(char* charSeq) {
    Stack* stack = createStack(MAX_SIZE);
    TreeNode* root = createNode(charSeq[0]);
    push(stack, root);
    int i = 1;
    while (i < strlen(charSeq)) {
        TreeNode* temp = NULL;
        while (!isEmpty(stack) && charSeq[i] > peek(stack)->data) {
            temp = pop(stack);
        }
        if (temp != NULL) {
            temp->right = createNode(charSeq[i]);
            push(stack, temp->right);
        } else {
            peek(stack)->left = createNode(charSeq[i]);
            push(stack, peek(stack)->left);
        }
        i++;
    }
    free(stack);
    return root;
}

// 先序遍历二叉树（非递归）
void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* stack = createStack(MAX_SIZE);
    push(stack, root);
    while (!isEmpty(stack)) {
        TreeNode* current = pop(stack);
        printf("%c ", current->data);
        if (current->right != NULL) {
            push(stack, current->right);
        }
        if (current->left != NULL) {
            push(stack, current->left);
        }
    }
    free(stack);
}

// 中序遍历二叉树（非递归）
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* stack = createStack(MAX_SIZE);
    TreeNode* current = root;
    while (!isEmpty(stack) || current != NULL) {
        while (current != NULL) {
            push(stack, current);
            current = current->left;
        }
        current = pop(stack);
        printf("%c ", current->data);
        current = current->right;
    }
    free(stack);
}

// 后序遍历二叉树（非递归）
void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* stack1 = createStack(MAX_SIZE);
    Stack* stack2 = createStack(MAX_SIZE);
    push(stack1, root);
    while (!isEmpty(stack1)) {
        TreeNode* current = pop(stack1);
        push(stack2, current);
        if (current->left != NULL) {
            push(stack1, current->left);
        }
        if (current->right != NULL) {
            push(stack1, current->right);
        }
    }
    while (!isEmpty(stack2)) {
        printf("%c ", pop(stack2)->data);
    }
    free(stack1);
    free(stack2);
}

int main() {
    char charSeq[MAX_SIZE];
    printf("输入字符序列（不超过 %d 个字符）：\n", MAX_SIZE);
    scanf("%s", charSeq);
    TreeNode* root = buildTree(charSeq);
    printf("先序遍历：");
    preorderTraversal(root);
    printf("\n中序遍历：");
    inorderTraversal(root);
    printf("\n后序遍历：");
    postorderTraversal(root);
    printf("\n");
    return 0;
}

程序中使用了栈结构来实现非递归遍历二叉树，先序遍历、中序遍历、后序遍历分别对应了 `preorderTraversal()`、`inorderTraversal()`、`postorderTraversal()` 三个函数。在 `buildTree()` 函数中，使用了先序遍历建立二叉树的方法。