数据结构课程设计报告 - 二叉排序树(用顺序表结构存储)

更新时间:2023-12-24 15:13:01 阅读量: 教育文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

淮阴工学院

数据结构课程设计报告

选题名称: 二叉排序树(二叉链表结构存储) 系(院): 计 算 机 工 程 系 专 业: 计算机科学与技术 班 级: 计算机1091 姓 名: 黄磊 学 号: 1091301108 指导教师: 张亚红 周海岩 学年学期: 2010 ~ 2011 学年 第 1 学期

2010 年 12 月 31 日

设计任务书

课题 名称 二叉排序树:用顺序表结构存储 通过一周的课程设计,用二叉链表存储结构实现对二叉排序树的的创建,中序设计 遍历,并计算其平均查找长度,查找和某个删除结点等基本操作,达到巩固和目的 运用理论知识、锻炼实践能力、构件合理知识结构和提高程序设计能力的目的。 实验 环境 Windows2000 以上操作系统 Visual C++6.0以上编译环境 1、搜集二叉排序树方面的资料; 2、编写代码,实现二叉排序树的创建,中序遍历,计算其平均查找长度,任务 要求 查找和删除某个结点; 3、撰写课程设计报告; 4、参加答辩。 工作进度计划 序号 1 2 3 4 起止日期 2010.12.23~2010.12.27 2010.12.27~2010.12.29 2010.12.30 2010.12.30~2010.12.31 工 作 内 容 搜集二叉排序树方面的资料 编写代码,上机调试 撰写课程设计报告 答辩 指导教师(签章): 2010 年 12 月 31 日

摘要:

数据结构是研究与数据之间的关系,我们称这一关系为数据的逻辑结构,简称数据结构。当数据的逻辑结构确定以后,数据在物理空间中的存储方式,称为数据的存储结构。相同的逻辑结构可以具有不同的存储结构,因而有不同的算法。本次课程设计,程序中的数据采用“树形结构”作为其数据结构。而二叉搜索树又是一种特殊的二叉树。本课程设中的二叉排序树是基于二叉链表作存储结构的,一共要实现五项基本的功能。它们分别是二叉搜索树的创建、中序遍历、查找结点、删除结点和计算二叉排序树搜索成功时的平均查找长度。

关键词:二叉排序树;中序遍历;搜索结点;删除结点;平均查找长度

目 录

1需求分析 .................................................................................................................... 1

1.1课程设计题目、任务及要求 ························ 1 1.2课程设计思想 ······························ 1

2概要设计 .................................................................................................................... 2

2.1 二叉排序树的定义 ···························· 2 2.2二叉链表的存储结构 ··························· 2 2.3建立二叉排序树 ····························· 2 2.4二叉排序树的生成过程 ·························· 3 2.5中序遍历二叉树 ····························· 3 2.6二叉排序树的查找 ···························· 3 2.7二叉排序树的插入 ···························· 4 2.8平均查找长度 ······························ 4

3详细设计和实现 ........................................................................................................ 4

3.1主要功能模块设计 ···························· 4 3.2主程序设计 ······························· 5

4调试与操作说明 ...................................................................................................... 12

4.1程序调试 ······························· 12 4.2程序操作说明 ····························· 12

总 结 ................................................................................................................. 16 致 谢 ................................................................................................................. 17 参 考 文 献 ............................................................................................................... 18

1需求分析

1.1课程设计题目、任务及要求

二叉排序树。用二叉链表作存储结构

(1)以(0)为输入结束标志,输入数列L,生成一棵二叉排序树T; (2)对二叉排序树T作中序遍历,输出结果;

(3)计算二叉排序树T查找成功的平均查找长度,输出结果;

(4)输入元素x,查找二叉排序树T:若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息“无x”;

1.2课程设计思想

建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找成功则不应再插入原树,否则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。

对二叉排序树进行中序遍历采用递归函数的方式。在根结点不为空的情况下,先访问左子树,再访问根结点,最后访问右子树。由于二叉排序树自身的性质,左子树小于根结点,而根结点小于右子树,所以中序遍历的结果是递增的。

计算二插排序树的平均查找长度时,仍采用类似中序遍历的递归方式,用s记录总查找长度,j记录每个结点的查找长度,s置初值为0,采用累加的方式最终得到总查找长度s。平均查找长度就等于s/i(i为树中结点的总个数)。

删除结点函数,采用边查找边删除的方式。如果没有查找到,则不对树做任何的修改;如果查找到结点,则分四种情况分别进行讨论:

1、该结点左右子树均为空; 2、该结点仅左子树为空; 3、该结点仅右子树为空; 4、该结点左右子树均不为空。

1

2概要设计

2.1 二叉排序树的定义

二叉排序树是一种动态树表。

二叉排序树的定义:二叉排序树或者是一棵空树, 或者是一棵具有如下性质的二叉树:

(1)每个结点都有一个作为搜索依据的关键码(key),所有结点的关键码互不

相同;

(2) 若它的左子树非空,则左子树上所有结点的值均小于根结点的值; (3) 若它的右子树非空,则右子树上所有结点的值均大于根结点的值; (4) 左、右子树本身又各是一棵二叉排序树。

2.2二叉链表的存储结构

建二叉树的结点至少应当包含三个域,分别存放结点的数据data,左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针,它指向二叉树的根结点,其作用是当作树的访问点。

2.3建立二叉排序树

从空的二叉排序树开始,经过一系列的查找插入操作以后,生成了一棵二叉排序树。

根据二叉排序树的定义,建立一棵二叉排序树的过程是按照待排序序列元素的先后次序,不断动态生成二叉树的结点,逐个插入到二叉树中。若p为根结点指针,b为当前待插入元素,其过程可以描述为:

(1) 若为空树(p=nil),动态生成一个结点,其数据域为当前待插入元素

b,左、右指针域为“空”,p指向该结点。

(2) 若非空树,比较b与根结点数据data(p)

如果b

左、右子树的插入方式与二叉排序树的插入方式相同。 不断调用上述的插入过程,直到所有待排序序列均排入后,就形成一棵二叉排序树。

由此可见,建立二叉排序树就是多次调用二叉排序树的插入算法。

2

2.4二叉排序树的生成过程

二叉排序树的生成,采用递归方式的边查找边插入的方式。如图:

图2.4.1 二叉排序树生成流程图

空树 否 是 插入 插入结点 初始化 在左子树中查找 否 在右子树中查找 是 插入 插入 2.5中序遍历二叉树

中序遍历二叉树算法的框架是: 若二叉树为空,则空操作;否则

(1) 中序遍历左子树(L); (2) 访问根结点(V); (3) 中序遍历右子树(R)。

中序遍历二叉树也采用递归函数的方式,先访问左子树,然后访问根结点,最后访问右子树.直至所有的结点都被访问完毕。

2.6二叉排序树的查找

在二叉排序树上进行查找,是一个从根结点开始,沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设我们想要在二叉排序树中查找关键码为x的元素,查找过程从根结点开始。如果根指针为NULL,则查找不成功;否则用给定值x与根结点的关键码进行比较;如果给定值等于根

3

结点的关键码,则查找成功,返回查找成功的信息,并报告查找到的结点地址。如果给定值小于根结点的关键码,则继续递归查找根结点的左子树;否则,递归搜索根结点的右子树。

2.7二叉排序树的插入

为了向二叉排序树中插入一个新元素,必须先检查这个元素是否在树中已经存在。所以在插入之前,先使用查找算法在树中检查要插入的元素有还是没有。如果搜索成功,说明树中已经有这个元素,不再插入;如果搜索不成功,说明树中原来没有关键码等于给定值的结点,把新元素加到搜索操作停止的地方。

插入过程:若二叉排序树为空,则待插入结点*s作为根结点插入到空树中; 当非空时,将待插结点关键字s->data和树根关键字subtree->data进行比较, 若s->data= subtree-> data,则无须插入,若s-> data data,则插入到根的左子树中,

若s-> data > subtree-> data,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同,如此进行下去,直到把结点*s作为一个新的树叶插入到二叉排序树中,或者直到发现树已有相同关键字的结点为止。

2.8平均查找长度

计算二叉排序树的平均查找长度时,采用类似先序遍历的递归方式,用count记录所有结点的总深度,deep记录每个结点的深度,count置初值为0,采用累加的方式最终得到所有结点总深度count。平均查找长度就等于count/i(i为树中结点的总个数)。

3详细设计和实现

3.1主要功能模块设计

程序主要设计了五个功能:首先是创建二叉排序树,完成后出现任务菜单,菜单中设计了四个模块:退出,中序遍历,搜索,删除结点和计算平均查找长度,另外还有一个附加功能计算所有结点的个数,用来计算平均查找长度。

主函数流程如下:

4

创建二叉排序树 Switch(0) 否 Switch(1) 否 Switch(2) 否 Switch(3) 否 Switch(4) 是 平均搜索长度 是 删除结点 是 是 搜索结点 是 是 中序遍历 是 是 Exit(0)退出 是

否 图3.1.1主函数流程图 3.2主程序设计

void main () {

int deep;

cout<<\输入一组数据建立二叉搜索树,以0结束\BinaryTreebr(0);

BinTreeNode*subtree=br.GetRoot (); int choicenumber;

char flag; //判断是否还要继续进行 int number; int number2; while(1) {

show(); //显示主要功能

5

cout<<\请选择你要进行的操作:1~5\cin>>choicenumber; switch(choicenumber) { case 0:

exit(0);break;

case 1:

cout<<\显示树的结点:\br.print ();break;

case 2:

cout<<\结点个数为:\

cout<<\ \

case 3:

cout<<\输入要查找的数:\cin>>number;

if(br.search (number)==NULL)

cout<<\没有找到\

else

cout<<\找到\break;

case 4:

cout<<\输入你要删除的结点:\cin>>number2;

if(br.search (number2)!=NULL) { } else

cout<<\你要删除的结点不存在!\br.remove (number2);

cout<<\删除结点后的二叉搜索树为:\br.print ();

break;

6

if(key==subtree->data)

return subtree;

else if(keydata)return search(key,subtree->leftChild); //若比该结点小,那就向它的左子树继续搜索

else if(key>subtree->data)return search(key,subtree->rightChild); ////若比该结点大,那就向它的右子树继续搜索

else return subtree;

};

// ******* 输出二叉树结点数 ******** template

int BinaryTree::Size (BinTreeNode*subtree) { //计算以*subtree为根的二叉树的结点数 if(subtree==NULL)

return 0; else

return 1+Size(subtree->leftChild)+Size(subtree->rightChild); }; #endif

4调试与操作说明

4.1程序调试

图4.1.1 调试界面

4.2程序操作说明

1)输入一组数列,以结0结束:

12

//左子树的

图4.2.1运行界面一

2)中序遍历:

图4.2.2运行界面二

3)计算搜索成功时的平均查找长度:

13

图4.2.3运行界面三

4)查找结点:

图4.2.4运行界面四

5)查找不存在的结点

图4.2.5运行界面五

6)删除已有结点:

14

图4.2.6运行界面六

7)删除结点后的平均搜索长度:

图4.2.7运行界面七

15

总 结

这次课程设计使我对数据结构认识深刻了许多,其中最深刻的是我理解了用二叉链表结构存储实现二叉排序树,同时也加深了对二叉树的理解。本课程设计实现了二叉排序树的创建、中序遍历、计算二叉排序树的平均查找长度和删除二叉排序树中某个结点,。在进行搜索时,还可以采用更好的搜索结构即动态搜索结构。当没有找到时,可以将其插入,而不是仅仅提示未找到。在进计算查找成功时的平均查找长度,使用递归的方法虽然短小,但很难理解,可以采用层次遍历来统计所有结点的深度之和,这样就更容易理解。在此课题中,我遇到最大的一个问题就是如何求搜索成功时平均搜索长度?最后通过加上deep来记录每一结点的深度给解决啦,可是又出现了另外一个新的问题,当删除结点后再求平均搜索长度却又错啦?最后通过单步调试发现,当进行完一次计算平均搜索长度后,count(用来记录所有结点深度和)会随着下一次计算时同步增长。那就必须要在每进行完一次计算后,给count做清零处理!于是我就在类中加了一个对count 清零处理的函数,int GetCount(){ count=0;return count;} 。从而解决了这个最大的难题。通过一周的课程设计,我已经会用二叉链表存储结构实现对二叉排序树的的创建,中序遍历,并计算其平均查找长度,查找和某个删除结点等基本操作。

但我同时也发现了自己许多不足之处 。

首先,对数据结构的掌握还不够。虽然完成了程序,但是只用到了基本的结点以及链表,在数据结构的选择上避重就轻,覆盖面较小,不能很好的体现各种数据结构的掌握度,同时也缺少了适当的锻炼,在这方面还需要自己主动去提高。

其次,在程序整体的设计上还不够完善,各模块可以适当增加内容,界面还可以更加的人性化些,这样整个程序才具有更强的美观性与实用性。

总而言之,这次课程设计给了我很大启发,我明白了,不管遇到什么问题,只要抓住根源,不气馁,从不同方面去攻破它,终究会成功,生活也是如此。

16

本文来源:https://www.bwwdw.com/article/wu35.html

Top