发布时间 : 星期日 文章基于BST(二叉排序树)的城市信息管理更新完毕开始阅读f0824ec44431b90d6d85c76b
一、 设计题目 【问题描述】
利用二叉排序树实现城市信息管理，城市信息包括城市名、城市坐标（X,Y）。 【基本要求】
将若干城市信息按城市名的顺序建立二叉排序树； 可以插入一个城市信息； 按城市名查找一个城市信息；
输入一个城市名，查找和该城市名的距离在指定范围内的所有城市。 【测试数据】 自己指定。 【选作内容】
删除一个城市信息。 二、需求分析
1）运行环境（软、硬件环境） Microsoft visual c++6.0 PC+window 7
2）输入的形式和输入值的范围 输入城市信息，例如：“城市名左坐标右坐标”的形式。输入的左右坐标是整型的，城市名是字符串（以中文的形式）。左右坐标为100内的整数。 3）输出的形式描述
输出的是城市信息，就是例如：“城市名左坐标右坐标”的形式。 4）功能描述
输入参数包括：城市名，左坐标，右坐标； 需要插入的城市与左右坐标；需要查找的城市名；需要查找周围城市信息的城市名与搜索范围；需要删除的城市名。 功能要求：
1.将若干城市信息按城市名的顺序建立二叉排序树； 2.可以插入一个城市信息； 3.按城市名查找一个城市信息；
4.输入一个城市名，查找和该城市名的距离在指定范围内的所有城市。 5.删除一个城市信息（选作）。 5）测试数据
输入的城市信息： 兰州（5,6） 成都（3,4） 西安（4,9） 上海（2,8） 北京（1,3）
需要插入的城市：银川（3,5） 需要查找的城市：兰州
需要查找哪个城市周围城市：西宁 查找范围：20
1
需要删除的城市名：新疆（选做） 三、概要设计
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），对已创建的二叉排序树进行中序遍历输出。
2
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）模块层次调用关系图 各模块之间的关系图：
3
前序遍历城市信息表 主菜单提示 中序遍历城市信息表 后序遍历城市信息表 查询城市信息 查找指定范围内的城市 插入一个城市 删除一个城市 退出 四、详细设计
实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。
1.二叉排序树的定义
二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树： ①若它的左子树非空，则左子树上所有结点的值均小于根结点的值； ②若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ③左、右子树本身又各是一棵二叉排序树。
上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。 template
public: BiTree(T a[],int n);//带参构造函数 BiNode
4