二叉排序树的实现(最终版)

实实 验验 报报 告告 课程名称 数据结构课程设计 题目名称 二叉树的实现 学生学院 应用数学学院 专业班级 14 信安 1 班 学 号 3114008224 学生姓名 阮志敏 指导教师 刘志煌 2016 年 12 月 9 日 二叉排序树的实现二叉排序树的实现 一 内容和要求 一 内容和要求 1 编程实现二叉排序树 包括生成 插入 删除 2 对二叉排序树进行先根 中根和后根非递归遍历 3 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来 4 分别用二叉排序树和数组去存储一个班 50 人以上 的成员信息 至少包括学号 姓 名 成绩 3 项 对比查找效率 并说明在什么情况下二叉排序树效率高 为什么 5 格式按照作业的要求 对数据测试 分析 总结和改进的工作要做详细一点 2 解决方案和关键代码解决方案和关键代码 1 二叉排序二叉排序树树的的实现实现 1 首先定义二叉树的结构体 代码如下 struct TreeNode typedef struct TreeNode TreePosition typedef struct TreeNode SearchTree typedef struct TreeNode Tree typedef int TreeElementType struct TreeNode 二叉树 TreeElementType element 节点中的元素 SearchTree left 左儿子 SearchTree right 右儿子 int leght 节点的深度 用于打印 int position 节点的位置 用于打印 2 实现插入和生成二叉树节点的方法 在这里用到了递归插入的方法 SearchTree insertTreeNode TreeElementType x SearchTree tree if tree NULL tree makeTree x NULL NULL 插入在该处 else if x element tree left insertTreeNode x tree left else if x tree element tree right insertTreeNode x tree right 如果相等 什么也不做 return tree 当 tree NULL 时 就是递归终止的条件 也是插入该节点的地方 在这里 用 makeTree 方 法创建一个节点 其代码如下 static SearchTree makeTree TreeElementType x SearchTree left SearchTree right SearchTree node SearchTree malloc sizeof struct TreeNode if node NULL printf make TreeNode fail n else node element x node left left node right right return node 3 实现二叉树节点删除的方法 删除节点时有 3 种情况 情况一 被删除的节点同时含有左儿子和右儿子 在这种情况下 必须找出一个合适的节点来替代被删除的节点 由于二叉树的特性 被删除节点右子树中的节点都比左子树节点大 因此 可以替代原节点的节点必然在被删 除节点的右子树中 并且是右子树的最小节点 所以 在这种情况下 应该把被删除节点 的右子树中最小节点替代被删除节点 情况二 被删除节点只有一个子节点 显然 应该把它的子节点替代它 情况三 被删除节点没有子节点 此时 直接删除它 具体代码如下 同样使用递归删除的方法 SearchTree deleteTreeNode TreeElementType x SearchTree tree TreePosition tmpNode if tree NULL 到叶节点了 还没找到可以删除的 printf not found n else if x element tree left deleteTreeNode x tree left else if x tree element tree right deleteTreeNode x tree right else if x tree element if tree left 找出右子树中最小的 tree element tmpNode element 把右子树中最小的值给当前树 节点 把 tree 右子树中最小值的节点删除了 那个要删除的节点不可能有左 儿子 tree right deleteTreeNode tree element tree right else 只有一个子节点 或者没有子节点 tmpNode tree if tree left NULL 0 个子节点也包含在内 tree tree right else if tree right NULL tree tree left free tmpNode return tree 其中的 findMin 方法为找出以某个节点为根的树的最小节点 在这里可以用循环遍历 tree left 来实现 也可以用递归来实现 代码如下 TreePosition findMin SearchTree tree 递归实现 if tree NULL return NULL if tree left NULL return findMin tree left else return tree 2 对对二叉排序二叉排序树进树进行先根 中根和后根非行先根 中根和后根非递归递归遍遍历历 1 先根遍历 先根遍历先访问根 再访问左儿子 接着访问右儿子 上图中的树 如果用先根遍历 顺序则是 A B E F C 要实现非递归遍历 必须使用循环来进行遍历 这就需要使每次循环时 都有一致的 操作 为了一致性 先定义每次循环中的一致性操作 每次循环只处理一个节点 也就是 打印当前节点 其左节点要等到下次循环再打印 这时 如果当前节点有左右节点 则需 要储存当前节点的左节点和右节点 以便下次循环时取出打印 如果没有左右节点 则直 接进入下次循环 在这里 有两种数据结构可用于储存待打印节点 一个是队列 一个是 栈 先尝试队列 队列的特性是先进先出 我们希望在访问完当前节点后 储存当前节点 的左节点和右节点 以便下次循环进取出进行打印 因此 节点储存的顺序必须为先储存 左节点 再储存右节点 以上图的树为例 当用队列时 会先访问 A 节点 然后储存 B 到 队列 再储存 C 到队列 此时 队列中的元素为 BC 下次循环时 会把 B 出列 访问完 B 后 再储存 E 和 F 此时 队列中的元素为 CEF 下次循环时 会把 C 出列进行访问 显然 这种访问顺序 A B C 不是正确的访问顺序 正确的应该是 A B E 因此队列并不能满足要求 接下来用栈进行储存尝试 当使用栈时 由于栈的特性为后进先出 故在第一次循环 时 先访问 A 然后把 C 入栈 再把 B 入栈 这时栈中的元素为 CB 下次循环时 把 B 出 栈进行访问 然后把 F 入栈 再把 E 入栈 这时 访问顺序为 A B E F C 因此 我们可以 用栈来作为循环遍历时的储存数据结构 此时 每轮循环的步骤就很清晰了 如果栈非空 出栈一个元素作为当前节点 先访问或者打印当前节点 接着 如果当前节点有左儿子或 者右儿子 则先把右儿子入栈 再把左儿子入栈然后进入下次循环 如果当前节点没有儿 子 则直接进入下次循环 具体代码如下 void preorderTraversal Tree tree Stack stack createStack 10 push tree stack while isStackEmpty stack TreePosition node pop stack printf d node element if node right NULL push node right stack if node left NULL push node left stack 2 中根遍历 中根遍历中 先访问当前节点的左儿子 再访问当前节点 最后访问右儿子 上图的树中 中根遍历的顺序为 D B F E A C 在中根遍历过程中 要访问当前节点 首先要访问当前节点的左节点 而如果左节点又有左节点 则会一直向左下去 比如要访 问 A 则首先要访问 B 要访问 B 则要先访问 E 因此 在循环遍历开始前 可以先将 A 以 及其左边的节点全部压入栈中 此时 栈中的元素为 ABD 然后开始循环遍历 在循环中 先从栈中弹出一个节点 访问该节点 然后判断该节点是否有右节点 如果有右节点 则 把其右子树中右节点开始的所有左节点压入栈中 这样 下一次循环就能访问到右节点所 在子树的最左边节点了 因为要访问右节点 必须先访问右节点的左子树中的最左边的元 素 比如上图的树中 在弹出 B 的时候 访问 B 然后 B 有右节点 E 因此 把 EF 都入栈 然后开始下一次循环 下一次循环开始时 就能取出 F 进行访问了 具体代码如下 中序遍历 void inorderTraversal Tree tree Stack stack createStack 30 if tree NULL printf the tree is NULL can t traversal n else pushLeftToStack tree stack while isStackEmpty stack TreePosition node pop stack printf d node element if node right pushLeftToStack node right stack printf n 其中的 pushLeftToStack 方法从该节点开始 一直向左 把左节点全部压入栈中 代码 如下 static void pushLeftToStack Tree tree Stack stack while tree push tree stack tree tree left 3 后根非递归遍历 后根遍历中 先访问当前节点的左儿子 再访问右儿子 最后才访问当前节点 在上 图的树中 访问的顺序为 D F E B C A 要实现非递归遍历 必须明确每一次循环中要进行 的操作 和中根遍历相似 在循环开始前应该先把根节点开始 一直向左的节点压入栈中 然后再开始循环 循环开始时先出栈一个节点 如果该节点没有右儿子 那么就可以直接 访问 该节点了 但如果该节点有右儿子 那么就还不能访问该节点 必须先访问完该节点的右 子树 如上图中 先弹出 D 由于 D 没有右儿子 则可以直接访问 进入下一次循环 但 弹出 B 时 由于 B 有右儿子 E 那么此时还不能访问 B 因此要将 B 重新压回栈中 然后 再把 EF 入栈 这里的问题在于 当访问完 FE 后 又回把 B 重新出栈 如果按照刚才的做 法 由于 B 还是有右儿子 这样 B 又会重新压入栈 同时 EF 也会再次入栈 这样就会造 成无限循环 一种解决这种无限循环的方式是 访问完 D 后 出栈 B 由于 B 有右儿子 为了避免后面的无限循环 可以在把 B 重新入栈时 先用临时变量 T 保存 B 的右儿子 然 后设置 B 的右儿子为空 然后再把 B 入栈 接着再把临时变量 T 作为原 B 的右儿子入栈 这样 再次弹出 B 时 由于 B 的儿子为空了 所以这次会直接访问 B 从而避免了无限循 环 但是这样破坏了树的结构 显然是不好的 因此要寻找另外的办法来避免无限循环 现在的重点是标识出 B 已经被重新压入过一次栈了 也就是说 B 被压了两次栈了 如果可 以标识出来 则在访问完 FE 时 B 重新出栈时 由于 B 已经两次入栈了 故可以直接访问 B 了 在这里采取的做法是 创建多一个栈 设其为 T 第一次弹出 B 时 由于 B 有右儿 子 则把 B 压回到原本的栈中 同时也把 B 压入栈 T 中 这样 每次弹出一个节点时 如 果这个节点有右儿子则先和栈 T 中的最顶元素做下对比 如果和栈 T 中的最顶元素相同 则证明这个有右儿子的节点在之前已经被压入多一次栈了 因此 可以直接访问这个节点 了 在上面例子中 访问完 FE 后 再次把 B 出栈 此时 B 有右儿子 故和栈 T 中的最顶元 素做比较 发现栈 T 中的最顶元素也是 B 因此证明 B 已经被压入过两次了 故可以直接 访问 B 了 访问完 B 后再把栈 T 中的 B 出栈 具体代码如下 后序遍历 void postorderTraversal Tree tree Stack stack createStack 30 Stack tmp createStack 30 保存入栈两次的 有右子树的节点 pushLeftToStack tree stack while isStackEmpty stack TreePosition node pop stack if node right NULL 如果右儿子为空 则直接输出 printf d node element else if isStackEmpty tmp node top tmp push node stack 再次把有右儿子的节点入栈 push node tmp 同时也把该节点压入临时栈中 pushLeftToStack node right stack else 如果该节点两次入栈了 就把它访问并输出 pop tmp printf d node element printf n disposeStack stack disposeStack tmp 3 打印打印树树 为了在终端中打印一棵树 则需要确定在打印一个节点时 前面需要打印多少个空格 在这里 我们可以为每个节点设置一个位置 位置的设置方式如下图 这棵树高为 3 故根节点的位置为 8 这个 8 代表在打印根节点时 需要在其前面打 印 8 1 7 个空格 确定好根节点的位置后 就可以确定其子节点的位置了 从最高的层开始 设置第 1 层所有节点的深度为 0 第 2 层所有节点的深度为 1 依此类推 设某个节点是其父 节点的左儿子 它的位置为 pc 深度为 l 父节点位置为 pp 根节点的位置为 R 则 pc pp R 2 l 如上面的根节点的左儿子的位置为 8 2 1 4 同理 根的右儿子的位置为 8 2 1 12 第 3 层中的第一个节点的位置为 4 8 2 2 4 2 2 这样 只要知道根节点的位置 可 以知道整棵树的位置了 而根节点的位置 R 2 h 其中 h 为树的高度 下面来看具体代码 先是获取树中每个节点的深度和整棵树的高度的代码 在这里 用层序遍历树来进行深 度设置 static int treeHeight 1 static void getLegthOfTree Tree tree Queue parentQueue CreateQueue TRAVERSAL QUEUE SIZE 保存父节点的队 列 Queue childQueue CreateQueue TRAVERSAL QUEUE SIZE 保存子节点的队 列 int leght 0 当前的深度 treeHeight 1 Enqueue tree parentQueue while IsQueueEmpty parentQueue while IsQueueEmpty parentQueue TreePosition node FrontAndDequeue parentQueue 出列 node leght leght if node left NULL Enqueue node left childQueue 把子节点入子队列中 if node right NULL Enqueue node right childQueue 交换父子队列 Queue tempQueue parentQueue parentQueue childQueue childQueue tempQueue leght 每遍历一层 深度加一 treeHeight 树高度加一 DisposeQueue parentQueue DisposeQueue childQueue 接下来是获取树中每个节点的位置的代码 这里同样使用层序遍历来获取每个节点的 位置 static void getPositionOfTree Tree tree Queue parentQueue CreateQueue TRAVERSAL QUEUE SIZE Queue childQueue CreateQueue TRAVERSAL QUEUE SIZE Enqueue tree parentQueue tree position 1 position while IsQueueEmpty parentQueue while IsQueueEmpty parentQueue TreePosition node FrontAndDequeue parentQueue if node left NULL int leftStep topPosition node left leght node left position node position leftStep Enqueue node left childQueue if node right NULL int rightStep topPosition node right leght node right position node position rightStep Enqueue node right childQueue Queue tempQueue parentQueue parentQueue childQueue childQueue tempQueue DisposeQueue parentQueue DisposeQueue childQueue 接下来是打印树的代码 void printTree Tree tree getLegthOfTree tree getPositionOfTree tree printf n Queue parentQueue CreateQueue TRAVERSAL QUEUE SIZE Queue childQueue CreateQueue TRAVERSAL QUEUE SIZE int prePosition 0 Enqueue tree parentQueue while IsQueueEmpty parentQueue while IsQueueEmpty parentQueue TreePosition node FrontAndDequeue parentQueue int spaceNum node position prePosition 1 printSpace spaceNum printf 2d node element prePosition node position if node left NULL Enqueue node left childQueue if node right NULL Enqueue node right childQueue prePosition 0 printf n Queue tempQueue parentQueue parentQueue childQueue childQueue tempQueue DisposeQueue parentQueue DisposeQueue childQueue 4 对对比存比存储储 50 个学生信息的二叉个学生信息的二叉树树和数和数组组的的查查找效率 找效率 二叉树和数组的查找效率是看情况而言的 二叉树的查找效率显然受到插入方式的影 响 可以分多种情况 先设 50 名学生的学号为 0 至 49 二叉树中以学生学号为比较依据 学生结构体如下代 码所示 struct Stu typedef struct Stu int id int score char name Student typedef Student TreeElementType 情况一 情况一 每个学生插入二叉树时 学号是随机的 这样 生成的二叉树比较理想 数 组中储存的学生和插入二叉树中的学生的顺序一样 查找学生时 数组的查找方法是一个 个地遍历来查找 如在二叉树中依次插入学号为 18 24 28 26 44 的学生 那么数组中的第一到第 五个元素也为学号为 18 24 28 26 44 的学生 在这种情况下 显然是二叉树的效率高 因为二叉树中查找需要时间是 O logn 的 而 数组的查找时间是 O n 2 的 下面编写代码测试这种情况 先编写生成随机学号数组的代码 为了生成随机的数组 可以先声明一个 50 元素的数 组 每个元素的初始值依次为 0 到 49 然后遍历数组 根据随机产生的位置来交换数组中的 元素位置 代码如下 void genRandArray int a 50 for int i 0 i 1 i int index rand i swap 随机交换位置 printf 随机数组生成成功 n 然后用随机的学号数组来生成学生数组 然后根据学生数组中学号的顺序来生成二叉 树 先是生成学生数组的代码 void genStudentArray Student students 50 int a 50 a 为学号随机数组 char nameArray 4 Tom Jenny Alice Bob for int i 0 i 50 i char name malloc 6 strcpy name nameArray rand 4 students i createStudent a i 90 rand 10 name 其中 学生的成绩均为 90 到 99 分 名字为 Tom Jenny Alice Bob 中的一个 学 号为 0 至 49 下面是根据学生数组生成二叉树的方法代码 该方法返回一棵和数组一致的树 Tree makeStudentTree Student students 50 Tree tree NULL for int i 0 i 50 i tree insertTreeNode students i tree return tree 查找的方法是进行 N 次的随机查找 统计两种结构的查找时间 每次查找的过程如下 先用随机函数生成五个随机的学号 然后用分别用这个学号执行 N 次查找 然后计算每个 学号查找的平均值 其中查找数组中元素的代码如下 采取的是遍历数组来查找 Student findStudentInArray Student students 50 int id Student student for int i 0 i id id student students i break return student 查找二叉树中元素的代码如下 TreePosition find TreeElementType x SearchTree tree if tree NULL return NULL if x id element id return find x tree left else if x id tree element id return find x tree right else return tree 下面是测试一百万次的代码 define NUM 1000000 int ids 5 for int i 0 i 5 i ids i rand 50 double arrayTimes 5 double treeTimes 5 clock t start finish for int i 0 i 5 i int id ids i start clock for int j 0 j NUM j findStudentInArray students id finish clock arrayTimes i double finish start CLOCKS PER SEC Student st findStudentInArray students id start clock for int k 0 k NUM k find st randTree finish clock treeTimes i double finish start CLOCKS PER SEC for int i 0 i 5 i printf 学号 d 的数组查找用了 f 秒 n ids i arrayTimes i double arrTime average arrayTimes printf 平均时间为 f n arrTime for int i 0 i 5 i printf 学号 d 的二叉树查找用了 f 秒 n ids i treeTimes i double treeTime average treeTimes printf 平均时间为 f n treeTime 经过几次的测试 如下图 发现数组查找的时间基本为二叉树查找的一倍 显然在这 种这种情况下 二叉树的查找效率比数组快 情况二 情况二 考虑一种极端的情况 二叉树按照学号的升序或者降序来插入学生 为了比 较 数组也是按照升序来储存 这样会使二叉树变成一条由左节点或者右节点组成的长链 这种情况下 二叉树中的查找时间就是 O n 2 和数组的遍历查找时间处于同一个数量级 但由于二叉树中的查找是指针操作 比数组操作慢 故二叉树效率会低 以下为测试代码 先生成一个 50 元素的 Student 数组 数组中元素的学号 ID 从 0 开 始 递增到 49 int a 50 for int i 0 i 50 i a i i Student students 50 genStudentArray students a Tree tree makeStudentTree students testTime students tree 其中 testTime 函数中的代码为测试代码 和上一种情况的代码一样 现在只关注测试 时间就行了 测试的时间如下 可以看到 在这种极端情况下 二叉树的查找效率十分差 比数组查找慢一倍多 情况三 情况三 二叉树元素插入的顺序是随机的 数组按学号升序储存学生 但这次数组的 查找算法不同 考虑到数组中的下标就是学号 可以直接通过学号 ID 映射到数组下标来查 找 如果是这样 显然是数组最快 但这种查找算法不太现实 因为现实中的学号都是很 大的 需要很大的数组来储存 因此 为了更一般 这里用二分查找来在有序的数组中查 找学生 二分查找的代码如下 Student binSearchArray Student stud