非递归C语言实现二叉树遍历：先序、中序、后序

"二叉树的建立和非递归遍历是数据结构中的重要概念，本文将探讨如何在C语言中实现非递归版本的先序、中序和后序遍历。" 在计算机科学中，二叉树是一种常用的数据结构，它由节点组成，每个节点有两个子节点：左子节点和右子节点。为了操作和分析二叉树，我们需要对其进行遍历，即按照特定顺序访问每个节点。常见的遍历方法有先序遍历、中序遍历和后序遍历。 先序遍历的顺序是：根节点 -> 左子树 -> 右子树。 中序遍历的顺序是：左子树 -> 根节点 -> 右子树。 后序遍历的顺序是：左子树 -> 右子树 -> 根节点。 在递归方式下，这三种遍历很容易实现。然而，非递归遍历通常需要借助栈来辅助完成。在给定的代码中，定义了一个`TreeNode`结构体表示二叉树节点，以及一个`MyStack`结构体来实现自定义的栈。`MyStack`包含一个大小为100的数组来存储节点，以及一个`top`指针来追踪栈顶。 首先，`initTreeNode`函数用于初始化一个二叉树节点，接收值、左子节点和右子节点作为参数。然后，`initMyStack`函数用于初始化栈，设置`top`为0。 `push`函数用于将节点入栈，`isEmpty`函数检查栈是否为空，`pop`函数出栈并返回栈顶元素，`top`函数返回栈顶元素但不移除。 非递归遍历的核心在于控制栈的状态来模拟递归过程。对于先序遍历，我们首先将根节点入栈，然后在循环中处理以下情况： 1. 当当前节点不为空时，打印其数据，并将当前节点入栈，然后转到其左子节点。 2. 如果栈不空且当前节点为空，说明我们已经遍历完当前节点的所有子节点，需要回溯到父节点。此时，我们出栈并更新当前节点为父节点，然后检查当前节点的右子节点，如果存在则转到其左子节点。 同样的逻辑也适用于中序和后序遍历，只是处理节点的顺序不同。在中序遍历中，我们先遍历左子树，然后处理根节点，最后处理右子树；在后序遍历中，我们先遍历左右子树，然后处理根节点。 通过这样的非递归方法，我们可以避免递归带来的调用栈过深的问题，尤其对于深度较大的二叉树，非递归遍历可能会更有效率。同时，这种方式也让代码逻辑更加清晰，因为不需要处理递归的嵌套。