数据结构课程设计报告二叉排序树用顺序表结构存储.docx
《数据结构课程设计报告二叉排序树用顺序表结构存储.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告二叉排序树用顺序表结构存储.docx（23页珍藏版）》请在冰点文库上搜索。
数据结构课程设计报告二叉排序树用顺序表结构存储
淮阴工学院
数据结构课程设计报告
选题名称:
二叉排序树（二叉链表结构存储）
系（院）:
计算机工程系
专业:
计算机科学与技术
班级:
计算机1091
姓名:
黄磊学号:
1091301108
指导教师:
张亚红周海岩
学年学期:
2010~2011学年第1学期
2010年12月31日
设计任务书
课题
名称
二叉排序树：
用顺序表结构存储
设计
目的
通过一周的课程设计，用二叉链表存储结构实现对二叉排序树的的创建，中序遍历，并计算其平均查找长度，查找和某个删除结点等基本操作，达到巩固和运用理论知识、锻炼实践能力、构件合理知识结构和提高程序设计能力的目的。
实验
环境
Windows2000以上操作系统
VisualC++6.0以上编译环境
任务
要求
1、搜集二叉排序树方面的资料；
2、编写代码，实现二叉排序树的创建，中序遍历，计算其平均查找长度，查找和删除某个结点；
3、撰写课程设计报告；
4、参加答辩。
工作进度计划
序号
起止日期
工作内容
1
2010.12.23~2010.12.27
搜集二叉排序树方面的资料
2
2010.12.27~2010.12.29
编写代码，上机调试
3
2010.12.30
撰写课程设计报告
4
2010.12.30~2010.12.31
答辩
指导教师（签章）：
2010年12月31日
摘要：
数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据结构。
当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。
相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。
本次课程设计，程序中的数据采用“树形结构”作为其数据结构。
而二叉搜索树又是一种特殊的二叉树。
本课程设中的二叉排序树是基于二叉链表作存储结构的，一共要实现五项基本的功能。
它们分别是二叉搜索树的创建、中序遍历、查找结点、删除结点和计算二叉排序树搜索成功时的平均查找长度。
关键词：
二叉排序树；中序遍历；搜索结点；删除结点；平均查找长度
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、该结点左右子树均不为空。
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如果b≥data（p），将b插入右子树中；
左、右子树的插入方式与二叉排序树的插入方式相同。
不断调用上述的插入过程，直到所有待排序序列均排入后，就形成一棵二叉排序树。
由此可见，建立二叉排序树就是多次调用二叉排序树的插入算法。
2.4二叉排序树的生成过程
二叉排序树的生成，采用递归方式的边查找边插入的方式。
如图：
图2.4.1二叉排序树生成流程图
2.5中序遍历二叉树
中序遍历二叉树算法的框架是：
若二叉树为空，则空操作；否则
（1）中序遍历左子树（L）；
（2）访问根结点（V）；
（3）中序遍历右子树（R）。
中序遍历二叉树也采用递归函数的方式，先访问左子树,然后访问根结点,最后访问右子树.直至所有的结点都被访问完毕。
2.6二叉排序树的查找
在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。
它可以是一个递归的过程。
假设我们想要在二叉排序树中查找关键码为x的元素，查找过程从根结点开始。
如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键码进行比较；如果给定值等于根结点的关键码，则查找成功，返回查找成功的信息，并报告查找到的结点地址。
如果给定值小于根结点的关键码，则继续递归查找根结点的左子树；否则，递归搜索根结点的右子树。
2.7二叉排序树的插入
为了向二叉排序树中插入一个新元素，必须先检查这个元素是否在树中已经存在。
所以在插入之前，先使用查找算法在树中检查要插入的元素有还是没有。
如果搜索成功，说明树中已经有这个元素，不再插入；如果搜索不成功，说明树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。
插入过程：
若二叉排序树为空，则待插入结点*s作为根结点插入到空树中；
当非空时，将待插结点关键字s->data和树根关键字subtree->data进行比较，
若s->data=subtree->data,则无须插入，若s->datadata,则插入到根的左子树中，
若s->data>subtree->data,则插入到根的右子树中。
而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。
2.8平均查找长度
计算二叉排序树的平均查找长度时，采用类似先序遍历的递归方式，用count记录所有结点的总深度，deep记录每个结点的深度，count置初值为0，采用累加的方式最终得到所有结点总深度count。
平均查找长度就等于count/i（i为树中结点的总个数）。
3详细设计和实现
3.1主要功能模块设计
程序主要设计了五个功能：
首先是创建二叉排序树，完成后出现任务菜单，菜单中设计了四个模块：
退出，中序遍历，搜索，删除结点和计算平均查找长度，另外还有一个附加功能计算所有结点的个数，用来计算平均查找长度。
主函数流程如下：
图3.1.1主函数流程图
3.2主程序设计
voidmain（）
{
intdeep;
cout<<"输入一组数据建立二叉搜索树，以0结束"<BinaryTreebr（0）;
BinTreeNode*subtree=br.GetRoot（）;
intchoicenumber;
charflag;//判断是否还要继续进行
intnumber;
intnumber2;
while
（1）
{
show（）;//显示主要功能
cout<<"请选择你要进行的操作：
1~5"<cin>>choicenumber;
switch（choicenumber）
{
case0:
exit（0）;break;
case1:
cout<<"显示树的结点：
"<br.print（）;break;
case2:
cout<<"结点个数为：
";
cout<<""<case3:
cout<<"输入要查找的数：
";
cin>>number;
if（br.search（number）==NULL）
cout<<"没有找到"<else
cout<<"找到"<break;
case4:
cout<<"输入你要删除的结点:
"<cin>>number2;
if（br.search（number2）!
=NULL）
{
br.remove（number2）;
cout<<"删除结点后的二叉搜索树为：
"<br.print（）;
}
else
cout<<"你要删除的结点不存在!
"<break;
case5:
deep=0;
doubleasl;
asl=br.Height（subtree,deep）/（br.Size（）*1.0）;
cout<<"二叉排序树查找成功的平均查找长度:
"<br.GetCount（）;//在每次计算平均长度之后都将count置零
break;
default:
break;
}
cout<<"你是否要继续（Y/N）?
"<cin>>flag;
if（flag=='N'||flag=='n'）break;
}
}
template
structBinTreeNode//二叉树结点类定义
{
Edata;//数据域
BinTreeNode*leftChild,*rightChild;//左子女、右子女链域
BinTreeNode（Ex,BinTreeNode*l=NULL,BinTreeNode*r=NULL）
{
data=x;
leftChild=l;
rightChild=r;
}
};
//二叉排序树类定义
template
classBinaryTree
{
private:
intcount;//用来表示所有结点的深度之和
BinTreeNode*root;//二叉树根结点指针
KRefvalue;//输入停止标志
intSize（BinTreeNode*subtree）;//结点的个数
boolinsert（E&t,BinTreeNode*&subtree）;//插入结点
voidprint（BinTreeNode*subtree）;//显示二叉搜索树的结点
BinTreeNode*search（Kkey,BinTreeNode*subtree）;//递归：
搜索
boolremove（Kkey,BinTreeNode*&subtree）;//在树中删除一个含k的结点
public:
BinaryTree（）{root=NULL;}
BinaryTree（Kvalue）;//构造函数
~BinaryTree（）{};//析构函数
BinTreeNode*GetRoot（）{returnroot;}//返回头指针
intGetCount（）{count=0;returncount;}//将count置零
boolsearch（Kkey）{returnsearch（key,root）!
=NULL?
true:
false;}//递归：
搜索
boolinsert（E&t）{returninsert（t,root）;}//插入结点
intSize（）{returnSize（root）;}//返回二叉树的结点数
voidprint（）{print（root）;}//显示二叉搜索树的结点
boolremove（Kk）{returnremove（k,root）;}//在树中删除一个值
intHeight（BinTreeNode*subtree,intdeep）;//高度
};
//******建立二叉搜索树的算法*****
template
BinaryTree:
:
BinaryTree（Kvalue）
{//输入一个元素序列，建立一颗二叉搜索树
Kx;
count=0;
root=NULL;
Refvalue=value;
cout<<"输入数据：
"<cin>>x;
while（x!
=Refvalue）//Refvalue是一个输入结束标志
{
insert（x,root）;//插入，再输入数据
cin>>x;
}
};
//********计算所有结点的深度之和即所在的层次之和*********
template
intBinaryTree:
:
Height（BinTreeNode*subtree,intdeep）
{
if（subtree）
{
deep++;//记录当前结点的在当前树中的深度
count=count+deep;//记录已遍历过的点的深度之和
Height（subtree->leftChild,deep）;
Height（subtree->rightChild,deep）;
}
returncount;
};
//********显示二叉搜索树的结点********
template
voidBinaryTree:
:
print（BinTreeNode*subtree）//利用的是中序输出，输出后的数是按照从小到大的顺序排列的
{
if（subtree!
=NULL）
{
print（subtree->leftChild）;
cout<<""<data<print（subtree->rightChild）;
}
};
//********插入结点t*********
template
boolBinaryTree:
:
insert（E&t,BinTreeNode*&subtree）
{
if（subtree==NULL）
{
subtree=newBinTreeNode（t）;
returntrue;
}
elseif（tdata）
{
insert（t,subtree->leftChild）;
returntrue;
}
elseif（t>subtree->data）
{
insert（t,subtree->rightChild）;
returntrue;
}
elsereturnfalse;
returnfalse;
};
//********删除节点k**********
template
boolBinaryTree:
:
remove（Kk,BinTreeNode*&subtree）
{
BinTreeNode*temp;
if（subtree!
=NULL）
{
if（kdata）
remove（k,subtree->leftChild）;
elseif（k>subtree->data）
remove（k,subtree->rightChild）;
elseif（subtree->leftChild!
=NULL&&subtree->rightChild!
=NULL）
{
//subtree指示关键码为k的结点，它有两个结点，在右子树树上找中序第一个子女填补
temp=subtree->rightChild;//到右子树树上找中序第一个子女填补
while（temp->leftChild!
=NULL）
temp=temp->leftChild;
subtree->data=temp->data;//用该结点数据代替删除结点数据
remove（subtree->data,subtree->rightChild）;//继续向右子树查找，将树连接好
}
else
{//subtree指示关键码为k的结点，它只有一个孩子子树或零个子树
temp=subtree;
if（subtree->leftChild==NULL）
subtree=subtree->rightChild;
else
subtree=subtree->leftChild;
deletetemp;returntrue;
}
}
returnfalse;
};
//*********查找关键字为k*********
template
BinTreeNode*BinaryTree:
:
search（Kkey,BinTreeNode*subtree）
{
if（subtree==NULL）
returnNULL;
if（key==subtree->data）
returnsubtree;
elseif（keydata）returnsearch（key,subtree->leftChild）;//若比该结点小，那就向它的左子树继续搜索
elseif（key>subtree->data）returnsearch（key,subtree->rightChild）;////若比该结点大，那就向它的右子树继续搜索
elsereturnsubtree;
};
//*******输出二叉树结点数********
template
intBinaryTree:
:
Size（BinTreeNode*subtree）
{//计算以*subtree为根的二叉树的结点数
if（subtree==NULL）
return0;
else
return1+Size（subtree->leftChild）+Size（subtree->rightChild）;//左子树的
};
#endif
4调试与操作说明
4.1程序调试
图4.1.1调试界面
4.2程序操作说明
1）输入一组数列，以结0结束：
图4.2.1运行界面一
2）中序遍历：
图4.2.2运行界面二
3）计算搜索成功时的平均查找长度：
图4.2.3运行界面三
4）查找结点：
图4.2.4运行界面四
5）查找不存在的结点
图4.2.5运行界面五
6）删除已有结点：
图4.2.6运行界面六
7）删除结点后的平均搜索长度：
图4.2.7运行界面七
总结
这次课程设计使我对数据结构认识深刻了许多，其中最深刻的是我理解了用二叉链表结构存储实现二叉排序树，同时也加深了对二叉树的理解。
本课程设计实现了二叉排序树的创建、中序遍历、计算二叉排序树的平均查找长度和删除二叉排序树中某个结点,。
在进行搜索时，还可以采用更好的搜索结构即动态搜索结构。
当没有找到时，可以将其插入，而不是仅仅提示未找到。
在进计算查找成功时的平均查找长度，使用递归的方法虽然短小，但很难理解，可以采用层次遍历来统计所有结点的深度之和，这样就更容易理解。
在此课题中，我遇到最大的一个问题就是如何求搜索成功时平均搜索长度？
最后通过加上deep来记录每一结点的深度给解决啦，可是又出现了另外一个新的问题，当删除结点后再求平均搜索长度却又错啦？
最后通过单步调试发现，当进行完一次计算平均搜索长度后，count（用来记录所有结点深度和）会随着下一次计算时同步增长。
那就必须要在每进行完一次计算后，给count做清零处理！
于是我就在类中加了一个对count清零处理的函数，intGetCount（）{count=0；returncount；}。
从而解决了这个最大的难题。
通过一周的课程设计，我已经会用二叉链表存储结构实现对二叉排序树的的创建，中序遍历，并计算其平均查找长度，查找和某个删除结点等基本操作。
但我同时也发现了自己许多不足之处。
首先，对数据结构的掌握还不够。
虽然完成了程序，但是只用到了基本的结点以及链表，在数据结构的选择上避重就轻，覆盖面较小，不能很好的体现各种数据结构的掌握度，同时也缺少了适当的锻炼，在这方面还需要自己主动去提高。
其次，在程序整体的设计上还不够完善，各模块可以适当增加内容，界面还可以更加的人性化些，这样整个程序才具有更强的美观性与实用性。
总而言之，这次课程设计给了我很大启发，我明白了，不管遇到什么问题，只要抓住根源，不气馁，从不同方面去攻破它，终究会成功，生活也是如此。
致谢
本次课程设计中，除了通过自己的努力，同时得到了很多来自他方的帮助，在这里我要谢谢所有帮助过我的老师同学。
首先，我要谢谢淮阴工学院计算机工程系给我提供了这次难得的实践机会，以及实验室
升级会员 