实验三：二叉树操作

《实验三：二叉树操作》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告学院（系）名称：计算机与通信工程学院姓名**学号********专业计算机科学与技术班级2015级*班实验项目实验三：二叉树操作课程名称数据结构与算法课程代码0661013实验时间年月日第节实验地点7-***考核标准实验过程25分程序运行20分回答问题15分实验报告30分特色功能5分考勤违纪情况5分成绩成绩栏其它批改意见:教师签字：考核内容评价在实验课堂中的表现，包括实验态度、编写程序过程等内容等。□功能完善,□功能不全□有小错□无法运行○正确○基本正确○有提示○无法回答○完整○较完整○一般○内容极少○无报告

2、○有○无○有○无一、实验目的理解二叉树的逻辑特点和二叉树的性质；掌握二叉树的二叉链表存储结构，掌握二叉树的创建算法、遍历算法的递归与非递归实现，并能在遍历算法基础上实现较复杂算法设计。二、实验题目与要求1.每位同学按下述要求实现相应算法：以二叉链表为存储结构，实现二叉树的创建、遍历算法1）问题描述：在主程序中提供下列菜单：1…建立树2…前序遍历树3…中序(非递归)遍历树4…后序遍历树0…结束2）实验要求：①定义下列过程：CreateTree():按从键盘输入的前序序列，创建树PreOrderTree()：前序遍历树（

3、递归）InOrderTree()：中序(非递归)遍历树LaOrderTree():后序遍历树（递归）②每位同学在实验过程中要单步运行程序，跟踪二叉树的创建过程与前序遍历的递归过程。3）注意问题:①注意理解递归算法的执行步骤。②注意字符类型数据在输入时的处理。③重点理解如何利用栈结构实现非递归算2.编写算法交换二叉树中所有结点的左、右子树1）问题描述：编写一算法，交换二叉树中所有结点的左、右子树2）实验要求：以二叉链表作为存储结构3.试编写按层次顺序遍历二叉树的算法1）问题描述：编写按层次顺序遍历二叉树的算法2）实验要

4、求：以二叉链表作为存储结构4.编写算法求二叉树高度及宽度。1）问题描述：二叉树高度是指树中所有节点的最大层数，二叉树宽度是指在二叉树的各层上，具有节点数最多的那一层上的节点总数。2）实验要求：以二叉链表作为存储结构三、实验过程与实验结果应包括如下主要内容：Ø数据结构定义Ø二叉树是个节点的有限集合，该集合或者为空，或者由一个根节点及两个分别称为左子树和右子树的互不相交的二叉树组成。当集合为空时，称该二叉树为空二叉树。Ø算法设计思路简介Ø1、利用递归算法前序建立二叉树，并完成二叉树的前序、中序和后序遍历。其中前序遍历和后

5、序遍历均用递归算法，中序遍历借助栈的机制，实现非递归遍历。Ø2、在前序遍历的过程中利用中间变量交换左右子树。Ø3、利用队列。当上一层中的数据全部出队（遍历）完毕再遍历本层节点。Ø4、高度：获取所有节点到根节点的最长路径。宽度：在层次遍历的基础上，返回最多节点的层的节点数。Ø算法描述：可以用自然语言、伪代码或流程图等方式Ø1、创建树：Ø（1）声明节点Ø（2）输入当前节点，若输入为#则当前节点为空，否则为当前节点申请空间。Ø（3）将输入的值赋给当前节点的data域，并前序建立当前节点的左子树和右子树。Ø（4）返回当前节点

6、。Ø前序遍历树：Ø（1）若当前节点为空则返回上一级函数，否则打印当前节点。Ø（2）前序遍历当前节点的左子树。Ø（3）前序遍历当前节点的右子树。Ø中序遍历树：Ø（1）声明一个顺序栈，并用p指针指向当前节点。Ø（2）若当前节点和栈不同时为空则重复进行下一步。否则程序结束Ø（3）若当前节点不为空则重复进行第四步，否则执行第五步。Ø（4）在栈不满的情况下将当前节点入栈，并把p指针指向当前节点左子树的根节点。Ø（5）若栈为空则执行第三步，否则执行第六步。Ø（6）将栈顶元素出栈，并打印栈顶元素的data，将p指向栈顶元素的右子树

7、的根节点。执行第二步。Ø前序遍历树：Ø（1）若当前节点为空则返回上一级函数否则执行下一步。Ø（2）后序遍历当前节点的左子树。Ø（3）后序遍历当前节点的右子树。Ø（3）打印当前节点的data。Ø2、Ø（1）若当前节点为空则返回NULL,结束。否则执行下一步。Ø（2）利用中间变量temp交换当前节点的左右子树。Ø（3）交换当前的点左子树根节点的左右子树。Ø（4）交换当前节点右子树根节点的左右子树。Ø（4）返回根节点。Ø3、Ø（1）利用指针temp指向根节点，并初始化一个队列。Ø（2）将temp指向的当点节点入队。Ø（3）

8、重复指向以下所有步骤，直到遇到break语句。Ø（4）用变量len记录队列中二叉树当前层的节点数。Ø（5）若len为0则结束整个程序，否则执行第六步。Ø（6）当len>0（即队列中还有前层的节点时）重复指向以下所有步骤。否则执行第三步。Ø（7）将当前对头出栈，len++，打印出队元素Ø（8）如果出队元素的左子树的根节点不为空则入队,len--.