用c语言编写一个非递归的中序遍历二叉树算法

在C语言中，非递归的中序遍历二叉树通常会采用栈的数据结构来辅助实现。下面是一个简单的示例：

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

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

// 助手函数，用于将当前节点压入栈
void pushIntoStack(TreeNode* root, StackNode** stack) {
    if (root == NULL) return;
    push(*stack, root);
    pushIntoStack(root->left, stack);
    pushIntoStack(root->right, stack);
}

// 助手函数，弹出栈顶元素并访问它
TreeNode* popAndVisit(StackNode** stack) {
    if (*stack->top == NULL) return NULL;
    TreeNode* node = (*stack)->top->data;
    (*stack)->top = (*stack)->top->next;
    return node;
}

// 中序遍历非递归版本
void inorderTraversalNonRecursive(TreeNode* root) {
    StackNode* stack = createStack(); // 初始化空栈
    TreeNode* current = root;
    
    while (current != NULL || !isEmpty(stack)) {
        while (current != NULL) {
            pushIntoStack(current, &stack);
            current = current->left;
        }
        
        current = popAndVisit(&stack); // 访问栈顶节点
        printf("%d ", current->val); // 输出节点值
        current = current->right; // 移动到右子树
    }

    destroyStack(stack); // 释放栈内存
}

int main() {
    // 创建二叉树并初始化...
    TreeNode* root = ...;
    inorderTraversalNonRecursive(root);
    return 0;
}

在这个例子中，我们首先创建一个栈，并将根节点及其所有左子节点压入栈。然后进入一个循环，只要栈不为空或者当前节点还有未访问的右子节点，就从栈顶取出一个节点访问，再将其右子节点压入栈。如此反复直到遍历完整棵树。