C++四叉树
时间: 2023-07-11 18:15:29 浏览: 78
C++ 四叉树是一种基于分治思想的数据结构,常用于处理二维平面上的数据。它将空间划分为四个象限,每个象限又可以继续划分成四个象限,以此类推,直到空间被划分为足够小的块为止。每个块可以存储多个数据点,或者指向更小的子块。
四叉树可以用来解决许多空间相关的问题,如碰撞检测、区域查找、图像处理等。在实现时,可以使用递归算法,也可以使用迭代算法。常见的操作包括插入数据点、删除数据点、查找数据点、遍历整棵树等。
以下是一个简单的 C++ 四叉树实现的示例代码:
```c++
#include <iostream>
using namespace std;
struct Point {
int x, y;
Point(int _x, int _y) : x(_x), y(_y) {}
};
struct QuadtreeNode {
Point* point;
QuadtreeNode* children[4];
QuadtreeNode() {
point = nullptr;
for (int i = 0; i < 4; i++) {
children[i] = nullptr;
}
}
};
class Quadtree {
public:
Quadtree(int _width, int _height) : root(nullptr), width(_width), height(_height) {}
void insert(Point* p) {
root = insert(root, p, 0, 0, width, height);
}
bool contains(Point* p) {
return contains(root, p, 0, 0, width, height);
}
private:
QuadtreeNode* root;
int width, height;
QuadtreeNode* insert(QuadtreeNode* node, Point* p, int left, int top, int right, int bottom) {
if (node == nullptr) {
node = new QuadtreeNode();
}
if (node->point == nullptr) {
node->point = p;
}
else {
int midX = (left + right) / 2;
int midY = (top + bottom) / 2;
if (p->x < midX) {
if (p->y < midY) {
node->children[0] = insert(node->children[0], p, left, top, midX, midY);
}
else {
node->children[1] = insert(node->children[1], p, left, midY, midX, bottom);
}
}
else {
if (p->y < midY) {
node->children[2] = insert(node->children[2], p, midX, top, right, midY);
}
else {
node->children[3] = insert(node->children[3], p, midX, midY, right, bottom);
}
}
}
return node;
}
bool contains(QuadtreeNode* node, Point* p, int left, int top, int right, int bottom) {
if (node == nullptr) {
return false;
}
if (node->point != nullptr) {
return node->point->x == p->x && node->point->y == p->y;
}
else {
int midX = (left + right) / 2;
int midY = (top + bottom) / 2;
if (p->x < midX) {
if (p->y < midY) {
return contains(node->children[0], p, left, top, midX, midY);
}
else {
return contains(node->children[1], p, left, midY, midX, bottom);
}
}
else {
if (p->y < midY) {
return contains(node->children[2], p, midX, top, right, midY);
}
else {
return contains(node->children[3], p, midX, midY, right, bottom);
}
}
}
}
};
int main() {
Quadtree quadtree(100, 100);
Point p1(10, 20);
Point p2(30, 40);
quadtree.insert(&p1);
quadtree.insert(&p2);
cout << quadtree.contains(&p1) << endl; // 输出 1
cout << quadtree.contains(&p2) << endl; // 输出 1
Point p3(50, 60);
cout << quadtree.contains(&p3) << endl; // 输出 0
return 0;
}
```
该示例代码实现了一个简单的四叉树,用于存储坐标在二维平面上的点。其中 `Point` 结构体表示一个点,`QuadtreeNode` 结构体表示一个四叉树节点,`Quadtree` 类表示一个四叉树。 `insert` 方法用于插入一个点,`contains` 方法用于查找一个点是否存在。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.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)
![](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)