用C语言编写并实现一个完整的非递归中序遍历二叉树程序

在C语言中，我们可以通过迭代而不是递归来实现二叉树的中序遍历。这里有一个使用栈的数据结构来辅助完成非递归遍历的例子：

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

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

// 助手函数，用于检查左右子节点是否存在
int hasLeftChild(TreeNode* node) {
    return node->left != NULL;
}

int hasRightChild(TreeNode* node) {
    return node->right != NULL;
}

// 递归版的中序遍历（辅助理解）
void inorderTraversal(TreeNode* root) {
    if (root) {
        inorderTraversal(root->left);
        printf("%d ", root->val);
        inorderTraversal(root->right);
    }
}

// 非递归版本的中序遍历
void iterativeInorderTraversal(TreeNode* root) {
    if (!root) {
        return;
    }

    // 创建一个栈，初始入栈根节点
    Stack<TreeNode*> stack;
    stack.push(root);

    while (!stack.isEmpty()) {
        // 弹出栈顶元素，访问其值
        TreeNode* current = stack.pop();
        printf("%d ", current->val);

        // 如果当前节点有右子节点，先将其左子节点入栈
        if (hasLeftChild(current)) {
            stack.push(current->left);
        }

        // 如果当前节点无右子节点但还有左子节点，继续向左子树推进
        else if (hasLeftChild(stack.top())) {
            current = stack.top();
            stack.pop();
            stack.push(current->left);
        }
    }
}

int main() {
    // 初始化你的二叉树...
    // ...

    iterativeInorderTraversal(root);  // 调用非递归遍历

    return 0;
}

在这个代码片段中，我们首先检查当前节点是否有左孩子，如果有就将其压入栈；如果没有，就从栈中弹出节点，访问其值，然后检查栈顶是否有右子节点，如果有则继续往左子节点推进。这样就可以保证中序遍历的顺序：左子树 -> 根节点 -> 右子树。