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

2021年1月17日发(作者：董祖诒)




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

用心整理的精品
word
文档，下载即可编辑！！


淮
阴
工
学
院

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


题目
：

二叉排序树的创建、插入、


删除



系

（院）
:
计算机工程学院


专

业
：

计算机科学与技术



班

级
：

计算机
3123


学

号
：

1121321124


姓

名
：

单永明


指导教师
：

刘作军
/
寇海州


学年学期
:
2014 ~ 2015
学年

第
1
学期


精心整理，用心做精品
2
用心整理的精品
word
文档，下载即可编辑！！

算法设计技能训练任务书

课题

名称


1
、

通过算法设计技能训练，深入理解算法设计的意义和重要性，更好地
掌握

设计

算法设计的知识。

目的

2
、

能够针对某一具体问题，设计算法进行解决。

3
、

锻炼实践动手能力，提高解决问题的能力。

硬件：
1
、
PC
机，奔腾
Ⅳ
以上
CPU
，
512MB
以上内存，
80G
以上硬盘；


实验

软件：
Visual C++
编程工具

环境


1.
分析问题，给出数学模型，选择数据结构

2.
设计算法，给出算法描述

任务

要求

3.
给出源程序清单

4.
编辑、编译、调试源程序

5.
撰写课程设计报告

工作进度计划

序号

1
2
3
4
起止日期

2014.12.20
2014.12.25
～
2014.12.28
2014.12.29
～
2013.12.31
2014.12.31
工

作

内

容

任务下达，查阅文献资料

总体设计、素材搜集、课题详细设计、调试

完善设计、撰写报告

答辩

指导教师（签章）：


年

月

日


精心整理，用心做精品
3
用心整理的精品
word
文档，下载即可编辑！！


目录

1
、引言
...................... .................................................. .................................................. ................
4

2
、课程设计的题目和内容

..................... .................................................. ...............................
5

2.1
课程设计的题目
........................... .................................................. .................
5

2.2
课程设计的内容
.................................................. ............................................
5

3
、课程设计报告内容
................. .................................................. ............................................
6

3.1
课程概述
.................... .................................................. ...................................
6

3.2
实验内容
.............................. .................................................. .........................
7

3.3
源程序代码
............................. .................................................. ....................
1
0
3.4
测试用例
.............................. .................................................. .......................
1
5
实验总结
.. .................................................. .................................................. ................................
18

致谢
....................................... .................................................. ...........................
1
9
参考文献
..................................... .................................................. ...............................................
20




精心整理，用心做精品
4
用心整理的精品
word
文档，下载即可编辑！！

1.
引言


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





















精心整理，用心做精品
5
用心整理的精品
word
文档，下载即可编辑！！

2
、课程设计的题目和内容


2.1
课程设计的题目



二叉排序树的基本操作


2.2
、课程设计内容


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

2.
编写程序实现二叉排序树上的基本操作：

3.
输入数列生成二叉排序树

4.
对二叉排序作中序遍历；

5.
查找二叉排序树

6.
删除二叉排序树





精心整理，用心做精品
6
用心整理的精品
word
文档，下载即可编辑！！

3
、课程设计报告内容

3.1
课题概述

1
、问题描述：（需求分析和背景意义）


利用二叉排序树实现一个动态查找表。

2
、基本要求：（设计阶段，概要设计和详细设计）


实现动态查找表的三种功能：查找、插入、删除。

3
、测试数据：自行设定。

4
、实现提示：


（
1
）初始，二叉排序树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。每次插入或删
除一个结点后，应更二叉排序树的 显示。


（
2
）二叉排序树的显示可采用凹入表现形式，也可以 采用图形
界面画出树行。

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


精心整理，用心做精品
7
用心整理的精品
word
文档，下载即可编辑！！


3.2
实验内容
：
二叉排序树。


任意给定一组 数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插
入、删除等操作。

1.
实验说明：










二叉排序树存储结构
如下：


typedef struct tree//
声明树的结构

{



struct tree *left; //
存放左子树的指针



二叉排序树插入算法伪代码
如下：

struct tree *right; //
存放又子树的指针


1.
若
root
是空树，则将结点
s
作为根结点插入；否则

2.
若
s
->
data
＜
root
->
data
，则把结点
s
插入到
root
的左子树中；否则< br>
二
3.
把结点
s
插入到
root
的右子树中。

叉
排





二叉排序树中删除一个结 点
f
的孩子
p
算法伪代码
如下：













1.
若结点
p
是叶子，则直接删除结点
p
；

2.
若结点
p
只有左子树，则只需重接
p
的左子树；


若结点
p
只有右子树，则只需重接
p
的右子树；

3.
若结点
p
的左右子树均不空，则

3.1
查找结点
p
的右子树上的最左下结点
s
以及结点
s
的双亲结点
par
；

3.2
将结点
s
数据域替换到被删结点
p
的数据域；

3.3
若结点
p
的右孩子无左子树，则将
s
的右子树接到
par
的右子树上；

否则，将
s
的右子树接到结点
par
的左子树上；

3.4
删除结点
s
；







2.
实验分析：


a.

主程序

精心整理，用心做精品
8
用心整理的精品
word
文档，下载即可编辑！！


从建树开始，依次输入你的关键字并以
-1
结束。将你的关键字插入二叉排序树

中，并中序输出创建过程。并对你的树执行下列操作：插入，删除，查找。

程序的主要流程图见图
2-1
：



开始

建树
：

①

依次输入
n
个关键字

②

插入二叉排序树中

删除任意结点

插入一个结点


中序输出操作后二叉排序树

是否继续

否

结束

是


2-1








3.
主要模块
：


1
）主函数模块

Main()
{
建立
n
个关键字的二叉排序树并输出；

精心整理，用心做精品
9
用心整理的精品
word
文档，下载即可编辑！！

从二叉树排序树
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
中，插入一个结点< br>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; //
存放又子树的指针

精心整理，用心做精品
10
用心整理的精品
word
文档，下载即可编辑！！


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) //
原树为空，新插入的结点为新的根



tptr=p;

else


if(keykey)



f->left=p;


else



f->right=p;


return tptr;
}

BSTree createBST()//
建立二叉树

{

BSTree t=NULL; //
根结点


KeyType key;

cin>>key;

while(key!=-1)

{


t=insertBST(t,key);


cin>>key;

}

return t;
}
void inorder_btree(BSTree root)//
中序遍历打印二叉排序树

{

BSTree p=root;

if(p!=NULL){


inorder_btree(p->left );


cout<<


inorder_btree(p->right );

}
}
int searchBST(BSTree t,KeyType key)//
查找

{
精心整理，用心做精品
11