用c++控制台应用实现四叉树算法的完整,具有增删改,检索等功能,并且可以导入文件进行上述功能的示例
时间: 2023-06-20 12:09:28 浏览: 48
以下是一个基于C++控制台应用的四叉树算法示例,包括增删改、检索和导入文件功能。代码中使用了STL库中的vector和fstream,需要在编译时链接这两个库。
```c++
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
// 定义四叉树节点
class QuadTreeNode {
public:
int x, y; // 节点坐标
QuadTreeNode* children[4]; // 子节点
QuadTreeNode(int x, int y) : x(x), y(y) {
for (int i = 0; i < 4; i++) {
children[i] = NULL;
}
}
};
// 定义四叉树
class QuadTree {
private:
QuadTreeNode* root; // 根节点
// 递归插入节点
void insert(QuadTreeNode* node, int x, int y) {
if (node->children[0] == NULL) { // 如果没有子节点,插入到该节点
node->children[0] = new QuadTreeNode(x, y);
} else { // 否则递归插入到子节点
int index = getIndex(node, x, y);
if (index != -1) {
insert(node->children[index], x, y);
} else { // 如果点恰好在该节点分界线上,插入到该节点
node->children[0] = new QuadTreeNode(x, y);
}
}
}
// 递归删除节点
void remove(QuadTreeNode* node, int x, int y) {
if (node->children[0] == NULL) { // 如果没有子节点,该节点就是要删除的节点
delete node;
node = NULL;
} else { // 否则递归删除子节点
int index = getIndex(node, x, y);
if (index != -1) {
remove(node->children[index], x, y);
}
}
}
// 递归查找节点
QuadTreeNode* search(QuadTreeNode* node, int x, int y) {
if (node->children[0] == NULL) { // 如果没有子节点,该节点就是要查找的节点
return node;
} else { // 否则递归查找子节点
int index = getIndex(node, x, y);
if (index != -1) {
return search(node->children[index], x, y);
} else { // 如果点恰好在该节点分界线上,返回该节点
return node;
}
}
}
// 获取点所在的象限
int getIndex(QuadTreeNode* node, int x, int y) {
int midX = (node->x + node->children[1]->x) / 2;
int midY = (node->y + node->children[2]->y) / 2;
if (x >= node->x && x <= midX && y >= node->y && y <= midY) {
return 1;
} else if (x >= midX && x <= node->children[1]->x && y >= node->y && y <= midY) {
return 0;
} else if (x >= node->x && x <= midX && y >= midY && y <= node->children[2]->y) {
return 2;
} else if (x >= midX && x <= node->children[1]->x && y >= midY && y <= node->children[2]->y) {
return 3;
}
return -1; // 点恰好在节点分界线上
}
// 递归清空节点
void clear(QuadTreeNode* node) {
if (node != NULL) {
for (int i = 0; i < 4; i++) {
clear(node->children[i]);
}
delete node;
node = NULL;
}
}
public:
QuadTree(int width, int height) {
root = new QuadTreeNode(0, 0);
root->children[1] = new QuadTreeNode(width, 0);
root->children[2] = new QuadTreeNode(0, height);
root->children[3] = new QuadTreeNode(width, height);
}
~QuadTree() {
clear(root);
}
// 插入节点
void insert(int x, int y) {
insert(root, x, y);
}
// 删除节点
void remove(int x, int y) {
remove(root, x, y);
}
// 查找节点
QuadTreeNode* search(int x, int y) {
return search(root, x, y);
}
// 清空四叉树
void clear() {
clear(root);
root = new QuadTreeNode(0, 0);
}
// 从文件导入节点
void load(const char* filename) {
ifstream in(filename);
int x, y;
while (in >> x >> y) {
insert(x, y);
}
}
// 将节点导出到文件
void save(const char* filename) {
ofstream out(filename);
vector<pair<int, int>> points;
getPoints(root, points);
for (int i = 0; i < points.size(); i++) {
out << points[i].first << ' ' << points[i].second << endl;
}
}
// 获取所有节点
void getPoints(QuadTreeNode* node, vector<pair<int, int>>& points) {
if (node->children[0] == NULL) { // 如果没有子节点,该节点就是一个点
points.push_back(make_pair(node->x, node->y));
} else { // 否则递归获取子节点
for (int i = 0; i < 4; i++) {
getPoints(node->children[i], points);
}
}
}
};
int main() {
QuadTree quadTree(100, 100); // 创建100x100的四叉树
// 插入节点
quadTree.insert(20, 30);
quadTree.insert(40, 50);
quadTree.insert(60, 70);
// 删除节点
quadTree.remove(40, 50);
// 查找节点
QuadTreeNode* node = quadTree.search(20, 30);
if (node != NULL) {
cout << "Found node at (" << node->x << ", " << node->y << ")" << endl;
}
// 导入节点
quadTree.load("points.txt");
// 导出节点
quadTree.save("points_out.txt");
// 清空四叉树
quadTree.clear();
return 0;
}
```
该示例中,QuadTreeNode表示四叉树节点,QuadTree表示四叉树,包括插入节点、删除节点、查找节点、清空四叉树等基本操作,以及从文件导入节点和导出节点到文件的操作。可以通过修改main函数中的操作来测试四叉树算法的各种功能。