用顺序和二叉链表作存储结构实现二叉排序树全代码.doc

数学与计算机学院 课程设计说明书 课 程 名 称 数据结构课程设计 课 程 代 码 6013799 题 目 二叉排序树的实现 年级 专业 班 10 级计科 3 班 学 生 姓 名 学 号 开 始 时 间 2012 年 12 月 25 日 完 成 时 间 2013 年 01 月 8 日 课程设计成绩 学习态度及平 时成绩 30 技术水平与实际 能力 20 创新 5 说明书撰写质量 45 总 分 100 指导教师签名 年 月 日 二叉排序树的实现 目 录 1 1 引引 言言 1 1 1 问题的提出 1 1 2 任务与分析 1 2 2 程序的主要功能程序的主要功能 2 2 1 二叉排序树的建立 2 2 2 二叉排序树的中序遍历 2 2 3 二叉排序树中元素的查找 2 2 4 二叉排序树中元素的删除 3 3 3 程序运行平台程序运行平台 4 4 4 总体设计总体设计 5 5 5 程序类的说明程序类的说明 6 6 6 模块模块 9 6 1 中序遍历模块 9 6 2 删除模块 9 7 7 系统测试系统测试 12 7 1 顺序存储 12 7 2 二叉链表存储 16 8 8 结论结论 19 总 结 19 心得体会 20 参考文献参考文献 21 全部代码全部代码 22 二叉链表结构C 22 二叉链表结构C 26 顺序存储结构C 29 二叉排序树的实现 摘摘 要要 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之 间的关系和操作等的学科 本课程设计中的二叉排序树 可以用顺序存储和链式存储 两种算法计算 本课程设中的二叉排序树 一共要实现四项基本的功能 它们分别是 二叉搜索树的创建 中序遍历 查找结点和删除结点 关键词 二叉排序树 中序遍历 搜索结点 删除结点 C C 1 二叉排序树的实现 1 引 言 1 1 问题的提出 研究关于如何创建二叉排序树并对树进行遍历 查找和删除等操作 同时关注用 顺序和二叉链表作存储结构带来的区别 1 2 任务与分析 用顺序和二叉链表作存储结构实现二叉排序树 1 以回车 n 为输入结束标志 输入数列 L 生成一棵二叉排序树 T 2 对二叉排序树 T 作中序遍历 输出结果 3 输入元素 x 查找二叉排序树 T 若存在含 x 的结点 则删除该结点 并作中序 遍历 执行操作 2 否则输出信息 无 x 2 二叉排序树的实现 2 程序的主要功能 2 1 二叉排序树的建立 建二叉树的结点至少应当包含三个域 分别存放结点的数据 data 左子女结点指 针 leftChild 和右子女结点指针 rightChild 整个二叉树的链表要有一个表头指针 它指 向二叉树的根结点 其作用是当作树的访问点 从空的二叉排序树开始 经过一系列的查找插入操作以后 生成了一棵二叉排序 树 根据二叉排序树的定义 建立一棵二叉排序树的过程是按照待排序序列元素的先 后次序 不断动态生成二叉树的结点 逐个插入到二叉树中 若 p 为根结点指针 b 为 当前待插入元素 其过程可以描述为 若为空树 p nil 动态生成一个结点 其数据域为当前待插入元素 b 左 右指 针域为 空 p 指向该结点 若非空树 比较 b 与根结点数据 data p 如果 bdata p t return 1 else if keydata searchBST t lchild key t p else searchBST t rchild key t p insertBSTinsertBST 的声明的声明 insertBST node t int key node p NULL s NULL if searchBST t key NULL s data key s lchild s rchild NULL if p t s else 7 二叉排序树的实现 if keydata p lchild s else p rchild s return 1 else return 0 inorderTraverseinorderTraverse 类的声明类的声明 inorderTraverse node t if t if inorderTraverse if inorderTraverse return 1 DeleteDelete 类的声明类的声明 node Delete node t int key node p t q NULL s f while p NULL if p data key break q p if p data key p p lchild else p p rchild if p NULL return t if p lchild NULL 8 二叉排序树的实现 if q NULL t p rchild else if q lchild p q lchild p rchild else q rchild p rchild free p else f p s p lchild while s rchild f s s s rchild if f p f lchild s lchild else f rchild s lchild p data s data free s return t 9 二叉排序树的实现 6 模块 6 1 中序遍历模块 系统将提示用户输入新添加的数据 输入结束后进行中序遍历 关键代码 inorderTraverse node t 中序遍历函数 if t if inorderTraverse 输出根结点 if inorderTraverse 中序遍历根的右子 树 return 1 6 2 删除模块 系统将对用户输入的数进行查找 查找到之后删除此数 并对全部数据进行中序遍历 关键代码 node Delete node t int key 删除函数 node p t q NULL s f while p NULL 查找要删除的点 10 二叉排序树的实现 if p data key break q p if p data key p p lchild else p p rchild if p NULL return t 查找失败 if p lchild NULL p 指向当前要删除的结点 if q NULL t p rchild q 指向要删结点的父母 else if q lchild p q lchild p rchild p 为 q 的左孩子 else q rchild p rchild p 为 q 的右孩子 free p else p 的左孩子不为空 f p s p lchild 11 二叉排序树的实现 while s rchild 左拐后向右走到底 f s s s rchild if f p f lchild s lchild 重接 f 的左子树 else f rchild s lchild 重接 f 的右子树 p data s data free s return t 12 二叉排序树的实现 7 系统测试 首先进入 VC 6 0 打开工程 zjr dsw 然后进入源程序 也可以不打开工程 直 接双击 zjr 文件夹下的 zjr exe 文件即可运行程序 7 1 顺序存储 图 7 1 1 打开程序 成功显示提示信息 13 二叉排序树的实现 图 7 1 2 输入数据 以 0 结束输入 操作成功 14 二叉排序树的实现 图 7 1 3 功能 1 中序输出数据 操作成功 图 7 1 4 功能 2 删除数据 显示提示信息 操作成功 15 二叉排序树的实现 图 7 1 5 删除数据 操作成功 16 二叉排序树的实现 图 7 1 6 重复执行程序 操作成功 7 2 二叉链表存储 图 7 2 1 打开程序 显示提示信息 操作成功 17 二叉排序树的实现 图 7 2 2 功能 1 输入数据 进行中序遍历 操作成功 18 二叉排序树的实现 图 7 2 3 功能 2 输入数据 进行删除 操作失败 因为没有此数据 显示 错误信息 图 7 2 4 功能 2 输入数据 进行中序遍历 操作成功 通过上述测试 本系统实现了二叉树的生成 中序遍历 查找删除功能 能避免 数据的输入错误等 验证结果正确 说明其符合算法设计的要求 1 正确性 可读性 健壮性 效率与低储存量需求 要写一个优质的算法 就必须考虑其时间复杂度 它表 示随问题的规模 n 的增大 算法执行时间的增长率和 f n 的增长率相同 和空间复 杂度 遍历二叉树的算法中的基本操作是访问结点 则不论按哪一次次序进行遍历 对含 n 个结点的二叉树 其时间复杂度都为 O n 所需空间为遍历过程中栈的最大 容量 即树的深度 最坏情况下为 n 则空间复杂度也为 O n 19 二叉排序树的实现 8 结论 总 结 这次课程设计使我对数据结构认识深刻了许多 其中最深刻的是我理解了用二叉 链表结构存储实现二叉排序树 同时也加深了对二叉树的理解 本课程设计实现了二 叉排序树的创建 中序遍历 删除二叉排序树中某个结点 在进行搜索时 还可以采 用更好的搜索结构即动态搜索结构 当没有找到时 可以将其插入 而不是仅仅提示 未找到 通过这一次的课程设计 我已经会用二叉链表存储结构实现对二叉排序树的 的创建 中序遍历 查找和某个删除结点等基本操作 但我同时也发现了自己许多不足之处 首先 对数据结构的掌握还不够 虽然完成了程序 但是只用到了基本的结点以 及链表 在数据结构的选择上避重就轻 覆盖面较小 不能很好的体现各种数据结构 的掌握度 同时也缺少了适当的锻炼 在这方面还需要自己主动去提高 其次 在程序整体的设计上还不够完善 各模块可以适当增加内容 界面还可以 更加的人性化些 这样整个程序才具有更强的美观性与实用性 总而言之 这次课程 设计给了我很大启发 我明白了 不管遇到什么问题 只要抓住根源 不气馁 从不 同方面去攻破它 终究会成功 生活也是如此 在今后的工作 学习中我将认真总结 经验教训 努力使自己成为一名技术过硬 工作严谨 思维活跃的工程人员 为提高 人们的生活质量做出更大的贡献 20 二叉排序树的实现 心得体会 课程设计结束了 在这次的课程设计中不仅检验了我所学的知识 也培养了我如 何去把握一件事情 如何去做一件事情 课程设计是我们专业课程知识综合应用的实 践训练是我们迈向社会 从事职业工作前一个必不可少的过程 我这次设计的科目是数据结构 数据结构 是一门研究非数值计算的程序设计问 题中计算机的操作对象 数据元素 以及它们之间的关系和运算等的学科 而且确保 经过这些运算后所得到的新结构仍然是原来的结构类型 这次通过对二叉排序树的深 入研究 我又一次的温习了 c c 和数据结构的有关知识 尽管这中间经历好多困难 但我通过查找多种资料 利用网络优势 完成了任务 我这次课程设计代码中主要使用了链表的循环和遍历这两种操作 循环链表是单 链表的另一种形式 遍历是指沿着某条收索路线 依次对树中每个节点均作一次且仅 作一次访问 通过这次的课程设计 更是让我深刻认识到自己在学习中的不足 同时 也找到了克服这些不足的方法 这是一笔很大的资源 在以后的学习中 我们应该利 用更多的时间去上机实验 加强自学的能力 多编写程序 相信不久以后我们的编程 能力都会有很大的提高 能创作出更多更完善更有新意的作品出来 21 二叉排序树的实现 参考文献 1 谭浩强 编著 程序设计 北京 清华大学出版社 2000 2 王珊珊 张志航 编著 C 程序设计教程 北京 机械工业出版社 2011 3 严蔚敏 吴伟民 编著 数据结构 北京 清华大学出版社 2001 22 二叉排序树的实现 全部代码全部代码 二叉链表结构二叉链表结构 c include include typedef struct Tnode int data 输入的数据 struct Tnode lchild rchild 结点的左右指针 分别指向结点的左右孩子 node BSTnode searchBST node t int key node f node p 查找函数 if t p f return 0 查找不成功 else if key t data p t return 1 查找成功 else if keydata searchBST t lchild key t p 在左子树中继续查找 else searchBST t rchild key t p 在右子树中继续查找 insertBST node t int key 插入函数 node p NULL s NULL if searchBST t key NULL s data key s lchild s rchild NULL if p t s 被插结点 s 为新的根结点 else if keydata p lchild s 被插结点 s 为左孩子 else p rchild s 被插结点 s 为右孩子 return 1 else return 0 树中已有关键字相同的结点 不再插入 23 二叉排序树的实现 inorderTraverse node t 中序遍历函数 if t if inorderTraverse 输出根结点 if inorderTraverse 中序遍历根的右子树 return 1 node Delete node t int key 删除函数 node p t q NULL s f while p NULL 查找要删除的点 if p data key break q p if p data key p p lchild else p p rchild if p NULL return t 查找失败 if p lchild NULL p 指向当前要删除的结点 if q NULL t p rchild q 指向要删结点的父母 else if q lchild p q lchild p rchild p 为 q 的左孩子 else q rchild p rchild p 为 q 的右孩子 free p else p 的左孩子不为空 f p s p lchild while s rchild 左拐后向右走到底 f s s s rchild if f p f lchild s lchild 重接 f 的左子树 24 二叉排序树的实现 else f rchild s lchild 重接 f 的右子树 p data s data free s return t void main node T NULL int num int s 0 j 0 i 0 int ch 0 node p NULL printf 输入一串数 每个数以空格分开 do scanf d if num printf 完成输入 n else insertBST while num printf n 1 中序输出 printf n 2 输入元素 while ch ch scanf d switch ch case 0 exit 0 0 退出 case 1 printf 中序遍历输出结果为 n inorderTraverse 1 中序遍历 break case 2 printf 输入元素 x 查找二叉排序树 T 若存在含 x 的结点 则删除该结点 并作中序遍历 否则输 出无 x scanf d 3 删除某个结点 if searchBST T num NULL 25 二叉排序树的实现 printf 删除成功 中序遍历输出 n inorderTraverse else printf 无 d num break default printf 无此结点 n break 输入无效字符 26 二叉排序树的实现 二叉链表结构二叉链表结构 c include using namespace std class node public node int i data i left NULL right NULL void inorder node cout data right void insert node else if itemdata insert ptr left item else insert ptr right item node find node if ptr data item return ptr else if itemdata find ptr left item else find ptr right item node else if itemdata 27 二叉排序树的实现 findy ptr left item else findy ptr right item node rl return left node rr return right void dele node else if ptr rr NULL ptr ptr rl else ptr ptr rr private int data node left 左孩子结点 node right 右孩子结点 int main int t i 0 j cout t cout 输入 t j node x new node j for i j x insert x j cout inorder x 作中序遍历 cout n 输入操作 当输入 1 时程序结束 j while j 1 node t x find x j 定位结点 if t NULL 28 二叉排序树的实现 node x dele y cout inorder x else cout 无 j cout n 输入操作 当输入 1 时程序结束 j return 0 29 二叉排序树的实现 顺序存储结构顺序存储结构 c include stdio h include malloc h include windows h define endflag 999999 define N 1000 int b N typedef struct int data int other int flag1 Link void Build Link a N int w i j k for i 0 i N i a i flag1 0 a i data 0 printf n t t t 请输入树的根结点 scanf d a 1 flag1 1 printf n t t t 请输入结点个数 scanf d for j 1 j k j printf n t t t 请输入结点的数值 scanf d printf n t t t 第 d 位 d j w a 0 data w a 0 flag1 1 i 1 if a 0 data a i data loop if a 2 i flag1 0 30 二叉排序树的实现 a 2 i data a 0 data a 2 i flag1 a 0 flag1 if a 2 i flag1 1 i 2 i if a 0 dataa i data goto loop1 if a 0 data a i data loop1 if a 2 i 1 flag1 0 a 2 i 1 data a 0 data a 2 i 1 flag1 a 0 flag1 if a 2 i 1 flag1 1 i 2 i 1 if a 0 dataa i data goto loop1 void Sdel Link a N int i int flag 0 int q int number 1 int j 1 int b N printf n t t t 请输入需要删除的结点的数值 scanf d for i 1 i N i 31 二叉排序树的实现 if a i data q a i data 0 printf n t t t 已删除 d q flag 1 for i 1 i