用c++实现四叉树算法的完整,具有增删改,检索等功能,并且可以导入文件进行上述功能的示例
时间: 2023-06-25 09:02:38 浏览: 45
以下是一个简单的四叉树算法的实现,包括增删改查等基本功能。这里我们假设四叉树中存储的是二维平面点,每个点有一个唯一的ID和坐标。同时,我们使用文件读写来演示如何导入数据。
```c++
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
// 定义二维平面上的点
struct Point {
int id;
double x, y;
Point(int id_, double x_, double y_) : id(id_), x(x_), y(y_) {}
};
// 定义四叉树节点
class QuadTreeNode {
public:
QuadTreeNode(double x0_, double y0_, double x1_, double y1_) : x0(x0_), y0(y0_), x1(x1_), y1(y1_), isLeaf(true) {}
~QuadTreeNode() {
for (auto& child : children) {
delete child;
}
}
// 插入一个点
bool insert(Point* p) {
if (!contains(p->x, p->y)) {
return false;
}
if (isLeaf) {
points.push_back(p);
if (points.size() > maxPointsPerNode) {
subdivide();
}
return true;
}
for (auto& child : children) {
if (child->insert(p)) {
return true;
}
}
return false;
}
// 删除一个点
bool remove(Point* p) {
if (!contains(p->x, p->y)) {
return false;
}
if (isLeaf) {
for (auto it = points.begin(); it != points.end(); ++it) {
if ((*it)->id == p->id) {
points.erase(it);
return true;
}
}
return false;
}
for (auto& child : children) {
if (child->remove(p)) {
return true;
}
}
return false;
}
// 更新一个点
bool update(Point* p) {
if (remove(p)) {
return insert(p);
}
return false;
}
// 查找包含某个点的所有节点
void search(double x, double y, vector<Point*>& result) {
if (!contains(x, y)) {
return;
}
for (auto& p : points) {
result.push_back(p);
}
if (!isLeaf) {
for (auto& child : children) {
child->search(x, y, result);
}
}
}
private:
double x0, y0, x1, y1;
bool isLeaf;
vector<Point*> points;
vector<QuadTreeNode*> children;
static const int maxPointsPerNode = 4; // 每个节点最多存储的点数
// 判断一个点是否在范围内
bool contains(double x, double y) const {
return x >= x0 && x < x1 && y >= y0 && y < y1;
}
// 分裂一个节点
void subdivide() {
isLeaf = false;
double xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;
children.push_back(new QuadTreeNode(x0, y0, xm, ym));
children.push_back(new QuadTreeNode(xm, y0, x1, ym));
children.push_back(new QuadTreeNode(x0, ym, xm, y1));
children.push_back(new QuadTreeNode(xm, ym, x1, y1));
for (auto& p : points) {
for (auto& child : children) {
if (child->insert(p)) {
break;
}
}
}
points.clear();
}
};
int main() {
// 从文件中读取数据
vector<Point> data;
ifstream fin("data.txt");
int id;
double x, y;
while (fin >> id >> x >> y) {
data.emplace_back(id, x, y);
}
fin.close();
// 构建四叉树
QuadTreeNode root(0, 0, 100, 100);
for (auto& p : data) {
root.insert(&p);
}
// 测试增删改查功能
Point p1(1, 10, 10);
root.insert(&p1);
Point p2(2, 20, 20);
root.update(&p2);
root.remove(&p1);
vector<Point*> result;
root.search(30, 30, result);
for (auto& p : result) {
cout << p->id << " " << p->x << " " << p->y << endl;
}
return 0;
}
```
在这个示例中,我们首先从文件中读取了一些点的数据,然后用这些点构建了一个四叉树。接着,我们对四叉树进行了一些增删改查的操作,并最终输出了包含特定点的所有节点。在实际使用中,你可以根据需要调整节点的最大点数以及节点的范围等参数,以适应不同的场景。
相关推荐
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)