基于BST二叉排序树的城市信息管理.docx

基于BST二叉排序树的城市信息管理.docx

《基于BST二叉排序树的城市信息管理.docx》由会员分享，可在线阅读，更多相关《基于BST二叉排序树的城市信息管理.docx（30页珍藏版）》请在冰点文库上搜索。

基于BST二叉排序树的城市信息管理

一、设计题目

【问题描述】

利用二叉排序树实现城市信息管理，城市信息包括城市名、城市坐标（X,Y）。

【基本要求】

将若干城市信息按城市名的顺序建立二叉排序树；

可以插入一个城市信息；

按城市名查找一个城市信息；

输入一个城市名，查找和该城市名的距离在指定围的所有城市。

【测试数据】

自己指定。

【选作容】

删除一个城市信息。

二、需求分析

1）运行环境（软、硬件环境）

Microsoftvisualc++6.0

PC+window7

2）输入的形式和输入值的围

输入城市信息，例如：

“城市名左坐标右坐标”的形式。

输入的左右坐标是整型的，城市名是字符串（以中文的形式）。

左右坐标为100的整数。

3）输出的形式描述

输出的是城市信息，就是例如：

“城市名左坐标右坐标”的形式。

4）功能描述

输入参数包括：

城市名，左坐标，右坐标；

需要插入的城市与左右坐标；需要查找的城市名；需要查找周围城市信息的城市名与搜索围；需要删除的城市名。

功能要求：

1.将若干城市信息按城市名的顺序建立二叉排序树；

2.可以插入一个城市信息；

3.按城市名查找一个城市信息；

4.输入一个城市名，查找和该城市名的距离在指定围的所有城市。

5.删除一个城市信息（选作）。

5）测试数据

输入的城市信息：

（5,6）

（3,4）

（4,9）

上海（2,8）

北京（1,3）

需要插入的城市：

（3,5）

需要查找的城市：

需要查找哪个城市周围城市：

查找围：

20

需要删除的城市名：

新疆（选做）

三、概要设计

1）抽象数据类型定义描述

（对各类的成员及成员函数进行抽象描述，参见书或ppt及实验）

本设计采用非线性结构中的树结构的二叉排序树思想，定义了如下的各类的成员及成员函数：

类：

information（包含城市的所有信息）

其中cityname作为其成员。

并在类定义了一个结构体，x，y为其成员，并定义了结构体的对象cityname_location，用来后期调用坐标变量x，y。

类：

BiNode（二叉排序树的结点结构）

将后面的BiTree作为其友元类。

其中定义了之前information类的对象data作为自己的成员，并定义了指向左孩子的指针和指向右孩子的指针。

类：

BiTree（二叉排序树的类）

定义了带参构造函数。

获取指向根结点的指针的成员函数（函数成员名Getroot）；

用于起始插入值的成员函数（函数成员名InsertBST）；

用于后期插入值的成员函数（函数成员名InsertBST1）；

用于删除一个或者多个结点的成员函数（函数成员名deleteBST）和其后面需要用到的两个函数（函数名：

searchMinRchild，searchParent）；（选做）

用于查找城市信息的成员函数（成员函数名SearchBST）；

用于前序遍历二叉树的成员函数（成员函数名Preorder）；

用于中序遍历二叉树的成员函数（成员函数名Inorder）；

用于选择界面的成员函数（成员函数名Choose）；

用于对起始城市坐标赋值的成员函数（成员函数名Begain）；

用于查找需要被动比较的城市的坐标的成员函数（成员函数名Find）；

用于查找作为参照的城市坐标的成员函数（成员函数名Find1）

还定义了二叉排序树（即二叉链表）的根指针（root）

2）功能模块设计（如主程序模块设计）

1、起始：

输入要输的城市的个数（数字，中文，英文都可以，大小写皆可）。

调用插入函数InsertBST，根据城市的名字（利用其ascii码值）进行二叉排序树的创建。

调用Begain函数，对起始城市坐标赋值

完成所有城市的所有信息输入完成，待用。

2、主菜单模块：

调用Choose函数，进行主菜单显示，并用switch与case进行菜单容的选择实现。

做到每次信息更新后都能及时显示在屏幕上供用户查看。

3、前序遍历城市信息表模块：

调用前序遍历二叉树的成员函数（成员函数名Preorder），对已创建的二叉排序树进行前序遍历输出。

4、中序遍历城市信息表模块：

调用中序遍历二叉树的成员函数（成员函数名Inorder），对已创建的二叉排序树进行中序遍历输出。

5、查询城市信息模块：

输入查询的总次数，用for循环实现多次的查找；

输入要查询的城市；

调用函数SearchBST进行查找。

结果显示。

6、查找制定距离的城市信息模块：

输入指定的城市；

输入指定的距离；

用for循环实现对所有已有的城市信息的查找。

调用函数Find查找需要被动比较的城市的坐标；

调用函数Find1查找作为参照的城市坐标。

对相应的城市坐标进行算术运算，相减平方开放

（即：

sqrt（（x-z）*（x-z）+（y-w）*（y-w）））

最终判定结果显示。

7、插入模块：

输入插入的总次数，用for循环实现多次的插入；

输入要插入的城市（新申请一个结点，用输入的城市名赋值于结点的data.city）；

由于新加了一个结点，所以总个数n要相应改变，每插入一个加一，并将信息放入对应的数组单元。

将新结点的指向左右孩子的指针赋值为空。

调用函数InsertBST进行插入，将其接入适合的二叉排序树的位置根据（左小右大）。

结果显示。

8、删除模块：

（选做）

输入删除的总次数，用for循环实现多次的删除；

输入要删除的城市；

先调用函数SearchBST对输入值进行查找，如果找到则，有效删除，否则显示不存在给的城市名。

结果显示。

9、退出模块：

显示本人信息，对使用表示感谢，然后用exit（0）直接退出程序。

3）模块层次调用关系图

各模块之间的关系图：

四、详细设计

实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。

1.二叉排序树的定义

　　二叉排序树（BinarySortTree）又称二叉查找（搜索）树（BinarySearchTree）。

其定义为：

二叉排序树或者是空树，或者是满足如下性质的二叉树：

①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；

②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；

③左、右子树本身又各是一棵二叉排序树。

　　上述性质简称二叉排序树性质（BST性质），故二叉排序树实际上是满足BST性质的二叉树。

template

classBiTree

{

public:

BiTree（Ta[],intn）;//带参构造函数

BiNode*Getroot（）{returnroot;}//获取指向根结点的指针

BiNode*InsertBST（BiNode*root,BiNode*s）;//在二叉排序树中插入一个结点s，此处用于起始值插入

BiNode*InsertBST1（BiNode*root,BiNode*s）;

//2在二叉排序树中插入一个结点s，用于后期功能的多个或一个插入

//值，会显示插入成功

BiNode*SearchBST（BiNode*root,Tk）;//查找值为k的结点

voidPreorder（BiNode*rt）;//前序遍历二叉树

voidInorder（BiNode*rt）;//中序遍历二叉树

voidChoose（）;//选择界面

BiNode*Begain（BiNode*root,BiNode*s）;//对城市X,Y坐标进行初始化

BiNode*Find（BiNode*root,Tk）;//用于查找需要被比较的城市的坐标

BiNode*Find1（BiNode*root,Tk）;//查找作为参照的城市坐标

private:

BiNode*root;//二叉排序树的根指针

};

2.二叉排序树的性质

按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。

3.二叉排序树的插入

在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。

此处我将插入模块分成了两个部分。

第一个用来将刚开始的数据建立最初的二叉排序树BiNode*BiTree:

:

InsertBST（BiNode*root,BiNode*s）情况1、先判断if（root==NULL）即如果原结点不存在，则，插入结点变成根结点returns；情况2、如果有结点存在，则进行判断，二叉排序树特点，根结点关键字大于其左子树，小于其右子树

1）插入结点小于根结点。

即：

if（s->data.citydata.city）//

root->lchild=InsertBST（root->lchild,s）;//插入左子树，再依次往下比较。

2）插入结点大于根结点。

root->rchild=InsertBST（root->rchild,s）;插入到右子树中，再依次比较，

最终确定位置

插入过程：

template

BiNode*BiTree:

:

InsertBST（BiNode*root,BiNode*s）

{//在二叉排序树中插入一个结点s，此处用于起始插入值

if（root==NULL）//如果原结点不存在，则插入结点变成根结点

returns;

else//如果有结点存在，则进行判断，二叉排序树特点，根结点大于其左子树，小于其右子树

{

if（s->data.citydata.city）//插入结点小于根结点（按关键字城市名进行判断）

root->lchild=InsertBST（root->lchild,s）;//插入到左子树中

else//插入结点大于根结点（按关键字城市名进行判断）

root->rchild=InsertBST（root->rchild,s）;//插入到右子树中

returnroot;

}

}

template

BiNode*BiTree:

:

InsertBST1（BiNode*root,BiNode*s）

{//1在二叉排序树中插入一个结点s，用于后期功能的多个或一个插入值，会显示插入成功

if（root==NULL）//如果原结点不存在，则，插入结点变成根结点

returns;

else

{

if（s->data.citydata.city）

{

root->lchild=InsertBST（root->lchild,s）;

}

else

{

root->rchild=InsertBST（root->rchild,s）;

cout<<""<

Begain（root,s）;

}

}

returnroot;

}

4.二叉排序树的查找

假定二叉排序树的根结点指针为root，给定的关键字值为K，则查找算法可描述为：

template

BiNode*BiTree:

:

Find（BiNode*root,Tk）

{//得到被比较结点的x,y坐标，根据关键字查找

if（root==NULL）

returnroot;

else

{

if（root->data.city==k）

{//查找成功，返回

x=root->data.city_cityname.x;//将找到的结点的坐标分别赋值给两个变量x，y

y=root->data.city_cityname.y;

returnroot;

}

else//如果之前没找到，则按二叉排序树左小右大的规律继续查找

{

if（kdata.city）

{

returnFind（root->lchild,k）;

}

else

{

returnFind（root->rchild,k）;

}

}

}

}

template

BiNode*BiTree:

:

Find1（BiNode*root,Tk）

{//得到结点的x,y坐标，作为参照的结点的坐标值

if（root==NULL）

returnroot;//同上解释

else

{

if（root->data.city==k）

{//查找成功，返回

z=root->data.city_cityname.x;

w=root->data.city_cityname.y;

returnroot;

}

else

{

if（kdata.city）

{

returnFind（root->lchild,k）;

}

else

{

returnFind（root->rchild,k）;

}

}

}

}

查找某个城市的所有信息

template

BiNode*BiTree:

:

SearchBST（BiNode*ROOT,Tk）

{//查找某个城市的所有信息

if（root==NULL）

{//没有找到时的显示

cout<<"此城市不存在!

"<

returnNULL;

}

else

{

if（root->data.city==k）

{//查找成功，返回

cout<<"查找"<data.city<<"成功!

"<

cout<<"城市为"<data.city<<"的坐标为"<<"（"<data.cityname.x<<"<"<data.cityname.y<<"）"<

returnroot;

}

else

{

if（kdata.city）

{

returnSearchBST（root->lchild,k）;

}//如果之前没找到，则按二叉排序树左小右大的规律继续查找

//查找左子树

else

{

returnSearchBST（root->rchild,k）;

}//查找右子树

}

}

}

五、调试分析

包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会。

部分问题总结：

1、在做前序遍历和中序遍历的时候，发现前序遍历和中序遍历的输出果是一样的，结果发现前序遍历和中序遍历的算法顺序出错

2、templateclassBiTree;staticintx,y,z,w;的时候，运用了全局变量，结果报错，于是在全局变量前，加上关键字static，该变量就被定义成为一个静态全局变量

3、还需引入头文件#include因为需要用到开方sqrt在计算围距离时，发现当输入的坐标值的整数部分一致时，输出的两城市之间的距离总是相同。

4、定义#include"1.h"#include#include#include

#include时，报错，于是将头文件的名字统一改了

5、删除是选做，于是试着按照参考书和上网资料做了一下，但是发现我的境界还不到。

时间复杂度：

二叉查找树中查找的运行时间与树T的高度成正比。

因为有n个结点的树的高度小则为O（logn），大则为O（n）；以下将树高算为logn。

构造函数：

插入n个函数，树高为logn，所以时间复杂度为O（nlogn）。

取根结点函数：

时间复杂度为O

（1）。

插入结点函数：

时间复杂度为O（logn）。

中序遍历函数：

时间复杂度为O（n）。

前序遍历函数：

时间复杂度为O（n）。

查找函数：

时间复杂度为O（logn）。

查找周围城市函数：

时间复杂度为O（nlogn）。

实验体会：

通过这次数据结构的实验，让我对BST二叉排序树的算法有了更加深入的了解。

在编写程序的过程中，遇到了很多棘手的问题，但是这些问题，我通过了找老师，上网查询问题出错的原因等方法努力的寻求答案，到现在为止，程序已经顺利完成，运行无阻。

在编辑二叉树的过程中，我对于C++、C++数据结构的很多算法和思想有了更深一层次的理解。

二叉排序树及其相关容是课堂中没有讲过的，所以我不得不去图书馆借相关书籍学习二叉排序树的相关性质和操作，锻炼了我的自学能力。

在编写程序的过程中经常出现逻辑混乱，代码混杂等情况，我在这个过程中耐心通过画图，分布运行程序解决问题，这锻炼了我的耐心与逻辑思维。

另外，书上的容无法解决所有情况，比如删除城市这一函数很难理解，解决这一问题的过程锻炼了我的理解能力。

虽然我在平时的理论学习中学的还可以，但是实践的过程中还是发现了许多以前不曾发现的问题，相信本着理论与实践相结合的原则我能在以后其他科目的学习中取得更好的效果。

自己根据要求，从零开始做一份实验真的不容易，需要对整体结构局势进行把握，在做之前要做好多重准备工作，例如运行环境（软、硬件环境）、输入的形式和输入值的围、输出的形式描述、功能描述。

细节决定成败，对于我而言，这次的作业让我清楚认识到，注重细节的重要性，有时候一个字母的大小写，几个变量的数据类型的统一性，考虑后选择的更为合适的数据类型，重复执行的问题等等，这些都让我不断进步。

编写出一套完成的程序固然重要，但是，我认为更重要的是，在整个过程中，我学到的东西，无论是同学间的互相帮助还是这种面对困难不退缩，勇敢的面对和挑战的感觉。

我相信我会一直保留下这份珍贵的记忆和经验，这将使我在以后发展的道路上走的更远。

六、测试结果

七、附录：

程序设计源代码

#include

usingnamespacestd;

template

classBinNode;

template

classBiTree;

template

classinformation//此类包含城市的所有信息（包含：

城市名，两个坐标）

{

public:

Tcity;//城市名

structlocation//定义一个结构体，用来放城市的坐标

{

intx,y;//城市坐标

}city_cityname;//结构体location的对象

};

template

classBiNode//二叉排序树的结点结构

{

public:

friendclassBiTree;//将BiTree这个类声明为其友元类，使其可以调用这个类中的一切

informationdata;

BiNode*lchild,*rchild;

};

template

classBiTree

{

public:

BiTree（Ta[],intn）;//带参构造函数

BiNode*Getroot（）{returnroot;}//获取指向根结点的指针

BiNode*InsertBST（BiNode*root,BiNode*s）;//在二叉排序树中插入一个结点s，此处用于起始值插入

BiNode*InsertBST1（BiNode*root,BiNode*s）;

//2在二叉排序树中插入一个结点s，用于后期功能的多个或一个插入

//值，会显示插入成功

BiNode*SearchBST（BiNode*root,Tk）;//查找值为k的结点

voidPreorder（BiNode*rt）;//前序遍历二叉树

voidInorder（BiNode*rt）;//中序遍历二叉树

voidChoose（）;//选择界面

BiNode*Begain（BiNode*root,BiNode*s）;//对城市X,Y坐标进行初始化

BiNode*Find（BiNode*root,Tk）;//用于查找需要被比较的城市的坐标

BiNode*Find1（BiNode*root,Tk）;//查找作为参照的城市坐标

private:

BiNode*root;//二叉排序树的根指针

};

#include"1.h"

#include

#include

#include

#include

template

classBiTree;

staticintx,y,z,w;//后面需要用到的算距离围

template

BiTree:

:

BiTree（Ta[],intn）//构造函数，初始化所有容

{

root=NULL;

for（inti=0;i

{

BiNode*s=newBiNode;

s->data.city=a[i];

s->lchild=NULL;

s->rchild=NULL;

root=InsertBST（root,s）;//结点依次插入

Begain（root,s）;//输入起始数据的各个坐标

}

}

template

BiNode*BiTree:

:

InsertBST（BiNode*root,BiNode*s）

{//在二叉排序树中插入一个结点s，此处用于起始插入值

if（root==NULL）//如果原结点不存在，则插入结点变成根结点

returns;

else//如果有结点存在，则进行判断，二叉排序树特点，根结点大于其左子树，小于其右子树

{

if（s->data.citydata.city）//插入结点小于根结点（按关键字城市名进行判断）

root->lchild=InsertBST（root->lchild,s）;//插入到左子树中

else//插入结点大于根结点（按关键字城市名进行判断）

root->rchild=InsertBST（root->rchild,s）;//插入到右子树中

returnroot;

}

}

template

BiNode*BiTree:

:

InsertBST1（BiNode*root,BiNode*s）

{//1在二叉排序树中插入一个结点s，用于后期功能的多个或