江苏大学C++二叉排序树的建立插入删除和查找免费下载.docx
- 文档编号:11269838
- 上传时间:2023-05-30
- 格式:DOCX
- 页数:23
- 大小:90.62KB
江苏大学C++二叉排序树的建立插入删除和查找免费下载.docx
《江苏大学C++二叉排序树的建立插入删除和查找免费下载.docx》由会员分享,可在线阅读,更多相关《江苏大学C++二叉排序树的建立插入删除和查找免费下载.docx(23页珍藏版)》请在冰点文库上搜索。
江苏大学C++二叉排序树的建立插入删除和查找免费下载
数据结构课程设计实验报告
设计题目:
二叉排序树的建立、插入、删除和查找
学生姓名:
系别:
专业:
班级:
学号:
指导教师:
一、需求分析
1、运行环境
MicrosoftVisualStudio2008
2、程序所实现的功能
二叉排序树的建立、插入、删除和查找
给出一组关键值,建立相应的二叉排序树,完成:
⑴结点的删除操作。
要求可以实现删除根结点、叶子结点以及其它任意结点的功能;
⑵插入一个新结点的操作;
⑶对给定的值在二叉排序树进行查找;
⑷随时显示操作的结果。
3、程序的输入,包含输入的数据格式和说明
程序从外部输入数据,输入一串数字序列并以-1结束
4、程序的输出,及其输出格式
通过用户手动选择操作指令,经由程序内部处理,输
出相应的结果到显示屏
5、测试数据,如果程序输入的数据量比较大,需要给出测试数据
用户手动输入一个数字序列进行数据测试
二、设计说明
1、算法设计的思想
通过算法的需求,确定算法的主要模块(建立并输出二叉树、插入结点、删除结点、查找结点、以及主函数模块)对各模块再进行函数的选取与构造,以及变量的控制等。
最后,再将各模块结合,形成完整的算法,注意全局变量的选择。
2、主要的数据结构设计说明
二叉排序树的主要存储结构
TypedefstructTreeNode//声明数的结构
{
Intkey;//存放关键字
StructTreeNode*left;//存放左子树的指针
StructTreeNode*right;//存放右子树的指针
}treeNode;
3、程序的主要流程图
否是
4、程序的主要模块,要求对流程图中出现的模块说明
*建立二叉树,用插入函数依次插入用户输入的序列,最后再中序遍历并输出显示
*结点的插入,运用递归算法进行结点的插入
*结点的删除,是该算法中较为复杂的一个模块,需判定用户输入的结点是根,还是叶子,这关系到删除的结点在序列中的位置
*结点的查找,在根指针所指二叉排序树中递归查找关键字等于key的数据元素;
若成功,返回指向该数据元素结点的指针;
否则返回空指针;
1)主函数模块
Main()
{
建立n个关键字的二叉排序树并输出;
从二叉树排序树中删除任意结点;
在二叉树排序树中,插入一个结点;
在二叉排序树中递归查找关键字;
}
2)创建二叉排序树模块
treeNode*buildTree(treeNode*head,intnumber)
{
建立n个关键字的二叉排序树;
从键盘输入调建立n个关键字依次用insertTree(intkey);
返回根结点;
输出过程;
}
3)删除模块
deleteTree(intkey)
{
从二叉树排序树中删除任意结点;
可以实现删除根结点、叶子结点以及其它任意结点的功能;
1.若结点p是叶子,则直接删除结点p;
2.若结点p只有左子树,则只需重接p的左子树;
若结点p只有右子树,则只需重接p的右子树;
3.若结点p的左右子树均不空,则
a查找结点p的右子树上的最左下结点(若为s)以及该结点的双亲结点par;
b将结点s数据域替换到被删结点p的数据域;
c若结点p的右孩子无左子树,则将s的右子树接到par的右子树上;否则,将s的右子树接到结点par的左子树上;
d删除结点s;
}
4)插入模块
voidinsertTree(intkey)
{
在二叉树排序树中,插入一个结点s(递归算法);
被CreatBST函数调用;}
5)查找模块
treeNode*searchTree(intkey)
{
在根指针所指二叉排序树中递归查找关键字等于key的数据元素;
若成功,返回指向该数据元素结点的指针;
否则返回空指针;
}
5、程序的主要函数及其伪代码说明
treeNode*BiSortTree:
:
buildTree(treeNode*head,intnumber)//建立一个二叉排序树
{
treeNode*p;//建立指向结点的指针
p=newtreeNode;//p结点是一个新的结点
p->key=number;
p->left=p->right=NULL;//p的左右分支均为空
if(head==NULL)
{
returnp;
}
else
{
if(p->key
head->left=buildTree(head->left,number);
else
head->right=buildTree(head->right,number);//否则赋值给head的右分支
returnhead;
}
}
treeNode*BiSortTree:
:
searchTree(intkey)//查找一个节点
{
returnsearch(Head,key);
}
voidBiSortTree:
:
insertTree(intkey)//插入一个结点
{
Head=buildTree(Head,key);
}
intBiSortTree:
:
deleteTree(intkey)//删除一个结点
{
treeNode*p;
p=NULL;
p=search(Head,key);
if(p==NULL)
{
cout<<"Can'tfindthekey";
}
if(p==Head)
{
Head=NULL;
}
else
{
treeNode*parent;
parent=searchParent(Head,p);
if(p->left==NULL&&p->right==NULL)//叶子节点即p的左右子树都为空
{
if(parent->left==p)//if(!
parent)
{
parent->left=NULL;
}
else
{
parent->right=NULL;
}
}
else//非叶子节点
{
if(p->right==NULL)//该节点没有右孩子
{
if(parent->left==p)
{
parent->left=p->left;
}
else
{
parent->right=p->left;
}
}
else//该点有左右孩子
{
treeNode*rightMinSon,*secondParent;//secondParent为右子树中的最小节点的父亲
rightMinSon=searchMinRight(p->right);
secondParent=searchParent(p->right,rightMinSon);
secondParent->left=rightMinSon->right;
if(p->right==rightMinSon)//右子树中的最小节点的父亲为p
{
p->right=rightMinSon->right;
}
p->key=rightMinSon->key;
}
}
}
return1;
}
treeNode*BiSortTree:
:
searchParent(treeNode*head,treeNode*p)
{
if(head->left==p||head->right==p||head==p||head==NULL)
returnhead;
else
{
if(p->key
returnsearchParent(head->left,p);
else
returnsearchParent(head->right,p);
}
}
treeNode*BiSortTree:
:
searchMinRight(treeNode*head)//找到右子树中最小的节点
{
if(head->left==NULL||head==NULL)
{
returnhead;
}
else
{
returnsearchMinRight(head->left);
}
}
三、上机结果及体会
1、实际完成的情况说明
所要求实现的基本功能:
建立二叉树、排序、插入、删除、查找等操作已能实现
2、程序的性能分析,包括时空分析
操作时间复杂度
查找
O(n)
插入
O(n)/O(logn)
删除
O(n)
3、打印程序运行时的初值及运行结果,画出相应的图示
初始界面
a:
输入所需建树的数据,给出中序序列以及用户操作菜单
b:
选择操作1,输出中序遍历的序列
c:
选择操作2,插入一个结点,同时输出中序遍历序列
d:
选择操作3,查找相关节点,判断所需查找的结点是否存在
e:
选择操作4,输入需要删除的结点,同时输出中序遍历序列
若所需删除的结点不存在,则会显示不存在该结点
4、上机过程中出现的问题及其解决方案
删除部分头节点的删除出错
解决方案:
改变指针指向的结点,保证指针指向的结点的顺序正确
5、程序中可以改进的地方说明
在建树阶段可以二叉树的形式进行输出,本程序所采用的输出形式是将二叉树中序遍历完成之后再进行输出的,输出的是一个已经完成排序的中序序列,较二叉树的输出形式来说没有其直观。
6、收获及体会
1)进行程序设计的时候注意模块的划分,从各个小模块开始进行设计
2)熟练掌握各函数的成员构成
3)交流与合作
打印一份源程序清单并附上注释
1、#include
2、#include
3、usingnamespacestd;
4、typedefstructTreeNode//声明树的结构
5、{
6、intkey;//存放关键字
7、structTreeNode*left;//存放左子树的指针
8、structTreeNode*right;//存放右子树的指针
9、}treeNode;
10、classBiSortTree
11、{
12、public:
13、BiSortTree(void);
14、voiddesplayTree(void);//显示这个树
15、voidinsertTree(intkey);//在树中插入一个结点
16、intdeleteTree(intkey);//在树中删除一个结点
17、treeNode*searchTree(intkey);//在树中查找一个结点
18、~BiSortTree();
19、private:
20、treeNode*buildTree(treeNode*head,intnumber);//建立一个树
21、treeNode*search(treeNode*head,intkey);//查找
22、treeNode*BiSortTree:
:
searchParent(treeNode*head,treeNode*p);//查找出p的父亲节点的指针
23、treeNode*BiSortTree:
:
searchMinRight(treeNode*head);//找到右子树中最小的节点
24、voidshowTree(treeNode*head);//显示
25、voiddestroyTree(treeNode*head);//删除
26、treeNode*Head;
27、};
28、BiSortTree:
:
BiSortTree()
29、{
30、cout<<"建立一棵二叉排序树,请输入你要建树的所有数(以-1作为结束标志!
):
"< 31、Head=NULL; 32、intnumber; 33、cin>>number; 34、while(number! =-1) 35、{ 36、Head=buildTree(Head,number); 37、cin>>number; 38、} 39、} 40、 41、treeNode*BiSortTree: : buildTree(treeNode*head,intnumber)//建立一个二叉排序树 42、{ 43、treeNode*p; 44、p=newtreeNode; 45、p->key=number; 46、p->left=p->right=NULL; 47、if(head==NULL) 48、{ 49、returnp; 50、} 51、else 52、{ 53、if(p->key 54、head->left=buildTree(head->left,number); 55、else 56、head->right=buildTree(head->right,number); 57、returnhead; 58、} 59、} 60、voidBiSortTree: : insertTree(intkey)//插入一个结点通过调用BuildTree函数 61、{ 62、Head=buildTree(Head,key); 63、} 64、 65、treeNode*BiSortTree: : searchTree(intkey)//查找一个节点调用search函数 66、{ 67、returnsearch(Head,key); 68、} 69、 70、treeNode*BiSortTree: : search(treeNode*head,intkey)//查找 71、{ 72、if(head==NULL) 73、returnNULL; 74、if(head->key==key) 75、returnhead; 76、else 77、{ 78、if(key 79、returnsearch(head->left,key); 80、else 81、returnsearch(head->right,key); 82、} 83、} 84、 85、intBiSortTree: : deleteTree(intkey)//删除一个结点 86、{ 87、treeNode*p; 88、p=NULL; 89、p=search(Head,key);//通过search函数先找到关键字 90、if(p==NULL)//结点为空找不到关键字 91、{ 92、cout<<"Can'tfindthekey"; 93、} 94、if(p==Head)//如果为头结点则直接删除 95、{ 96、Head=NULL; 97、} 98、else//否则分为叶子结点,有孩子的结点和左右孩子都有的结点讨论 99、{ 100、treeNode*parent; 101、parent=searchParent(Head,p); 102、if(p->left==NULL&&p->right==NULL)//叶子节点即p的左右子树都为空 103、{ 104、if(parent->left==p)//if(! parent) 105、{ 106、parent->left=NULL; 107、} 108、else 109、{ 110、parent->right=NULL; 111、} 112、} 113、else//非叶子节点 114、{ 115、if(p->right==NULL)//该节点没有右孩子 116、{ 117、if(parent->left==p) 118、{ 119、parent->left=p->left; 120、} 121、else 122、{ 123、parent->right=p->left; 124、} 125、} 126、else//该点有左右孩子 127、{ 128、treeNode*rightMinSon,*secondParent;//secondParent为右子树中的最小节点的父亲 129、rightMinSon=searchMinRight(p->right); 130、secondParent=searchParent(p->right,rightMinSon); 131、secondParent->left=rightMinSon->right; 132、if(p->right==rightMinSon)//右子树中的最小节点的父亲为p 133、{ 134、p->right=rightMinSon->right; 135、 136、} 137、p->key=rightMinSon->key; 138、} 139、} 140、} 141、return1; 142、} 143、treeNode*BiSortTree: : searchParent(treeNode*head,treeNode*p)//寻找父亲结点 144、{ 145、if(head->left==p||head->right==p||head==p||head==NULL) 146、returnhead; 147、else 148、{ 149、if(p->key 150、returnsearchParent(head->left,p); 151、else 152、returnsearchParent(head->right,p); 153、} 154、} 155、treeNode*BiSortTree: : searchMinRight(treeNode*head)//找到右子树中最小的节点 156、{ 157、if(head->left==NULL||head==NULL) 158、{ 159、returnhead; 160、} 161、else 162、{ 163、returnsearchMinRight(head->left); 164、} 165、} 166、voidBiSortTree: : desplayTree(void)//递归中序遍历输出 167、{ 168、showTree(Head); 169、cout< 170、} 171、voidBiSortTree: : showTree(treeNode*Head) 172、{ 173、if(Head! =NULL) 174、{ 175、showTree(Head->left); 176、cout< 177、showTree(Head->right); 178、} 179、} 180、BiSortTree: : ~BiSortTree()//调用析构函数,运用递归删除所有的New结点 181、{ 182、cout<<"已经消除了一棵树"< 183、destroyTree(Head); 184、} 185、voidBiSortTree: : destroyTree(treeNode*head) 186、{ 187、if(head! =NULL) 188、{ 189、destroyTree(head->left); 190、destroyTree(head->right); 191、deletehead; 192、} 193、} 194、voidprint() 195、{ 196、cout<<"*************以下是对二叉排序树的基本操作*************"< 197、cout<<"1.输出二叉树"< 198、cout<<"2.插入一个节点"< 199、cout<<"3.查找一个节点"< 200、cout<<"4.删除一个节点"< 201、} 202、intmain() 203、{ 204、BiSortTreetree; 205、intnumber; 206、intchoiceNumber; 207、charflag; 208、while (1) 209、{ 210、print(); 211、cout<<"请选择你要进行的操作(1~4)"< 212、cin>>choiceNumber; 213、switch(choiceNumber) 214、{ 215、case1: 216、tree.desplayTree();break; 217、case2: 218、cout<<"请插入一个结点: "< 219、cin>>number; 220、tree.insertTree(number); 221、tree.desplayTree(); 222、break; 223、case3: 224、cout<<"请输入你要查找的结点: "< 225、cin>>number; 226、if(tree.searchTree(number)==NULL) 227、{ 228、cout<<"未找到所要查找的结点"< 229、} 230、else 231、{ 232、 233、cout<<"已找到所要查找的结点"< 234、} 235、break; 236、case4: 237、cout<<"请输入你要删除的数: "< 238、cin>>number; 239、tree.deleteTree(number); 240、tree.desplayTree(); 241、break; 242、default: break; 243、} 244、cout<<"你是否要继续(Y/N)? "< 24
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 江苏 大学 C+ 二叉排序树 建立 插入 删除 查找 免费 下载