用C语言编写一个不使用递归的中序遍历二叉树的程序

在C语言中，非递归地遍历二叉树通常采用栈的数据结构。以下是使用前序遍历的思想来实现中序遍历（左根右）的一个例子，因为中序遍历的过程是先遍历左子树，然后访问根节点，最后遍历右子树：

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

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

// 助手函数：将当前节点压入栈中
void push(TreeNode* node, stack_type* s) {
    if (node != NULL) {
        s->top = (TreeNode*)malloc(sizeof(TreeNode));
        s->top->val = node->val;
        s->top->left = NULL;
        s->top->right = NULL;
        s->size++;
        push(node->left, s);
        push(node->right, s);
    }
}

// 中序遍历辅助函数：弹出栈顶元素并访问，然后遍历右子树
void inOrderTraversal(TreeNode* root, stack_type* s) {
    while (root || s->top != NULL) {
        // 先处理左子树
        while (root) {
            push(root, s);
            root = root->left;
        }

        // 当左子树为空时，访问栈顶元素
        root = s->top;
        printf("%d ", root->val); // 访问节点值
        s->top = s->top->right; // 移动到右子树

        // 清空已经访问过的左子树
        while (s->top && s->top->val == root->val) {
            printf("%d ", s->top->val); // 再次访问同层节点，直到遇到下一个不同的节点
            s->top = s->top->right;
        }
    }
}

// 主函数
int main() {
    // 初始化你的二叉树...
    TreeNode* root = ...;

    stack_type s;
    s.top = NULL;
    s.size = 0;
    inOrderTraversal(root, &s);

    return 0;
}