下载文档原格式
中序遍历算法中序遍历是二叉树遍历的一种方式，它按照从左到右的顺序访问二叉树中的所有节点。
1. 什么是中序遍历中序遍历是一种深度优先搜索（DFS）的方法，它按照”左子树-根节点-右子树”的顺序访问二叉树中的节点。
对于任意一个节点，首先访问它的左子树，然后访问该节点本身，最后再访问它的右子树。
2. 中序遍历算法实现下面我们来看一种递归实现中序遍历算法的方式：def inorderTraversal(root):if root is None:return []result = []result.extend(inorderTraversal(root.left))result.append(root.val)result.extend(inorderTraversal(root.right))return result在这个算法中，我们使用了递归来实现对二叉树的中序遍历。
首先判断当前节点是否为空，如果为空则返回空列表。
否则，我们首先递归调用函数对左子树进行中序遍历，并将结果添加到结果列表中。
然后将当前节点的值添加到结果列表中。
最后再递归调用函数对右子树进行中序遍历，并将结果添加到结果列表中。
最终返回结果列表。
3. 中序遍历的应用中序遍历在二叉搜索树（BST）中有着重要的应用。
由于BST的特性，中序遍历的结果是一个有序的列表。
因此，我们可以利用中序遍历来对BST进行排序。
另外，中序遍历还可以用于验证一个二叉树是否为BST。
如果中序遍历结果是一个有序列表，则说明该二叉树是BST。
4. 非递归实现中序遍历算法除了递归实现外，我们还可以使用迭代的方式来实现中序遍历算法。
下面是一种非递归实现的方式：def inorderTraversal(root):if root is None:return []result = []stack = []while stack or root:if root:stack.append(root)root = root.leftelse:node = stack.pop()result.append(node.val)root = node.rightreturn result在这个算法中，我们使用了一个栈来模拟递归调用的过程。
栈的应用递归到非递归的转换张 铭 北京大学信息学院1内容提要递归函数调用原理 机械的递归转换 优化后的非递归函数 非递归的二叉树周游2张铭 北京大学信息学院递归函数示例void exmp(int n, int& f) { int u1, u2; if (n<2) f = n+1; else { exmp((int)(n/2), u1); exmp((int)(n/4), u2); f = u1*u2; } } 张铭3北京大学信息学院数学公式fu (n) ={n +1当n < 2时fu ( ⎣n / 2 ⎦)* fu ( ⎣n / 4 ⎦)n ≥ 2时}4张铭 北京大学信息学院函数调用及返回的步骤调用– 保存调用信息（参数，返回地址） – 分配数据区（局部变量） – 控制转移给被调函数的入口返回– 保存返回信息 – 释放数据区 – 控制转移到上级函数（主调用函数）5张铭 北京大学信息学院函数执行过程图解二叉树图解 Exmp(7,&f) f=u1*u2=4u1=f=2 u2=f=2 Exmp(3,&f) Exmp(1,&f) f=u1*u2=2u1=f=2 Exmp(1,&f)张铭u2=f=1 Exmp(0,&f)6北京大学信息学院用栈模拟递归调用过程后调用，先返回(LIFO），所以用栈rd=1: n=1 f=1 u1=? u2=? f=2 rd=2: n=0 f=? u1=? u2=? f=? rd=2: n=1 f=? u1=2 u2=1 rd=1: n=3 f=? u1=? u2=? f=2 u1=? u2=? rd=3: n=7 f=? u1=? u2=? u1=2 u2=2张铭7北京大学信息学院递归过程的模拟假设 void recfunc(p1, p2, p3，…，pk, pk+1, …, pm) 是一个递归函数void是无返回值型的函数，如果有返回值， 我们可以把返回值转换为一个引用型参数 其中参数p1, p2, p3，…，pk是值传递，参 数pk+1, …, pm是引用传递。
递归如何转换为⾮递归递归算法实际上是⼀种分⽽治之的⽅法，它把复杂问题分解为简单问题来求解。
递归的特点包括：递归过程简洁、易编、易懂；递归过程效率低、重复计算多。
考虑递归的执⾏效率低，可以尝试将递归过程转换为⾮递归过程。
本⽂就是来探讨怎么转换的。
将递归算法转换为⾮递归算法有两种⽅法，⼀种是直接求值（迭代/循环），不需要回溯；另⼀种是不能直接求值，需要回溯。
前者使⽤⼀些变量保存中间结果，称为直接转换法；后者使⽤栈保存中间结果，称为间接转换法，下⾯分别讨论这两种⽅法。
⼀、直接转换法直接转换法通常⽤来消除尾递归和单向递归，将递归结构⽤循环结构来替代。
1.单向递归简单的说是指递归的过程总是朝着⼀个⽅向进⾏，如果函数１调⽤了函数２,⽽函数２⼜调⽤了函数１,则这种情况不属于单向递归。
斐波那契数列（单向递归）的递归求解可转⽤⼀个迭代法实现。
斐波那契数列的递归求解：int Fib(int n) { if(n <= 1) return n; else return Fib(n - 1) + Fib(n - 2);}转换为迭代求解过程：int Fib(int n) { if(n <= 1) return n; int twoBack = 0; int oneBack = 1; int cur; for(int i = 2;i < = n; i++) { cur = twoBack + oneBack; twoBack = oneBack; oneBack = cur; } return cur;}2.尾递归是以递归调⽤结尾的函数，是单向递归的特例。
它的递归调⽤语句只有⼀个，⽽且是放在过程的最后。
当递归调⽤返回时，返回到上⼀层递归调⽤语句的下⼀语句，⽽这个位置正好是程序的结尾，因此递归⼯作栈中可以不保存返回地址；除了返回值和引⽤值外，其他参数和局部变量都不再需要，因此可以不⽤栈，直接采⽤循环写出⾮递归过程。
上机实验的目的、要求和评分标准一、实验目的上机实践是各位对本门课程所学知识的一种全面、综合的能力训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节，也是对课堂教学与实践教学效果的一种检验。
通常，实验题中的问题比平时的习题复杂得多，也更接近实际。
实验着眼于原理与应用的结合，使你们学会如何把书上学到的知识运用于解决实际问题的过程中去，培养从事软件开发设计工作所必需的基本技能；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。
平时的练习较偏重于如何编写功能单一的“小”算法，而实验题是软件设计的综合训练，包括问题分析（需求分析）、总体结构设计和用户界面设计（概要设计）、程序设计基本技能和技巧等，即一整套软件工程规范的训练和科学作风的培养。
此外，还有很重要的一点是：机器是比任何教师都严厉的主考者。
为了达到上述目的，本课程共安排了10个实验单元，各单元的训练重点在于基本的数据结构，而不强调面面俱到。
各实验单元与教科书的各章具有紧密的对应关系。
二、要求：⒈做好每一次上机前的准备以提高上机效率：①预先认真阅读相关实验内容，做到心中有明确的目的要求和任务，要有备而来，应该自己独立的思考和设计你的算法和程序，并争取在规定的时间内如期完成上机工作任务。
对于个别目前基础较差的同学，实在是没法完成任务的建议你先参考其他同学的算法，勤学好问，最终自己独立完成，以增强你的感性认识，强化你的实践基础，提高你的实践能力。
②按照实验内容规定的习题题目，事先在实验预习报告上编写好源程序及运行程序所需的典型数据，并经人工静态检查认为无误；手编程序应书写整齐，应在每个题目之间留出一定的空间，以备记录上机调试情况和运行结果等；对程序中自己有疑问的地方，应作出记号，以便上机时给以注意。
③将想要上机验证的问题草拟提纲；制定一个简捷的程序调试计划。
⒉上机时输入和调式自己所编写的程序。
对“出错信息”，应善于自己分析判断，并充分利用开发工具提供的错误信息和调试手段解决出现的问题，及时修改与完善算法、源程序，随时记录有价值的内容。
pta6-2 中序遍历的非递归算法
中序遍历的非递归算法可以使用栈来实现。
首先将根节点入栈，然后将左子树的所有节点入栈，直到到达最左边的叶子节点。
然后从栈中弹出一个节点，访问它，并将它的右子树入栈。
重复上述过程，直到栈为空。
具体步骤如下：
1. 初始化一个空栈。
2. 将根节点入栈。
3. 当栈非空时，重复以下步骤：
- 将栈顶节点弹出，并访问它。
- 如果该节点的右子树非空，将右子树入栈。
- 如果该节点的左子树非空，将左子树入栈。
以下是用Python实现中序遍历的非递归算法的示例代码：
```python
def inorderTraversal(root):
if not root:
return []
stack = []
result = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return result
```
这个算法的时间复杂度是O(n)，其中n是二叉树中节点的个数。
上海应用技术学院课程设计报告课程名称《数据结构课程设计》设计题目猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；院系计算机科学与信息工程专业计算机科学与技术班级姓名学号指导教师日期一.目的与要求1. 巩固和加深对常见数据结构的理解和掌握2. 掌握基于数据结构进行算法设计的基本方法3. 掌握用高级语言实现算法的基本技能4. 掌握书写程序设计说明文档的能力5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力表。
3、输出功能：void print(LinkList *head);通过一个while的循环控制语句，在指针p!=NULL时，完成全部学生记录的显示。
知道不满足循环语句，程序再次回到菜单选择功能界面。
4、删除功能：LinkList *Delete(LinkList *head);按想要删除的学生的学号首先进行查找，通过指针所指向结点的下移来完成，如果找到该记录，则完成前后结点的连接，同时对以查找到的结点进行空间的释放，最后完成对某个学生记录进行删除，并重新存储。
5、插入功能：LinkList *Insert(LinkList *head)；输入你想插入的位置，通过指针所指向结点的下移，找到该位置，将该新的学生记录插入到该结点，并对该结点后面的指针下移。
链表长度加一，重新存储。
(5) 程序的输入与输出描述输入：调用LinkList *create()函数，输入学生的姓名、学号、三门功课的成绩；输出：调用void print(LinkList *head)函数，输出学生的记录。
(6) 程序测试主菜单：成绩管理系统的主界面：学生成绩记录的输入：输出学生成绩记录：学生成绩记录的删除（删除学号是1101的学生记录）插入新的学生成绩记录（插入学号为1103的学生记录）(7) 尚未解决的问题或改进方向尚未解决的问题：该成绩管理系统还存在不少缺陷，而且它提供的功能也是有限的，只能实现学生成绩的输入、输出、删除、插入。
诚信应考 考出水平 考出风格浙江大学城市学院2010 — 2011 学年第一学期期末考试试卷《 数据结构基础 》开课单位：计算学院 ；考试形式：闭卷；考试时间：_2011_年__1__月__16__日； 所需时间： 120 分钟 题序 一 二 三 四 五 六 七 八 总 分 得分 评卷人注：答案请写在答卷上，写在试卷上无效。
一．单项选择题 (本大题共_20_题，每题_1_分，共_20_分。
)1.数据结构主要研究数据的( )。
A 、 逻辑结构B 、 存储结构C 、 逻辑结构和存储结构D 、 逻辑结构和存储结构及其运算的实现 2.算法在发生非法操作时可以做出处理的特性称为( )。
A 、 正确性B 、 易读性C 、 健壮性D 、 可靠性 3.下面的程序段违反了算法的( )原则。
void sam() { int n=2;while (n%2==0) n+=2; printf(n); }A 、 有穷性B 、 确定性C 、 可行性D 、 健壮性 4.线性表是具有n 个( )的有限序列。
A 、 表元素B 、 字符C 、 数据元素D 、 数据项 5.用单链表表示的链式队列的对头在链表的( )位置。
A 、 链头B 、 链尾C 、 链中D 、 任意 6.递归过程或函数调用时，处理参数及返回地址，要用一种称为( )的数据结构。
A 、 队列B 、 多维数组C 、 栈D 、 线性表得分年级：_____________ 专业：_____________________ 班级：_________________ 学号：_______________ 姓名：__________________ …………………………………………………………..装………………….订…………………..线………………………………………………………7.以下叙述中哪个选项是不正确的。
( )A 、 顺序存储方式只能用于存储线性结构。
B 、 顺序查找法适用于存储结构为顺序或链接存储的线性表。
数据结构实验报告知识范畴：树实验题目：二叉树的基本算法二(三叉链表的建立、非递归遍历)实验内容及要求：设二叉树采用三叉链表存储结构，结点数据域为字符类型，从键盘输入先序遍历字符序列（用#字符表示NULL指针域）建立三叉链表存储结构。
对先序、中序、后序遍历分别定义各自的求第一访问结点地址first(bt)以及下一访问结点地址next(p)函数，然后用三种遍历的first(bt)和next(p)函数实现非递归遍历。
实验目的：掌握二叉树的三叉链表存储结构及其非递归遍历算法。
数据结构设计简要描述：采用双向链表，每个结点包括字符类型的数据域和一个指针域。
链表结点结构如下：typedef struct node{ElemTp data; //字符数据域struct node *lchild; //左儿子指针struct node *rchild; //右儿子指针struct node *parent; //双亲指针}算法设计简要描述：采用三叉链表的存储结构，双亲指针指向根结点，左右指针指向左右儿子构造双向链表的二叉树。
每一次遍历时先用该遍历的first函数获取第一个访问的结点地址，调用next函数获取下一个访问的结点地址，当结点为空为循环的结束条件。
获取下一个访问的结点地址时需要判断是否需要回溯，需要回溯时通过双亲指针获取根节点地址，再判断是否需要再回溯。
回溯的结束条件为根节点地址为空。
输入/输出设计简要描述：从键盘输入二叉树的数据域，用#表示空。
按先序遍历的顺序依次构建二叉树。
输出三种遍历的遍历结果，并有文字提示。
编程语言说明：使用Visual C++编程。
主要代码采用C语言实现；动态存储分配采用C的malloc操作符实现；输入与输出采用C的printf和scanf流；程序注释采用C/C++规范。
主要函数说明：void InitTrT(TrT bt) //初始化二叉树void crtTrT(TrT *bt) //创建三叉结构的二叉树void destroyTrT(TrT *bt) //销毁二叉树Status emptyTrT(TrT bt) //判断二叉树是否为空int depthTrT(TrT bt) //求二叉树的深度TrT prefirst(TrT bt) //找出先序遍历的第一个结点TrT prenext(TrT bt) //找出先序遍历的下一结点void preorder(TrT bt) //先序非递归遍历TrT midfirst(TrT bt,int &mark) //查找中序遍历的第一个结点TrT midnext(TrT bt,int &mark) //查找中序遍历的下一个结点void midorder(TrT bt) //中序非递归遍历TrT lastfirst(TrT bt,int &mark) //查找后序遍历的第一个结点TrT lastnext(TrT bt,int &mark) //查找后序遍历的下一个结点void lasorder(TrT bt) //后序非递归遍历程序测试简要报告：输入：ABC#F##D##E##输出：程序输出结果与期望输出结果相符。
