二叉树实验报告.doc

实践教学实践教学 学院学院 计算机信息与科学学院 2010 年春季学期 算法与数据结构算法与数据结构课程设计课程设计 题 目 二叉排序树的实现 专业班级 姓 名 学 号 指导教师 成 绩 二叉排序树问题 1 目目 录录 摘摘 要要 2 前前 言言 2 正正 文文 3 1 问题描述 3 2 任务与分析 3 3 整体程序设计 3 4 程序编码 4 5 程序的测试和演示 16 设计总结设计总结 17 参考文献参考文献 18 附录 程序代码程序代码 18 二叉排序树问题 2 摘摘 要要 该设计要求学生设计程序 实现二叉排序树的相关操作 通过该 题目的设计过程 可以加深理解二叉树 查找表的逻辑结构 存储结 构 掌握二叉排序树上基本运算的实现 进一步理解和熟练掌握课本 中所学的各种数据结构 学会如何把学到的知识用于解决实际问题 培养学生的动手能力 使用二叉链表存储二叉排序树 生成一棵二叉排序树 并掌握二 叉树正确查找 插入 删除一个给定值的方法 关键词 关键词 二叉排序树 二叉链表 查寻 删除 遍历 输出结果 前前 言言 问题的背景问题的背景 二叉树是树型结构的一个重要类型 关于二叉树的存储结构 及算法都较为简单 因此 二叉树在数据结构的研究领域中具有 很重要的地位 问题的意义问题的意义 掌握二叉树的概念 二叉树的性质 存储结构以及基本运算 二叉排序树问题 3 并用二叉树解决一些综合应用问题 正正 文文 1 问题描述 操作 1 用顺序和二叉链表作存储结构设置一个字符作为输入结束标志 输入数列 L 生成一棵二叉排序树 T 对二叉排序树 T 作中序遍历 输出 结果 操作 2 输入元素 x 查找二叉排序树 T 若存在含 x 的结点 则删除该结点 并作中序遍历 执行操作 2 否则输出信息 无 x 2 任务与分析 1 查阅文献资料 一般在 3 篇以上 2 建立数据的逻辑结构和物理结构 3 完成相应算法的设计 4 完成测试工作 5 撰写设计说明书 6 做好答辩工作 任务是一个二叉排序树的实现问题 根据任一数列生成一棵二叉 排序树 查询结点并删除结点且保证仍为二叉排序树 根据二叉排序 树的概念 查找当前插入的元素的位置 删除结点如果不是叶子结点 要注意考虑如何使树仍为二叉排序树 当删除结点为根结点时 考虑 如何保证二叉树照常输出 3 整体程序设计方案 此课题是研究二叉排序树的实现 建立二叉树 查找一个数是否 二叉排序树问题 4 存在 插入一个给定的值 删除一个给定的值并输出结果 为了直观 和方便 画出流程图如下图 1 主程序模块 创建一个 菜单 建立一个 二叉树 查找字符 是否存在 删除查到 的结点 遍历输出结 果 图 1 4 程序编码 4 14 1 主程序 程序执行时需要的头文件及程序中运用到的结构体 include include include include include define maxsize 50 typedef struct node2 char data 数据域 struct node2 lchild rchild parent 左指针域 右指针域 btnode 二叉链接点类型 typedef struct stack btnode data maxsize int top seqstack 建立一个栈 以便非递归使用 4 24 2 建立一个二叉排序树 以先序形式构建一个二叉树 使产生的结点有 3 个指针域 左 右孩 子及父结点 以空格结束 结点为空 btnode createbitree btnode scanf c if ch t NULL else t btnode malloc sizeof btnode t data ch t parent NULL t lchild createbitree t lchild if t lchild t lchild parent t t rchild createbitree t rchild if t rchild t rchild parent t return t 4 34 3 在一个二叉排序树查找一个数是否存在 对输入的字符 x 进行查找 当 x 存在时返回该结点 否则返回空 btnode searchnode btnode b char x 查找结点 btnode p if b NULL return NULL 空二叉树的查找失败出口 else if b data x return b 查找成功出口 else p searchnode b lchild x 在左子树查找 if p NULL return p else return searchnode b rchild x 在右子树查找 4 54 5 删除结点 对结点进行删除 有以下 5 种情况 根结点 叶子结点 有右无左 有左无右 有左有右 当结点删除后不改变输出二叉树的顺序 btnode deltree btnode t char x btnode q if t lchild NULL q NULL else if t parent lchild data x q t parent lchild t parent lchild NULL else q t parent rchild t parent rchild NULL free t else if t lchild NULL while q lchild NULL 以先序方式遍历到最后一个左孩子 q q lchild q parent lchild NULL q rchild t rchild t rchild parent q q parent NULL else if t parent lchild data x t parent lchild t rchild t rchild parent t parent else t parent rchild t rchild t rchild parent t parent 二叉排序树问题 7 free t else if t lchild NULL q parent NULL else if t parent lchild data x t parent lchild t lchild t lchild parent t parent else t parent rchild t lchild t lchild parent t parent free t else 删除结点既有 左孩子又有右孩子 if t parent NULL 删除结点为根结点 q t rchild while q lchild NULL 以先序方式遍历到最后一个左孩子 q q lchild q parent lchild NULL q lchild t lchild q rchild t rchild t rchild parent q t lchild parent q q parent NULL else if t parent lchild data x t parent rchild data x 直接指向 删除结点的右孩子 二叉排序树问题 8 q t rchild while q lchild NULL 以先序方式遍历到最后一个左孩子 q q lchild q parent lchild NULL 当将 q 结点提出时 则应该其原来的储存位 置置空 用 q 代替要删除结点 保证以中序输出的结点顺序不变 if t parent lchild data x q lchild t lchild q rchild t rchild t lchild parent q t rchild parent q t parent lchild q q parent t parent else q lchild t lchild q rchild t rchild t lchild parent q t rchild parent q t parent rchild q q parent t parent free t return q 4 5 进行遍历 void preorder btnode bt 递归 先序 遍历 if bt NULL printf c bt data preorder bt lchild preorder bt rchild void preorder2 btnode bt 非递归 先序遍历 二叉排序树问题 9 btnode p seqstack ps ps top 1 if bt NULL return else ps top ps data ps top bt while ps top 1 p ps data ps top ps top printf c p data if p rchild NULL ps top ps data ps top p rchild if p lchild NULL ps top ps data ps top p lchild void inorder btnode p 递归中序遍历 if p NULL inorder p lchild printf c p data inorder p rchild void inorder2 btnode bt 非递归中序遍历 btnode p q 二叉排序树问题 10 seqstack ps ps top 1 if bt NULL return else while bt NULL ps top ps data ps top bt bt bt lchild while ps top 1 p ps data ps top ps top printf c p data while p rchild NULL ps top ps data ps top p rchild q p rchild while q lchild NULL ps top ps data ps top q lchild q q lchild break void postorder btnode bt 递归后序遍历 if bt NULL postorder bt lchild 二叉排序树问题 11 postorder bt rchild printf c bt data void postorder2 btnode bt 非递归后序遍历 seqstack ps ps top 1 btnode t int flag do while bt NULL ps top ps data ps top bt bt bt lchild t NULL flag 1 while ps top 1 if bt rchild t t 表示为 null 或者右子节点被访问过了 printf c bt data ps top t bt t 记录下刚刚访问的节点 else bt bt rchild flag 0 二叉排序树问题 12 while ps top 1 4 64 6 创建菜单 void output1 int i for i 0 i 23 i printf for i 0 i 32 i printf printf n void mainpp int i output1 for i 0 i 23 i printf printf printf 1 先 序 建 立 二 叉 树 for i 0 i 4 i printf printf printf n for i 0 i 23 i printf printf printf 2 非递归先序遍历二叉树 for i 0 i 4 i printf printf printf n for i 0 i 23 i printf printf printf 3 非递归中序遍历二叉树 二叉排序树问题 13 for i 0 i 4 i printf printf printf n for i 0 i 23 i printf printf printf 4 非递归后序遍历二叉树 for i 0 i 4 i printf printf printf n for i 0 i 23 i printf printf printf 5 递归先序 遍历 二叉树 for i 0 i 4 i printf printf printf n for i 0 i 23 i printf printf printf 6 递归中序 遍历 二叉树 for i 0 i 4 i printf printf printf n for i 0 i 23 i printf printf printf 7 递归后序 遍历 二叉树 for i 0 i 4 i printf printf printf n for i 0 i 23 i printf printf printf 8 查 找 并 删 除 结 点 二叉排序树问题 14 for i 0 i 4 i printf printf printf n for i 0 i 23 i printf printf printf 9 输出删除结点的二叉树 for i 0 i 4 i printf printf printf n for i 0 i 23 i printf printf printf 10 以嵌套形式输出二叉树 for i 0 i 3 i printf printf printf n for i 0 i 23 i printf printf printf 0 退 出 for i 0 i 5 i printf printf printf n output1 4 74 7 主函数主函数 void main system color 0B mainpp btnode root t char x int w k 1 while k 二叉排序树问题 15 printf 请选择0 9 scanf d getchar switch w case 0 return case 1 printf 先 序 建 立 二 叉 树 createbitree root getchar break case 2 printf 非递归先序遍历二叉树 preorder2 root break case 3 printf 非递归中序遍历二叉树 inorder2 root break case 4 printf 非递归后序遍历二叉树 postorder root break case 5 printf 递归先序遍历二叉树 preorder root break case 6 printf 递归中序遍历二叉树 inorder root break case 7 二叉排序树问题 16 printf 递归后序遍历二叉树 postorder root break case 8 printf 输入字符x scanf c getchar t searchnode root x if t if t root root deltree t x else deltree t x printf 删除结点成功 n else printf 无x n break case 9 printf 中序输出删除后二叉树的各结点 n inorder root break case 10 printf 嵌套形式输出二叉树 dispbitree root default return printf n继续运行吗y 1 n 0 scanf d getchar if k 二叉排序树问题 17 return 5 程序测试与演示 测试数据 a b c d e f 测试结果下如图 设 计 总 结 通过这次课程设计的程序实践 我实在获益匪浅 数据结构是这 个学期开展的一门学科 学习好这门学科是非常重要的 在以后的程 序设计方面这门学科能给我们很大的帮助 同时 学习这门学科也是 二叉排序树问题 18 艰辛的 因为它比较难懂 这不仅需要我们要发挥我们的聪明才志 还需要我们在不断的实践中领悟 这次的程序设计对我来说无疑是一个具大的考验 从接起课题后 我就一直为实现程序而努力 翻阅相关书籍 在网上查找资料 因为 开始时基础不是很好 过程中遇到了不少的阻碍 编写程序的进度也 比较慢 但是通过努力 我对这次实验的原理有了一定的理解 通过 参照从网上找到的源程序 终于在其它源程序的基础下写出了本次课 程设计的核心算法 并使其能够正常的运行 这次的设计工作 让我体会到了作为一个编程人员的艰难 一个 算法到具体实现 再到应用层面的开发是需要有一段较长的路要走的 不是一朝一夕就可以实现的 而且在编好程序后 编程人员还要花很 多的时间去完善它 其中的辛苦 很难用言语表达出来 今后 我会更加努力的学习专业知识 努力提高自我的能力 参考文献参考文献 1 谭浩强 c 语言程序设计 清华大学出版社 2 陈建新 李志敏 数据结构 实验指导与课程设计教程 附录附录 程序代码程序代码 include include include 二叉排序树问题 19 include include define maxsize 50 typedef struct node2 char data 数据域 struct node2 lchild rchild parent 左指针域 右指针域 btnode 二叉链接点类型 typedef struct stack 建立一个栈 btnode data maxsize int top seqstack btnode createbitree btnode scanf c if ch t NULL else t btnode malloc sizeof btnode t data ch t parent NULL t lchild createbitree t lchild if t lchild t lchild parent t t rchild createbitree t rchild if t rchild t rchild parent t return t btnode searchnode btnode b char x 查找结点 二叉排序树问题 20 btnode p if b NULL return NULL 空二叉树的查找失败出口 else if b data x return b 查找成功出口 else p searchnode b lchild x 在左子树查找 if p NULL return p else return searchnode b rchild x 在右子树查找 btnode deltree btnode t char x btnode q if t lchild NULL q t q NULL else if t parent lchild data x printf 删除结点为叶子结点 n q t parent lchild t parent lchild NULL else printf 删除结点为叶子结点 n 二叉排序树问题 21 q t parent rchild t parent rchild NULL free t else if t lchild NULL q t rchild while q lchild NULL 以先序方式遍历到最后一个左孩子 q q lchild q parent lchild NULL q rchild t rchild t rchild parent q q parent NULL else if t parent lchild data x printf 删除结点叶结点 n t parent lchild t rchild t rchild parent t parent else printf 删除结点叶结点 n t parent rchild t rchild t rchild parent t parent free t else if t lchild NULL q t lchild q parent NULL else if t parent lchild data x printf 删除结点叶结点 n t parent lchild t lchild t lchild parent t parent else printf 删除结点叶结点 n t parent rchild t lchild t lchild parent t parent free t else 删除结点既有 左孩子又有右孩子 if t parent NULL 删除结点为根结点 printf 删除结点叶结点 n q t rchild while q lchild NULL 以先序方式遍历到最后一个左孩子 q q lchild q parent lchild NULL q lchild t lchild q rchild t rchild t rchild parent q t lchild parent q 二叉排序树问题 23 q parent NULL else if t parent lchild data x t parent rchild data x 直接指向 删除结点的右孩子 printf 删除结点叶结点 n q t rchild while q lchild NULL 以先序方式遍历到最后一个左孩子 q q lchild q parent lchild NULL 当将 q 结点提出时 则应该其原来的储 存位置置空 用 q 代替要删除结点 保证以中序输出的结点顺序不变 if t parent lchild data x q lchild t lchild q rchild t rchild t lchild parent q t rchild parent q t parent lchild q q parent t parent else q lchild t lchild q rchild t rchild t lchild parent q t rchild parent q t parent rchild q q parent t parent free t return q 二叉排序树问题 24 void preorder btnode bt 递归 先序 遍历 if bt NULL printf c bt data preorder bt lchild preorder bt rchild void preorder2 btnode bt 非递归 先序遍历 btnode p seqstack ps ps top 1 if bt NULL return else ps top ps data ps top bt while ps top 1 p ps data ps top ps top printf c p data if p rchild NULL ps top ps data ps top p rchild if p lchild NULL 二叉排序树问题 25 ps top ps data ps top p lchild void inorder btnode p 递归中序遍历 if p NULL inorder p lchild printf c p data inorder p rchild void inorder2 btnode bt 非递归中序遍历 btnode p q seqstack ps ps top 1 if bt NULL return else while bt NULL ps top ps data ps top bt bt bt lchild 二叉排序树问题 26 while ps top 1 p ps data ps top ps top printf c p data while p rchild NULL ps top ps data ps top p rchild q p rchild while q lchild NULL ps top ps data ps top q lchild q q lchild break void postorder btnode bt 递归后序遍历 if bt NULL postorder bt lchild postorder bt rchild printf c bt data void postorder2 btnode bt 非递归后序遍历 二叉排序树问题 27 seqstack ps ps top 1 btnode t int flag do while bt NULL ps top ps data ps top bt bt bt lchild t NULL flag 1 while ps top 1 if bt rchild t t 表示为 null 或者右子节点被访问过了 printf c bt data ps top t bt t 记录下刚刚访问的节点 else bt bt rchild flag 0 二叉排序树问题 28 while ps top 1 void dispbitree btnode b 嵌套 输出二叉树 if b NULL printf c b data if b lchild NULL b rchild NULL printf dispbitree b lchild 递归处理左子树 if b rchild NULL printf dispbitree b rchild 递归处理右子树 printf void output1 int i for i 0 i 23 i printf for i 0 i 32 i printf printf n void mainpp int i output1 for i 0 i 23 i printf printf printf 1 先 序 建 立 二 叉 树 for i 0 i 4 i printf 二叉排序树问题 29 printf printf n for i 0 i 23 i printf printf printf 2 非递归先序遍历二叉树 for i 0 i 4 i printf printf printf n for i 0 i 23 i printf printf printf 3 非递归中序遍历二叉树 for i 0 i 4 i printf printf printf n for i 0 i 23 i printf printf printf 4 非递归后序遍历二叉树 for i 0 i 4 i printf printf printf n for i 0 i 23 i printf printf printf 5 递归先序 遍历 二叉树 for i 0 i 4 i printf printf printf n for i 0 i 23 i printf 二叉排序树问题 30 printf printf 6 递归中序 遍历 二叉树 for i 0 i 4 i