实验三：二叉树操作

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