用c语言实现二叉树的非递归算法

二叉树的非递归算法通常使用栈来实现。具体实现可以参考以下代码：

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

// 定义树的结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 定义栈的结构体
typedef struct Stack {
    int top;
    int capacity;
    TreeNode **arr;
} Stack;

// 初始化栈
Stack *initStack(int capacity) {
    Stack *stack = (Stack *)malloc(sizeof(Stack));
    stack->top = -1;
    stack->capacity = capacity;
    stack->arr = (TreeNode **)malloc(sizeof(TreeNode *) * capacity);
    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 *node) {
    if (isFull(stack)) {
        printf("Stack is full.\n");
        return;
    }
    stack->arr[++stack->top] = node;
}

// 出栈
TreeNode *pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty.\n");
        return NULL;
    }
    return stack->arr[stack->top--];
}

// 获取栈顶元素
TreeNode *top(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty.\n");
        return NULL;
    }
    return stack->arr[stack->top];
}

// 创建新节点
TreeNode *newNode(int val) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 构建二叉树
TreeNode *buildTree() {
    TreeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    return root;
}

// 非递归前序遍历
void preorderTraversal(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);
        }
    }
    printf("\n");
}

// 非递归中序遍历
void inorderTraversal(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;
    }
    printf("\n");
}

// 非递归后序遍历
void postorderTraversal(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);
    }
    printf("\n");
}

int main() {
    TreeNode *root = buildTree();
    printf("Preorder traversal: ");
    preorderTraversal(root);
    printf("Inorder traversal: ");
    inorderTraversal(root);
    printf("Postorder traversal: ");
    postorderTraversal(root);
    return 0;
}

这里实现了二叉树的非递归前序、中序和后序遍历算法。其中，非递归中序遍历需要用到两个栈，而非递归后序遍历需要用到两个栈，其中一个栈用于辅助遍历，另一个栈用于存储遍历结果。