《实验三：二叉树操作word版本.》由会员分享，可在线阅读，更多相关《实验三：二叉树操作word版本.（15页珍藏版）》请在金锄头文库上搜索。
1、实 验 三 二 叉 树 操 作 精品文档 收集于网络 如有侵权请联系管理员删除 实验报告 学院 系 名称 计算机与通信工程学院 姓名 学号 专业计算机科学与技术 班级2015级 班实验项目实验三 二叉树操作 课程名称数据结构与算法课程代码0661013 实验时间年 月 日第节实验地点7 考核 标准 实验过程 25 分 程序运行 20 分 回答问题 15 分 实验报告 30分 特色 功能 5 分 考勤违 纪情况 5 分 成绩 成绩 栏 其它批改意见 教师签字 考核 内容 评价在实验 课堂中的表 现 包括实 验态度 编 写程序过程 等内容等 功能完善 功能不全 有小错 无法运行 正确 基本正确 有
2、提示 无法回答 完整 较完整 一般 内容极少 无报告 有 无 有 无 精品文档 收集于网络 如有侵权请联系管理员删除 一 实验目的 理解二叉树的逻辑特点和二叉树的性质 掌握二叉树的二叉链表存储结构 掌握二叉树 的创建算法 遍历算法的递归与非递归实现 并能在遍历算法基础上实现较复杂算法设计 二 实验题目与要求 1 每位同学按下述要求实现相应算法 以二叉链表为存储结构 实现二叉树的创建 遍 历算法 1 问题描述 在主程序中提供下列菜单 1 建立树 2 前序遍历树 3 中序 非递归 遍历树 4 后序遍历树 0 结束 2 实验要求 定义下列过程 CreateTree 按从键盘输入的前序序列 创建树 P
3、reOrderTree 前序遍历树 递归 InOrderTree 中序 非递归 遍历树 LaOrderTree 后序遍历树 递归 每位同学在实验过程中要单步运行程序 跟踪二叉树的创建过程与前序遍历的递归 过程 3 注意问题 注意理解递归算法的执行步骤 注意字符类型数据在输入时的处理 重点理解如何利用栈结构实现非递归算 2 编写算法交换二叉树中所有结点的左 右子树 1 问题描述 编写一算法 交换二叉树中所有结点的左 右子树 2 实验要求 以二叉链表作为存储结构 3 试编写按层次顺序遍历二叉树的算法 1 问题描述 编写按层次顺序遍历二叉树的算法 2 实验要求 以二叉链表作为存储结构 4 编写算法求
4、二叉树高度及宽度 1 问题描述 二叉树高度是指树中所有节点的最大层数 二叉树宽度是指在二叉树 的各层上 具有节点数最多的那一层上的节点总数 2 实验要求 以二叉链表作为存储结构 三 实验过程与实验结果 应包括如下主要内容 数据结构定义 二叉树是个节点的有限集合 该集合或者为空 或者由一个根节点及两个分别称为左子树 和右子树的互不相交的二叉树组成 当集合为空时 称该二叉树为空二叉树 算法设计思路简介 1 利用递归算法前序建立二叉树 并完成二叉树的前序 中序和后序遍历 其中前序遍历 和后序遍历均用递归算法 中序遍历借助栈的机制 实现非递归遍历 2 在前序遍历的过程中利用中间变量交换左右子树 3 利
5、用队列 当上一层中的数据全部出队 遍历 完毕再遍历本层节点 4 高度 获取所有节点到根节点的最长路径 宽度 在层次遍历的基础上 返回最多节点 精品文档 收集于网络 如有侵权请联系管理员删除 的层的节点数 算法描述 可以用自然语言 伪代码或流程图等方式 1 创建树 1 声明节点 2 输入当前节点 若输入为 则当前节点为空 否则为当前节点申请空间 3 将输入的值赋给当前节点的data 域 并前序建立当前节点的左子树和右子树 4 返回当前节点 前序遍历树 1 若当前节点为空则返回上一级函数 否则打印当前节点 2 前序遍历当前节点的左子树 3 前序遍历当前节点的右子树 中序遍历树 1 声明一个顺序栈
6、并用p 指针指向当前节点 2 若当前节点和栈不同时为空则重复进行下一步 否则程序结束 3 若当前节点不为空则重复进行第四步 否则执行第五步 4 在栈不满的情况下将当前节点入栈 并把p 指针指向当前节点左子树的根节点 5 若栈为空则执行第三步 否则执行第六步 6 将栈顶元素出栈 并打印栈顶元素的data 将 p 指向栈顶元素的右子树的根节点 执 行第二步 前序遍历树 1 若当前节点为空则返回上一级函数否则执行下一步 2 后序遍历当前节点的左子树 3 后序遍历当前节点的右子树 3 打印当前节点的data 2 1 若当前节点为空则返回NULL 结束 否则执行下一步 2 利用中间变量temp 交换当前
7、节点的左右子树 3 交换当前的点左子树根节点的左右子树 4 交换当前节点右子树根节点的左右子树 4 返回根节点 3 1 利用指针temp 指向根节点 并初始化一个队列 2 将 temp 指向的当点节点入队 3 重复指向以下所有步骤 直到遇到break 语句 4 用变量len 记录队列中二叉树当前层的节点数 5 若 len 为 0 则结束整个程序 否则执行第六步 6 当 len 0 即队列中还有前层的节点时 重复指向以下所有步骤 否则执行第三步 7 将当前对头出栈 len 打印出队元素 8 如果出队元素的左子树的根节点不为空则入队 len 9 如果出队元素的右子树的根节点不为空则入队 len 4
8、 1 利用指针temp 指向根节点 并初始化一个队列 2 将 temp 指向的当点节点入队 并声明当前层最大节点数为0 3 重复指向以下所有步骤 直到遇到break 语句 若遇到break 语句则结束整个程序并 返回最大节点数 4 用变量len 记录队列中二叉树当前层的节点数 精品文档 收集于网络 如有侵权请联系管理员删除 5 若 len 为 0 则结束整个程序 否则执行第六步 6 当 len 0 即队列中还有前层的节点时 重复七 九步 否则执行第十步 7 将当前对头出栈 len 打印出队元素 8 如果出队元素的左子树的根节点不为空则入队 len 9 如果出队元素的右子树的根节点不为空则入队
9、len 10 当前层最大节点数等于上一层最大节点数和当前队列中的节点数中较大的一个 执行第三步 算法的实现和测试结果 包括算法运行时的输入 输出 实验中出现的问题及解决办法等 1 输入 ABH FD E CK G 输出 2 输入 ABH FD E CK G 输出 3 输入 ABH FD E CK G 输出 4 输入 ABH FD E CK G 输出 精品文档 收集于网络 如有侵权请联系管理员删除 算法时间复杂度分析 1 O n 2 O n 3 O n 4 O n 四 收获与体会 学了二叉树之后顿时感觉之前的内容有多简单了 二叉树中用到很多递归算法 看起来 很难懂 需要一步一步的跟下去才能理解
10、但是理解还远远不够 关键是是自己能写出来属 于自己的递归算法 经过长时间的练习 我已经能写出来一些简单的递归算法了 但是稍微 难一点的就写不出来了 后面的图还更难 革命尚未成功 诸君还需努力呐 我相信经过自 己不屑的练习 我会提高的 五 源代码清单 1 include include define MaxSize 100 typedef char Elemtype typedef struct BitNode Elemtype data struct BitNode lchild struct BitNode rchild BitNode BitNode CreateTree char ch
11、BitNode T scanf c if ch T NULL else if T BitNode malloc sizeof BitNode exit 1 T data ch T lchild CreateTree T rchild CreateTree return T void PreOrder BitNode T if T NULL return printf c T data 精品文档 收集于网络 如有侵权请联系管理员删除 PreOrder T lchild PreOrder T rchild void PostOrder BitNode T if T NULL return Post
12、Order T lchild PostOrder T rchild printf c T data void InOrder BitNode T BitNode p q BitNode Stack MaxSize int top 0 p T while p NULL if top data p p rchild int main BitNode root root CreateTree printf 前序遍历结果 PreOrder root printf n printf 中序遍历结果 InOrder root printf n printf 后序遍历结果 PostOrder root 精品文
13、档 收集于网络 如有侵权请联系管理员删除 printf n return 0 2 include include typedef char Elemtype typedef struct BitTree Elemtype data struct BitTree lchild struct BitTree rchild BitTree BitTree CreateTree char ch BitTree T scanf c if ch T NULL else T BitTree malloc sizeof BitTree T data ch T lchild CreateTree T rchil
14、d CreateTree return T void InOrder BitTree T if T NULL return InOrder T lchild printf c T data InOrder T rchild BitTree Exchange BitTree T BitTree temp if T NULL return NULL temp T lchild T lchild T rchild T rchild temp Exchange T lchild Exchange T rchild return T int main BitTree root root CreateTr
15、ee printf 中序遍历原二叉树 精品文档 收集于网络 如有侵权请联系管理员删除 InOrder root root Exchange root printf n中序遍历交换后的二叉树 InOrder root printf n return 0 3 include include define MaxSize 100 typedef char Elemtype typedef struct BitTree Elemtype data struct BitTree lchild struct BitTree rchild BitTree typedef BitTree Elementtyp
16、e typedef struct QueueNode Elementtype base int front int rear QueueNode BitTree CreateTree char ch BitTree T scanf c if ch T NULL else T BitTree malloc sizeof BitTree T data ch T lchild CreateTree T rchild CreateTree return T 以上为树 QueueNode InitQueue QueueNode Q Q QueueNode malloc sizeof QueueNode Q base Elementtype malloc MaxSize sizeof Elementtype Q rear Q front 0 return Q int QueueFull QueueNode Q 精品文档 收集于网络 如有侵权请联系管理员删除 if Q rear 1 MaxSize Q front return 1 elsereturn 0 int QueueEmpty QueueN
