c语言中非递归方式实现二叉树中序遍历

在C语言中，非递归方式实现二叉树的中序遍历通常通过使用栈来辅助完成。这是一种叫做迭代遍历的方法，也称为后序遍历法（因为先访问左节点，然后入栈，最后访问根节点）。以下是步骤：

定义一个指针cur来表示当前节点，初始化为根节点；
创建一个空栈stack；
当cur不为空时，执行以下操作：
a. 先将cur的左子节点压入栈中，直到cur变为NULL；
b. 将cur出栈，并访问它的值（打印或存储）；
c. 将cur更新为其右子节点。

下面是伪代码示例：
struct TreeNode* node; // 根节点指针
struct TreeNode* stack[100]; // 栈
int top = -1;

void inorderTraversal(struct TreeNode* root) {
if (root == NULL) return;

while (true) {
// 入栈所有左子节点
while (root != NULL) {
stack[++top] = root;
root = root->left;
}

// 如果栈不为空，就出栈并访问当前节点
if (top != -1) {
root = stack[top--];
// 访问节点值
visit(root);

// 跳到右子节点
root = root->right;
} else {
break; // 结束循环
}
}
}
登录后复制
在这个过程中，当遍历完所有左子节点后，栈顶就会只剩下一个未访问的节点，接着进入下一轮循环，直到栈为空。