该回答引用ChatGPT辅助答疑,若有帮助,还请题主采纳。
四叉树是一种将二维空间分为四个象限的数据结构,每个节点最多有四个子节点,分别表示左上、右上、左下、右下四个子区域。给定一个二维空间范围 x∈[0,10]
,y∈[0,10]
,并且有若干个点,要求通过四叉树来进行存储,并按层序遍历的顺序输出每个点。
下面是一个 C++ 实现四叉树创建和层序遍历输出的代码:
四叉树的实现步骤
- 定义四叉树的节点:每个节点包含一个点
(x, y)
和四个子节点(分别表示左上、右上、左下、右下)。 - 插入点:将点插入四叉树,按照其坐标判断应该插入到哪个象限。
- 层序遍历:使用队列(Queue)进行层序遍历。
代码实现
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Point {
float x, y;
Point(float _x, float _y) : x(_x), y(_y) {}
};
struct QuadTreeNode {
Point point;
float x_min, x_max, y_min, y_max;
QuadTreeNode *children[4];
QuadTreeNode(Point p, float x_min, float x_max, float y_min, float y_max)
: point(p), x_min(x_min), x_max(x_max), y_min(y_min), y_max(y_max) {
for (int i = 0; i < 4; i++) {
children[i] = nullptr;
}
}
};
class QuadTree {
public:
QuadTree(float x_min, float x_max, float y_min, float y_max)
: root(nullptr), x_min(x_min), x_max(x_max), y_min(y_min), y_max(y_max) {}
void insert(Point p) {
root = insert(root, p, x_min, x_max, y_min, y_max);
}
void levelOrderTraversal() {
if (!root) return;
queue<QuadTreeNode*> q;
q.push(root);
while (!q.empty()) {
QuadTreeNode* node = q.front();
q.pop();
cout << node->point.x << " " << node->point.y << endl;
for (int i = 0; i < 4; i++) {
if (node->children[i]) {
q.push(node->children[i]);
}
}
}
}
private:
QuadTreeNode *root;
float x_min, x_max, y_min, y_max;
QuadTreeNode* insert(QuadTreeNode* node, Point p, float x_min, float x_max, float y_min, float y_max) {
if (!node) {
return new QuadTreeNode(p, x_min, x_max, y_min, y_max);
}
float x_mid = (x_min + x_max) / 2;
float y_mid = (y_min + y_max) / 2;
int quadrant = getQuadrant(p, x_mid, y_mid);
if (node->children[quadrant] == nullptr) {
if (quadrant == 0) {
node->children[0] = new QuadTreeNode(p, x_min, x_mid, y_mid, y_max);
} else if (quadrant == 1) {
node->children[1] = new QuadTreeNode(p, x_mid, x_max, y_mid, y_max);
} else if (quadrant == 2) {
node->children[2] = new QuadTreeNode(p, x_min, x_mid, y_min, y_mid);
} else if (quadrant == 3) {
node->children[3] = new QuadTreeNode(p, x_mid, x_max, y_min, y_mid);
}
} else {
insert(node->children[quadrant], p, x_min, x_max, y_min, y_max);
}
return node;
}
int getQuadrant(Point p, float x_mid, float y_mid) {
if (p.x <= x_mid && p.y > y_mid) return 0;
if (p.x > x_mid && p.y > y_mid) return 1;
if (p.x <= x_mid && p.y <= y_mid) return 2;
if (p.x > x_mid && p.y <= y_mid) return 3;
return -1;
}
};
int main() {
QuadTree qt(0, 10, 0, 10);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
float x, y;
cin >> x >> y;
qt.insert(Point(x, y));
}
qt.levelOrderTraversal();
return 0;
}
代码说明:
- Point 结构体:表示一个二维点,包含
x
和 y
坐标。 - QuadTreeNode 结构体:表示四叉树的节点,保存一个点以及该节点的区域范围和四个子节点。
- QuadTree 类:包含插入点的方法
insert()
,以及层序遍历方法 levelOrderTraversal()
。 - insert 方法:根据点的位置,决定它应该插入哪个子区域(左上、右上、左下、右下)。如果该子区域已经有子节点,则递归插入。
- levelOrderTraversal 方法:使用队列进行层序遍历,输出所有点。
输入示例:
7
2 5
3 7.5
4.2 6.8
5 2.5
8 5.6
7 3.5
5.5 3.5
输出示例:
8 5.6
2 5
5 2.5
3 7.5
4.2 6.8
5.5 3.5
7 3.5
总结:
- 这段代码通过四叉树将二维空间划分为四个象限并存储点数据,使用层序遍历输出所有点的顺序。
- 插入点时,根据点的坐标决定它应放在哪个象限,如果该象限已经有子节点则递归插入。