c语言二叉树的中序遍历(非递归)

使用非递归方式实现C语言中二叉树的中序遍历可以借助栈的数据结构。以下是一个简单的实现示例：

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

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

// 栈结构
struct StackNode {
    struct TreeNode* treeNode;
    struct StackNode* next;
};

// 创建栈节点
struct StackNode* createStackNode(struct TreeNode* treeNode) {
    struct StackNode* newNode = (struct StackNode*)malloc(sizeof(struct StackNode));
    newNode->treeNode = treeNode;
    newNode->next = NULL;
    return newNode;
}

// 判断栈是否为空
int isStackEmpty(struct StackNode* top) {
    return top == NULL;
}

// 入栈操作
void push(struct StackNode** top, struct TreeNode* treeNode) {
    struct StackNode* newNode = createStackNode(treeNode);
    newNode->next = *top;
    *top = newNode;
}

// 出栈操作
struct TreeNode* pop(struct StackNode** top) {
    if (isStackEmpty(*top)) {
        return NULL;
    }

    struct StackNode* temp = *top;
    *top = (*top)->next;
    struct TreeNode* poppedNode = temp->treeNode;
    free(temp);
    return poppedNode;
}

// 中序遍历（非递归）
void inOrderTraversal(struct TreeNode* root) {
    struct TreeNode* current = root;
    struct StackNode* stack = NULL;

    while (current != NULL || !isStackEmpty(stack)) {
        while (current != NULL) {
            push(&stack, current);
            current = current->left;
        }

        current = pop(&stack);
        printf("%d ", current->data);

        current = current->right;
    }
}

// 创建一个测试用的二叉树
struct TreeNode* createSampleTree() {
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->data = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->data = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->data = 3;
    root->right->left = NULL;
    root->right->right = NULL;

    return root;
}

// 主函数
int main() {
    struct TreeNode* root = createSampleTree();

    printf("中序遍历结果: ");
    inOrderTraversal(root);

    return 0;
}

此示例包含了一个简单的二叉树结构和一个基本的非递归中序遍历实现。