用栈实现二叉树中序遍历的非递归程序 c语言

二叉树的中序遍历可以用栈来实现非递归程序，具体实现步骤如下：

1. 创建一个栈，并将根节点入栈。

2. 当栈不为空时，执行以下操作：

a. 取出栈顶元素，如果该元素有左子树，则将左子树入栈。

b. 如果该元素没有左子树或者左子树已经遍历完了，则输出该元素的值，并将右子树入栈。

3. 当所有节点都被遍历完了，中序遍历结束。

下面是该算法的C语言实现代码：

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

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

// 栈的结构体定义
typedef struct StackNode {
    struct TreeNode* node;
    struct StackNode* next;
} StackNode;

// 创建一个空栈
StackNode* createStack()
{
    return NULL;
}

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

// 元素入栈
void push(StackNode** top, TreeNode* node)
{
    StackNode* new_node = (StackNode*)malloc(sizeof(StackNode));
    new_node->node = node;
    new_node->next = *top;
    *top = new_node;
}

// 元素出栈
TreeNode* pop(StackNode** top)
{
    if (isEmpty(*top)) {
        return NULL;
    }
    TreeNode* res = (*top)->node;
    StackNode* temp = *top;
    *top = (*top)->next;
    free(temp);
    return res;
}

// 中序遍历二叉树的非递归实现
void inorderTraversal(TreeNode* root)
{
    if (root == NULL) {
        return;
    }
    StackNode* stack = createStack();
    while (root != NULL || !isEmpty(stack)) {
        while (root != NULL) {
            push(&stack, root);
            root = root->left;
        }
        root = pop(&stack);
        printf("%d ", root->val);
        root = root->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);

    return 0;
}

这段代码中，我们定义了一个`StackNode`结构体表示栈中的节点，该结构体包含一个指向二叉树节点的指针`node`和一个指向下一个节点的指针`next`。我们还定义了一个`createStack()`函数用来创建一个空栈，一个`isEmpty()`函数判断栈是否为空，一个`push()`函数将元素入栈，一个`pop()`函数将元素出栈。最后，我们定义了一个`inorderTraversal()`函数用来实现中序遍历二叉树的非递归程序。