数据结构-中序遍历算法详解

"中序遍历算法讲解，来自清华大学严蔚敏教授的数据结构课程。" 这篇内容涉及的是数据结构中的一个重要概念——中序遍历算法，这是在计算机科学中处理树形数据结构的一种常见方法。中序遍历通常用于二叉搜索树，其顺序是左子树-根节点-右子树。提供的代码片段展示了C语言实现中序遍历的基本框架。 首先，定义了一个名为`TREENODE`的结构体，包含一个字符型数据成员`data`，以及两个指向左右子节点的指针`lchild`和`rchild`。`root`是一个全局变量，用于保存树的根节点。 `creat_tree()`函数虽然未给出具体实现，但通常这个函数会用于创建一个树结构，可能是通过用户输入或者预定义的数据来构建。 `inorder`函数是中序遍历的核心，它采用递归方式遍历树。如果给定的节点`p`不为空，它首先递归地访问左子树，然后访问当前节点，最后访问右子树。这样的顺序保证了在遍历过程中，节点按照从小到大的顺序被访问，对于二叉搜索树来说，这就是排序的顺序。 数据结构是计算机科学的基础，它研究的是数据的逻辑组织和物理存储，以及如何高效地操作这些数据。在第一章绪论中，讨论了数据结构的重要性，强调了数据的逻辑结构和物理结构对算法选择和效率的影响。例如，电话号码查询系统、图书馆书目检索系统、教师资料档案管理系统和多叉路口交通灯管理等问题，都可以通过设计合适的数据结构和对应的算法来解决。 基本概念和术语包括数据（Data）、数据结构（Data Structure）、逻辑结构和物理结构等。逻辑结构关注数据之间的关系，如线性、树形、图形等，而物理结构则涉及数据在内存或磁盘上的实际存储方式。数据结构还定义了一组操作，这些操作可以对结构进行插入、删除、查找等操作，且保证操作后的结构仍然符合原有的逻辑结构。 此外，算法是解决问题的方法，它应该满足可行性、确定性、有穷性和拥有合理的输入输出等要求。算法的效率可以通过时间复杂度和空间复杂度来衡量，前者关注执行时间，后者关注存储需求。在数据结构和算法设计时，通常需要权衡这两者以达到最优性能。