二叉排序树的创建、删除、插入等操作

淮阴工学院

算法设计技能训练实习报告

题目： 二叉排序树的创建、插入、

删除

系 （院）: 计算机工程学院

专 业： 计算机科学与技术

班 级： 计算机3123 学 号： 1121321124 姓 名： 单永明 指导教师： 刘作军/寇海州 学年学期: 2014 ~ 2015 学年 第 1 学期

企业管理文档表格

页眉内容

企业管理文档表格

页眉内容

算法设计技能训练任务书

课题

名称 1、 通过算法设计技能训练，深入理解算法设计的意义和重要性，更好地掌握 设计 目的 算法设计的知识。 2、 能够针对某一具体问题，设计算法进行解决。 3、 锻炼实践动手能力，提高解决问题的能力。 硬件：1、PC机，奔腾Ⅳ以上CPU， 512MB以上内存，80G以上硬盘； 实验 环境 软件：Visual C++编程工具 1.分析问题，给出数学模型，选择数据结构 2.设计算法，给出算法描述 任务 3.给出源程序清单 要求 4.编辑、编译、调试源程序 5.撰写课程设计报告 工作进度计划 企业管理文档表格

页眉内容

序号 1 起止日期 2014.12.20 工 作 内 容 任务下达，查阅文献资料 2 2014.12.25～2014.12.28 总体设计、素材搜集、课题详细设计、调试 3 2014.12.29～2013.12.31 完善设计、撰写报告 4 2014.12.31 答辩 指导教师（签章）：

年 月 日

企业管理文档表格

页眉内容

目录

1、引言 .......................................................................................... 4 2、课程设计的题目和内容 .................................................................. 5 2.1课程设计的题目 ............................................................................ 5 2.2课程设计的内容 ........................................................................... 5 3、课程设计报告内容 ........................................................................ 6 3.1课程概述 .................................................................................... 6 3.2实验内容 .................................................................................... 7 3.3源程序代码 ................................................................................ 10 3.4测试用例 ................................................................................... 15 实验总结 ....................................................................................... 18

致谢 ............................................................................................. 19

参考文献 ...................................................................................... 20

企业管理文档表格

页眉内容

1.引言

本算法设计技能训练的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。

企业管理文档表格

页眉内容

2、课程设计的题目和内容 2.1课程设计的题目 二叉排序树的基本操作

2.2、课程设计内容

1.用二叉链表作存储结构，

2.编写程序实现二叉排序树上的基本操作： 3.输入数列生成二叉排序树 4.对二叉排序作中序遍历； 5.查找二叉排序树 6.删除二叉排序树

企业管理文档表格

页眉内容

3、课程设计报告内容 3.1课题概述

1、问题描述：（需求分析和背景意义） 利用二叉排序树实现一个动态查找表。 2、基本要求：（设计阶段，概要设计和详细设计） 实现动态查找表的三种功能：查找、插入、删除。 3、测试数据：自行设定。 4、实现提示：

（1）初始，二叉排序树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。每次插入或删除一个结点后，应更二叉排序树的显示。 （2）二叉排序树的显示可采用凹入表现形式，也可以采用图形界面画出树行。

（3）教科书已给出查找和插入算法，本题重点在于对删除算法的设计和实现。假设要删除关键字为x的结点。如果x不在叶子结点上，则用它的左子树中最大值或右子树中的最小值取代x。如此反复取代，直到删除动作传递到某个叶子结点。删除叶子结点时，若需要进行平衡交换，可采用插入的平衡变换的反变换（如，左子树变矮对应右子树长高）。

企业管理文档表格

页眉内容

企业管理文档表格

页眉内容

3.2实验内容：二叉排序树。 任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。 1.实验说明： 二叉排序树存储结构如下： typedef struct tree//声明树的结构 { 二叉排序树插入算法伪代码如下： 1. 若root是空树，则将结点s作为根结点插入；否则 二叉排 二叉排序树中删除一个结点f的孩子p算法伪代码如下： 企业管理文档表格

页眉内容

1. 若结点p是叶子，则直接删除结点p； 2. 若结点p只有左子树，则只需重接p的左子树； 若结点p只有右子树，则只需重接p的右子树； 2.实验分析： a. 主程序 从建树开始，依次输入你的关键字并以-1结束。将你的关键字插入二叉排序树 中，并中序输出创建过程。并对你的树执行下列操作：插入，删除，查找。 程序的主要流程图见图2-1： 企业管理文档表格

页眉内容

开始 建树： ① 依次输入n个关键字 删除任意结点 插入一个结点 中序输出操作后二叉排序树 是否继续 否 结束 2-1 3.主要模块： 1）主函数模块 是 企业管理文档表格

页眉内容

Main() { 建立n个关键字的二叉排序树并输出； 从二叉树排序树T中删除任意结点,其关键字为key； 在二叉树排序树T中，插入一个结点t,其关键字为key； 在二叉排序树T中递归查找关键字等于 key2 的数据元素； } 2）创建二叉排序树模块 BiTree CreatBST(int n) { 建立n个关键字的二叉排序树； 从键盘输入调建立n个关键字依次用InsertBST1（插入函数）； 返回根结点T； 输出过程； } 3）删除模块 DeleteNode(BiTree &T, int x) { 企业管理文档表格

页眉内容

从二叉树排序树T中删除任意结点,其关键字为x； 可以实现删除根结点、叶子结点以及其它任意结点的功能； } 4）插入模块 void InsertBST1(BiTree &T,BiTNode *s) { 在二叉树排序树T中，插入一个结点s(递归算法)； 被CreatBST函数调用； } 5）查找模块 BiTree searchBST1(BiTree T,TElemType key) { 在根指针T所指二叉排序树中递归查找关键字等于 key 的数据元素； 若成功，返回指向该数据元素结点的指针； 否则返回空指针； } 3.3.源程序代码： 企业管理文档表格

页眉内容

#include using namespace std; typedef int KeyType; typedef struct tree//声明树的结构 { struct tree *left; //存放左子树的指针 struct tree *right; //存放又子树的指针 KeyType key; //存放节点的内容 } BSTNode, * BSTree; //声明二叉树的链表 BSTree insertBST(BSTree tptr,KeyType key)// 在二叉排序树中插入结点 { //若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回 BSTree f,p=tptr; //p的初值指向根结点 while(p) //查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲 { if(p->key==key) //树中已有key，无须插入 return tptr; f=p; //f保存当前查找的结点，即f是p的双亲 企业管理文档表格

页眉内容

} } p=(keykey)?p->left:p->right; p=(BSTree )malloc(sizeof(BSTNode)); //生成新结点 p->key=key; p->left=p->right=NULL; if(tptr==NULL) //原树为空，新插入的结点为新的根 else if(keykey) else f->right=p; f->left=p; tptr=p; return tptr; BSTree createBST()//建立二叉树 { BSTree t=NULL; //根结点 KeyType key; cin>>key; while(key!=-1) { t=insertBST(t,key); 企业管理文档表格

页眉内容

} void inorder_btree(BSTree root)// 中序遍历打印二叉排序树 { } int searchBST(BSTree t,KeyType key)//查找 { if(key==t->key) return 1; BSTree p=root; if(p!=NULL){ } inorder_btree(p->left ); cout<<\" \"<key<<\" \"; inorder_btree(p->right ); } return t; cin>>key; if(t==NULL) return 0; if(keykey) else return searchBST(t->right,key); return searchBST(t->left,key); 企业管理文档表格

页眉内容

} BSTree deleteBST(BSTree tptr,KeyType key)//删除 { BSTree p,tmp,parent=NULL; p=tptr; while(p) { if(p->key==key) break; parent=p; p=(keykey)?p->left:p->right; } if(!p) return NULL; tmp=p; if(!p->right&&!p->left) /*p的左右子树都为空*/ { if(!parent) //要删根，须修改根指针 tptr=NULL; else if(p==parent->right) parent->right=NULL; else parent->left=NULL; free(p); 企业管理文档表格

页眉内容

} else if(!p->right) //p的右子树为空，则重接p的左子树 { p=p->left; if(!parent) //要删根，须修改根指针 tptr=p; else if(tmp==parent->left) parent->left=p; else parent->right=p; free(tmp); } else if(!p->left) //的左子树为空，则重接p的左子树 { p=p->right; if(!parent) //要删根，须修改根指针 tptr=p; else if(tmp==parent->left) parent->left=p; else parent->right=p; free(tmp); 企业管理文档表格

页眉内容

} else if(p->right&&p->left) //p有左子树和右子树，用p的后继覆盖p然后删去后继 { //另有方法：用p的前驱覆盖p然后删去前驱||合并p的左右子树 parent=p; //由于用覆盖法删根，则不必特殊考虑删根 p=p->right; while(p->left) { parent=p; p=p->left; } tmp->key=p->key; if(p==parent->left) parent->left=NULL; else parent->right=NULL; free(p); } return tptr; } int main() { KeyType key; int flag,test; 企业管理文档表格

页眉内容

char cmd; BSTree root; do { cout<<\"\\n\\n\"<>cmd; flag++; }while(cmd!='c'&&cmd!='C'&&cmd!='a'&&cmd!='A'); if(cmd=='c'||cmd=='C') { cout<<\"请输入你所要创建的二叉树的结点的值，以-1结束：\\n\"; 企业管理文档表格

页眉内容

root=createBST(); do { flag=0; cout<<\"\\n\\n中序遍历二叉树：\"<页眉内容

scanf(\"%c\ flag++; }while(cmd!='s'&&cmd!='S'&&cmd!='i'&&cmd!='I'&&cmd!='d'&&cmd!='D'&&cmd!='q'&&cmd!='Q'); switch(cmd) { case 's': case 'S': cout<<\"请输入你要查找结点的关键字：\\n\"; cin>>key; test=searchBST(root,key); if(test==0) else cout<<\"\\n成功找到结点\\n\"<>key; root=insertBST(root,key); //注意必须将值传回根 企业管理文档表格

页眉内容

} } break; case 'd': case 'D': } cout<<\"请输入你要删除结点的关键字：\\n\"; cin>>key; root=deleteBST(root,key); //注意必须将值传回根 if(root==NULL) else cout<<\"\\n成功删除结点 \"<页眉内容

实 验 内 容 企业管理文档表格

页眉内容

3.4测试用例： 1,程序运行时菜单显示如下： 当输入的二叉树序列为：{2,6,9,8,4}时，创建二叉排序树，并输出结果如下： 企业管理文档表格

页眉内容

1.查找9结点时，运行结果如下： 2.删除结点6时运行结果如下： 企业管理文档表格

页眉内容

3.插入结点7时运行结果如下： 企业管理文档表格

页眉内容

实 验 内 容 企业管理文档表格

页眉内容

实验总结 通过这次的实验，我认识到：仅仅掌握课本上的知识是不够的，在实际操作时，常常遇到一些问题，自己看不懂，更无法解决。不过，经过自己不断的思考，尝试着去更改代码中出现的问题。虽然开始很困难，但在老师和同学的帮助下，我逐渐的熟悉了许多操作，为后继工作的顺利进行做了准备。 个人的力量是薄弱的，我学会了咨询别人，不再胆怯，不再保守。 在过程中和同学相互讨论，询问老师，不断进步。 也许，我们可以说，编一个程仅仅是开始，调试和运行相比之下更难。实践中收获的远比想象的多。 看到自己完成了所要求的任务，有一种无法用言语来形容的欣慰之感，这也是无法从学习书本知识中得到的。 企业管理文档表格

页眉内容

致谢 本设计是在指导教师刘作军老师和寇海洲老师的亲切关怀和细心指导下完成的。刘作军老师从设计方案的选定，设计计划的安排，都给予了精心的指导及严格的要求。寇海洲老师在实验过程中给予了我们很大的支持与帮助。这个算法设计和报告的完成，凝结着两位老师的心血和汗水。二位老师严谨的治学态度，开拓性的工作作风和科学的思维方法都使我受益非浅。二位老师对我的设计和报告给予了莫大的关心和帮助，在此，我表示衷心的感谢和诚挚的谢意。 在设计过程中也得到了同学们的指点和帮助，特别是在编程中遇到技术性问题的时候，同学的指点使我茅塞顿开，顺利的解决了问题。在此我表示诚挚的感谢。 参考文献 1. 钱能.c++程序设计教程（修订版）,北京：清华大学出版社，2009.7 企业管理文档表格

页眉内容

2. 严蔚敏，吴伟民.数据结构（c语言版）,北京：清华大学出版社，2007 3. 蔡锁章.数学建模原理与方法,北京：海洋出版社，2000 4. 范金城，梅长林.数据分析,北京：科学出版社，2002 企业管理文档表格

页眉内容

指导教师评语

班级 计算机3123 学号 1121321124 姓名 单永明 选题 二叉排序树 名称 序号 评价内容 权重（%） 得分 1 考勤记录、学习态度、工作作风与表现。 自学情况： 5 2 上网检索机时数、文献阅读情况（笔记）。 3 论文选题是否先进，是否具有前沿性或前瞻性。 成果验收： 4 是否完成设计任务；能否运行、可操作性如何等。 报告的格式规范程度、是否图文并茂、语言规范及流畅程度；主题是否鲜明、重心是否突出、论述是否充分、结论是否正确；是否提出了自己的独到见解。 文献引用是否合理、充分、真实。 答辩情况： 自我陈述、回答问题的正确性、用语准确性、10 5 20 5 30 6 5 7 25 企业管理文档表格

页眉内容

逻辑思维、是否具有独到见解等。 合计 指导教师（签章）： 年 月 日

企业管理文档表格