二叉树遍历：递归与非递归实现

本文档提供了一种创建和遍历二叉树的方法，包括递归和非递归方式。其中，二叉树的节点结构由`typedefstructNode`定义，包括字符数据、左子节点和右子节点。创建二叉树的函数`CreateBiTree`通过用户输入构建树结构。此外，提供了四种遍历方法：前序遍历（PreOrder）、中序遍历（InOrder）、后序遍历（PostOrder，注释掉未执行）以及一个非递归的前序遍历实现（PreOrde1）。 在二叉树的遍历中，遍历顺序对结果有着显著影响，以下是每种遍历方式的详细说明： 1. **前序遍历（PreOrder）**： - 访问根节点。 - 遍历左子树。 - 遍历右子树。 函数`PreOrder`实现了递归的前序遍历。首先打印根节点的数据，然后分别对左右子树进行前序遍历。 2. **中序遍历（InOrder）**： - 遍历左子树。 - 访问根节点。 - 遍历右子树。 函数`InOrder`同样采用递归方式，先中序遍历左子树，然后打印根节点数据，最后中序遍历右子树。 3. **后序遍历（PostOrder）**： - 遍历左子树。 - 遍历右子树。 - 访问根节点。 函数`PostOrder`（注释掉，未执行）会递归地遍历左右子树，最后访问根节点。虽然在此代码中没有执行，但通常后序遍历在非递归实现时会用到栈来辅助操作。 4. **非递归前序遍历（PreOrde1）**： - 使用栈辅助，确保在遍历过程中正确访问节点。 - 当节点不为空时，将其压入栈并访问，然后遍历左子节点。 - 如果当前节点为空且栈不空，弹出栈顶元素作为新的当前节点，并检查其右子节点是否为空。如果为空，继续弹出栈顶元素；如果不为空，将右子节点设为当前节点并压入栈。 函数`PreOrde1`实现了一个非递归的前序遍历，它依赖于一个辅助栈`S`。首先初始化栈，然后设置指针`p`指向根节点。在循环中，当节点不为空时，将节点压入栈并打印数据，然后访问左子节点。如果节点为空但栈不空，说明需要处理右子节点或返回上一层。此时，弹出栈顶元素，检查其右子节点是否为空，根据情况决定下一步操作。 这些遍历方法在不同的场景下有着不同的应用。例如，前序遍历常用于复制二叉树，中序遍历常用于二分搜索树中查找排序序列，后序遍历则适用于计算表达式树的值。非递归遍历方法在处理大量数据时可以避免深度过大的调用栈，提高效率。