用C++实现四叉树
时间: 2023-07-11 21:20:35 浏览: 62
四叉树是一种二叉树的变体,它将平面空间递归分成四个象限。下面是C++代码实现:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 定义节点结构体
struct Node {
int x, y, val;
Node *nw, *ne, *sw, *se;
Node(int x, int y, int val) : x(x), y(y), val(val), nw(NULL), ne(NULL), sw(NULL), se(NULL) {}
};
// 定义四叉树类
class QuadTree {
private:
Node *root; // 根节点
int size; // 树的大小
// 插入节点
Node* insert(Node *node, int x, int y, int val) {
if (node == NULL) {
// 如果节点为空,则新建一个节点
size++;
return new Node(x, y, val);
}
if (node->x == x && node->y == y) {
// 如果节点已存在,则更新节点的值
node->val = val;
return node;
}
if (x < node->x && y < node->y) {
// 如果点在左下象限,则递归到左下子树
node->sw = insert(node->sw, x, y, val);
} else if (x < node->x && y >= node->y) {
// 如果点在左上象限,则递归到左上子树
node->nw = insert(node->nw, x, y, val);
} else if (x >= node->x && y < node->y) {
// 如果点在右下象限,则递归到右下子树
node->se = insert(node->se, x, y, val);
} else {
// 如果点在右上象限,则递归到右上子树
node->ne = insert(node->ne, x, y, val);
}
return node;
}
// 查询节点
Node* query(Node *node, int x, int y) {
if (node == NULL) {
// 如果节点为空,则返回NULL
return NULL;
}
if (node->x == x && node->y == y) {
// 如果节点匹配,则返回节点
return node;
}
if (x < node->x && y < node->y) {
// 如果点在左下象限,则递归到左下子树
return query(node->sw, x, y);
} else if (x < node->x && y >= node->y) {
// 如果点在左上象限,则递归到左上子树
return query(node->nw, x, y);
} else if (x >= node->x && y < node->y) {
// 如果点在右下象限,则递归到右下子树
return query(node->se, x, y);
} else {
// 如果点在右上象限,则递归到右上子树
return query(node->ne, x, y);
}
}
public:
// 构造函数
QuadTree() : root(NULL), size(0) {}
// 插入节点
void insert(int x, int y, int val) {
root = insert(root, x, y, val);
}
// 查询节点
Node* query(int x, int y) {
return query(root, x, y);
}
// 获取树的大小
int getSize() {
return size;
}
};
int main() {
QuadTree tree;
tree.insert(0, 0, 1);
tree.insert(1, 1, 2);
tree.insert(2, 2, 3);
tree.insert(3, 3, 4);
Node *node = tree.query(1, 1);
if (node != NULL) {
cout << "Node value: " << node->val << endl;
} else {
cout << "Node not found!" << endl;
}
cout << "Tree size: " << tree.getSize() << endl;
return 0;
}
```
以上代码实现了四叉树的插入和查询功能,可以根据需要进行修改。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.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)