河南大学：非递归中序遍历迭代算法详解及栈的应用

在河南大学计算机与信息工程学院的数据结构课程中，关于中序遍历的非递归（迭代）算法是教学的重点内容之一。这一算法的目标是实现对二叉树的遍历，遵循中序遍历的顺序，即先遍历左子树，然后访问根节点，最后遍历右子树。算法的核心在于利用堆栈来模拟递归过程，因为非递归情况下需要手动控制遍历顺序。 算法的详细步骤如下： 1. 初始化一个堆栈 `S`，并将根节点 `T` 入栈。 2. 当堆栈不为空时，执行循环： - 进行一个子树遍历阶段，不断将左子节点压入堆栈，直到遇到空节点或者到达最左侧。 - 从堆栈弹出当前节点 `p`，如果堆栈不为空，说明还有未访问的节点，进行节点访问： - 检查 `p->data` 是否需要访问，如果需要，调用函数 `Visit` 处理该节点。 - 如果访问成功，将右子节点 `p->rchild` 压入堆栈，以便后续遍历右子树。 3. 当堆栈为空时，表示已经遍历完整棵树，返回 `OK` 表示成功。 这种方法避免了递归调用带来的额外开销，通过循环和堆栈操作实现了对二叉树的中序遍历。在教学过程中，可能还会引用严蔚敏等编著的《数据结构》（C语言版）作为主要教材，让学生理解并掌握这种非递归遍历方法。同时，课程会强调数据结构在解决非数值计算问题中的重要性，以及它在软件开发中的应用，比如在查找、排序、树和二叉树操作等场景中。 此外，课程还推荐了几本参考书供学生深入学习和练习，如《数据结构（用面向对象方法与C++）》、《数据结构习题解析》等，这些书籍不仅提供了理论知识，还包含丰富的习题和案例分析，有助于巩固和拓展所学内容。通过这样的教学方式，学生能够全面理解数据结构的概念、术语，以及如何在实际编程中灵活运用不同遍历算法。