数据结构课程设计报告 二叉树

PAGE淮阴工学院Project1课程设计报告选题名称:二叉排序树：用顺序表结构存储系（院）: 计 算 机 工 程 学院 专业: 软件工程 班级:软件1092姓名:单重阳学号:1091305206指导教师:殷路张亚红张勇军冯万利学年学期: 2010~2011学年第1学期 2010 年 12 月

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

摘要：数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。本次课程设计，程序中的数据采用“树形结构”作为其数据结构。具体采用的是“二叉排序树”，并且使用“一维数组”来作为其存储结构。一维数组顺序表存储结构是用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素；本课程设计实现了二叉排序树的创建、中序遍历、计算二叉排序树的平均查找长度和删除二叉排序树中某个结点。关键词：二叉排序树；中序遍历；平均查找长度；删除结点

目 录TOC\o"1-2"\h\z\u1需求分析 11.1课程设计题目、任务及要求 11.2课程设计思想 11.3软硬件运行环境及开发工具 12概要设计 22.1二叉排序树的定义 22.2一维数组的存储结构 22.3建立二叉排序树 22.4二叉排序树的生成过程 22.5中序遍历二叉树 32.6二叉排序树的查找 32.7二叉排序树的插入 42.8平均查找长度 43详细设计和实现 53.1主要功能模块设计 53.2主程序设计 64调试与操作说明 74.1程序调试 74.2程序操作说明 8总 结 10致 谢 11参考文献 12PAGEPAGE131需求分析1.1课程设计题目、任务及要求二叉排序树。用顺序表(一维数组)作存储结构(1)以回车('\n')为输入结束标志,输入数列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.3软硬件运行环境及开发工具Windows2000以上操作系统、MicrosoftVisualC++6.02概要设计2.1二叉排序树的定义二叉排序树是一种动态树表。二叉排序树的定义：二叉排序树或者是一棵空树，

或者是一棵具有如下性质的二叉树：⑴若它的左子树非空，则左子树上所有结点的值均小于根结点的值；⑵若它的右子树非空，则右子树上所有结点的值均大于根结点的值；⑶左、右子树本身又各是一棵二叉排序树。2.2一维数组的存储结构建立二插排序树，首先用一个一维数组记录下读入的数据，然后再用边查找边插入的方式将数据一一对应放在完全二叉树相应的位置，为空的树结点用“0”补齐。2.3建立二叉排序树从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点指针，b为当前待插入元素，其过程可以描述为：若为空树（p=nil），动态生成一个结点，其数据域为当前待插入元素b，左、右指针域为“空”，p指向该结点。若非空树，比较b与根结点数据data（p）如果b＜data(p),将b插入左子树中；如果b≥data（p），将b插入右子树中；左、右子树的插入方式与二叉排序树的插入方式相同。不断调用上述的插入过程，直到所有待排序序列均排入后，就形成一棵二叉排序树。由此可见，建立二叉排序树就是多次调用二叉排序树的插入算法。2.4二叉排序树的生成过程二叉排序树的生成，采用递归方式的边查找边插入的方式。如图：插入结点插入结点在左子树中查找在右子树中查找空树插入初始化数组是是否否插入插入图2.4.1二叉排序树生成流程图2.5中序遍历二叉树中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则中序遍历左子树（L）；访问根结点（V）；中序遍历右子树（R）。中序遍历二叉树也采用递归函数的方式，先访问左子树2i,然后访问根结点i,最后访问右子树2i+1.先向左走到底再层层返回，直至所有的结点都被访问完毕。2.6二叉排序树的查找在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较叛等的过程。它可以是一个递归的过程。假设我们想要在二叉排序树中查找关键码为x的元素，查找过程从根结点开始。如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键码进行比较；如果给定值等于根结点的关键码，则查找成功，返回查找成功的信息，并报告查找到的结点地址。如果给定值小于根结点的关键码，则继续递归查找根结点的左子树；否则，递归搜索根结点的右子树。2.7二叉排序树的插入在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。为了向二叉排序树中插入一个新元素，必须先检查这个元素是否在树中已经存在。所以在插入之前，先使用查找算法在树中检查要插入的元素有还是没有。如果搜索成功，说明树中已经有这个元素，不再插入；如果搜索不成功，说明树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。

插入过程：若二叉排序树为空，则待插入结点*S作为根结点插入到空树中；

当非空时，将待插结点关键字S->key和树根关键字t->key进行比较，

若s->key=t->key,则无须插入，若s->key<t->key,则插入到根的左子树中，

若s->key<>t->key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。2.8平均查找长度计算二叉排序树的平均查找长度时，采用类似中序遍历的递归方式，用s记录总查找长度，j记录每个结点的查找长度，s置初值为0，采用累加的方式最终得到总查找长度s。平均查找长度就等于s/i(i为树中结点的总个数)。

假设在含有n(n>=1)个关键字的序列中，i个关键字小于第一个关键字，n-i-1个关键字大于第一个关键字，则由此构造而得的二叉排序树在n个记录的查找概率相等的情况下，其平均查找长度为：

ASL(n,i)=[1+i*(P(i)+1)+(n-i-1)(P(n-i-1)+1)]/n

其中P(i)为含有i个结点的二叉排序树的平均查找长度，则P(i)+1为查找左子树中每个关键字时所用比较次数的平均值，P（n-i-1）+1为查找右子树中每个关键字时所用比较次数的平均值。又假设表中n个关键字的排列是“随机”的，即任一个关键字在序列中将是第1个，或第2个，…，或第n个的概率相同，则可对上式从i等于0至n-1取平均值。最终会推导出：

当n>=2时，ASL(n)<=2(1＋1/n)ln(n)由此可见，在随机的情况下，二叉排序树的平均查找长度和log（n）是等数量级的。另外，含有n个结点的二叉排序树其判定树不是惟一的。对于含有同样一组结点的表，由于结点插入的先后次序不同，所构成的二叉排序树的形态和深度也可能不同。3详细设计和实现3.1主要功能模块设计程序主要设计了五个功能：首先是创建二叉排序树，完成后出现任务菜单，菜单中设计了四个模块：退出，中序遍历，计算平均查找长度和删除结点。主函数流程如下：否否否否否否是创建二叉排序树Switch(1)中序遍历Switch(0)Exit(0)退出Switch(3)删除结点Switch(2)default提示出错计算平均查找长度是是是是是是是是是图3.1.1主函数流程图3.2主程序设计voidmain(){BSTT;intcrew[N];inti=0;intnum,ch=0,j;cout<<"请输入以数字0为结束标志的一组数列:"<<endl;do{cin>>num;if(!num)cout<<"输入完成!"<<endl;else{crew[i]=num;i++;}}while(num);T=create(crew,i);cout<<"\n\n主程序菜单\n";/*主程序菜单*/cout<<"\n0:退出";cout<<"\n1:中序遍历";cout<<"\n2:计算平均查找长度";cout<<"\n3:删除结点"; cout<<"\n\n\n"; while(ch==ch){cout<<"\n选择命令:";cin>>ch;switch(ch) {case0:exit(0);/*0－退出*/case1:cout<<"中序遍历为:\n"; cout<<"";inordertraverse(T,1);/*1－中序遍历*/break;case2:j=0;computeASL(T,1,&j,0);/*2－计算平均查找长度*/cout<<"ASL(平均查找长度)="<<j<<"/"<<i<<"="<<j/i;break;case3:cout<<"请输入需要删除的结点:";cin>>num;/*3－删除某个结点*/j=search(T,num,1);if(j){T=remove(T,num);cout<<"\n删除成功!\n"; cout<<"新的中序遍历为:\n"; cout<<"";inordertraverse(T,1);i--;}else cout<<"查找不到"<<num<<"这个结点";break;default:cout<<"请重新输入!\n"<<endl<<endl;break;/*输入无效字符*/}}}4调试与操作说明4.1程序调试图4.1.1调试界面在程序调试过程当中，编译时并没有报错，但是运行时总是出错，在查阅资料和老师的帮助下，发现程序未对数组初始化。添加数组初始化代码：T.data=(int*)malloc(N*sizeof(int));4.2程序操作说明1）输入一组数列，以结0结束：图4.2.1运行界面一2）中序遍历：图4.2.2运行界面二3）计算平均查找长度：图4.2.3运行界面三3）删除已有结点：图4.2.4运行界面四总 结这次课程设计是我学会了用顺序表结构存储实现二叉排序树，具体采用的是“二叉排序树”，并且使用“一维数组”来作为其存储结构。一维数组顺序表存储结构是用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素；本课程设计实现了二叉排序树的创建、中序遍历、计算二叉排序树的平均查找长度和删除二叉排序树中某个结点,通过一周的课程设计，我已经会用顺序表存储结构实现对二叉排序树的的创建，中序遍历，并计算其平均查找长度，查找和某个删除结点等基本操作。致 谢本次数据结构课程设计让我收获很多，我从指导老师身上学到了很多东西。他们认真负责的工作态度，严谨的治学精神和深厚的理论水平都使我收益匪浅。无论在理论上还是在实践中，都给与我很大的帮助，使我得到很大的提高，这对于我以后的工作和学习都有一种巨大的帮助，在此感谢他耐心的辅导。在撰写论文阶段，老师审阅我们的论文，提出了许多宝贵意见，没有他的指导，我们就不能较