c语言实现二叉树的二叉链存储以及二叉树的前中后序遍历非递归完整代码

以下是C语言实现二叉树的二叉链存储以及二叉树的前中后序遍历非递归完整代码：

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

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

// 栈结构体
typedef struct Stack {
    TreeNode** data;
    int top;
    int size;
} Stack;

// 初始化栈
Stack* initStack(int size) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->data = (TreeNode**)malloc(sizeof(TreeNode*) * size);
    stack->top = -1;
    stack->size = size;
    return stack;
}

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

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

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

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

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

// 创建二叉树
TreeNode* createTree() {
    int val;
    scanf("%d", &val);
    if (val == -1) {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = val;
    root->left = createTree();
    root->right = createTree();
    return root;
}

// 前序遍历非递归
void preOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* stack = initStack(100);
    push(stack, root);
    while (!isEmpty(stack)) {
        TreeNode* node = pop(stack);
        printf("%d ", node->val);
        if (node->right != NULL) {
            push(stack, node->right);
        }
        if (node->left != NULL) {
            push(stack, node->left);
        }
    }
}

// 中序遍历非递归
void inOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* stack = initStack(100);
    TreeNode* node = root;
    while (node != NULL || !isEmpty(stack)) {
        while (node != NULL) {
            push(stack, node);
            node = node->left;
        }
        node = pop(stack);
        printf("%d ", node->val);
        node = node->right;
    }
}

// 后序遍历非递归
void postOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* stack1 = initStack(100);
    Stack* stack2 = initStack(100);
    push(stack1, root);
    while (!isEmpty(stack1)) {
        TreeNode* node = pop(stack1);
        push(stack2, node);
        if (node->left != NULL) {
            push(stack1, node->left);
        }
        if (node->right != NULL) {
            push(stack1, node->right);
        }
    }
    while (!isEmpty(stack2)) {
        TreeNode* node = pop(stack2);
        printf("%d ", node->val);
    }
}

int main() {
    TreeNode* root = createTree();
    printf("前序遍历结果：");
    preOrder(root);
    printf("\n中序遍历结果：");
    inOrder(root);
    printf("\n后序遍历结果：");
    postOrder(root);
    return 0;
}