c语言实现二叉树非递归中序遍历算法

二叉树的中序遍历可以通过非递归的方式实现，常用的方法是利用栈。具体的实现方法如下：

1. 初始化一个栈，将根节点入栈。

2. 循环执行以下步骤，直到栈为空：

1. 将栈顶节点弹出，并将其右子节点（如果有）压入栈中。

2. 将当前节点压入栈中，并将其左子节点（如果有）置为当前节点。

3. 遍历完成。

下面是具体的代码实现：

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

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

// 栈节点结构体
typedef struct StackNode {
    TreeNode* node;
    struct StackNode* next;
} StackNode;

// 初始化栈
StackNode* initStack() {
    return NULL;
}

// 入栈
StackNode* push(StackNode* stack, TreeNode* node) {
    StackNode* new_node = (StackNode*)malloc(sizeof(StackNode));
    new_node->node = node;
    new_node->next = stack;
    return new_node;
}

// 出栈
StackNode* pop(StackNode* stack) {
    if (stack == NULL) {
        return NULL;
    }
    StackNode* top = stack;
    stack = stack->next;
    free(top);
    return stack;
}

// 获取栈顶节点
TreeNode* top(StackNode* stack) {
    if (stack == NULL) {
        return NULL;
    }
    return stack->node;
}

// 中序遍历二叉树（非递归）
void inorderTraversal(TreeNode* root) {
    StackNode* stack = initStack();  // 初始化栈
    TreeNode* cur = root;  // 当前节点
    while (stack != NULL || cur != NULL) {
        if (cur != NULL) {
            stack = push(stack, cur);  // 当前节点入栈
            cur = cur->left;  // 左子节点置为当前节点
        } else {
            cur = top(stack);  // 获取栈顶节点
            stack = pop(stack);  // 栈顶节点出栈
            printf("%d ", cur->val);  // 打印节点值
            cur = cur->right;  // 右子节点置为当前节点
        }
    }
}

int main() {
    // 构造二叉树
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = 1;
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->val = 3;
    root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->left->val = 4;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->right->val = 5;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    // 中序遍历二叉树
    inorderTraversal(root);
    printf("\n");

    return 0;
}

上述代码中，`push`、`pop` 和 `top` 操作均是常规的栈操作，不再赘述。在 `inorderTraversal` 函数中，每次循环都将当前节点的左子节点置为当前节点，并将当前节点入栈，直到当前节点为空。然后，取出栈顶节点，打印节点值，并将右子节点置为当前节点。循环执行这个过程，直到栈为空。