八叉树是一种树数据结构，其中每个内部节点最多可以拥有 8 个子节点。就像二叉树将空间划分为两个部分一样，八叉树将空间最多划分为八个部分，我们称之为“八分体”。它主要用于存储需要占用大量空间的 3D 点。如果八叉树的所有内部节点都恰好包含 8 个子节点，那么我们就称它为完全八叉树。它在高分辨率图形领域（如 3D 计算机图形）也非常有用。
我们可以通过以下步骤从 3D 体积生成八叉树：
- 将当前的 3D 体积划分为 8 个盒子
- 如果任何盒子包含不止一个点，则将其进一步划分为更小的盒子
- 不要分割包含一个或零个点的盒子
- 重复此过程，直到所有盒子都只包含一个或零个点
上述步骤如下图所示。
!Imagination of above algorithm
如果 S 是每个维度上的点数，那么八叉树中形成的节点数由以下公式给出：(S^{3} -1)/7。
八叉树中的插入
- 为了在八叉树中插入一个节点，首先我们要检查该节点是否存在。如果节点已经存在，我们直接返回；否则，我们进行递归操作。
- 首先，我们从根节点开始，并将其标记为当前节点。
- 然后，我们要找到可以存储该点的子节点。
- 如果该节点为空，我们将其替换为我们要插入的节点，并将其设为叶子节点。
- 如果该节点是叶子节点，我们将其转换为内部节点；如果它已经是内部节点，则进入其子节点。此过程递归执行，直到找到一个空节点为止。
- 此函数的时间复杂度为
O(log(N))，其中 N 是节点的数量。
八叉树中的搜索
- 此函数用于搜索树中是否存在某个点。
- 从根节点开始，如果找到包含给定点的节点，则递归搜索并返回 true；如果遇到空节点、边界点或空点，则返回 false。
- 如果找到内部节点，则进入该节点。此函数的时间复杂度也是
O(log N)，其中 N 是节点的数量。
下面是上述方法的实现
CPP14
// c++ 中的八叉树实现
#include
#include
using namespace std;
#define TopLeftFront 0
#define TopRightFront 1
#define BottomRightFront 2
#define BottomLeftFront 3
#define TopLeftBottom 4
#define TopRightBottom 5
#define BottomRightBack 6
#define BottomLeftBack 7
// 点的结构体
struct Point {
int x;
int y;
int z;
Point()
: x(-1), y(-1), z(-1)
{
}
Point(int a, int b, int c)
: x(a), y(b), z(c)
{
}
};
// 八叉树类
class Octree {
// 如果 point == NULL，节点是内部节点。
// 如果 point == (-1, -1, -1)，节点是空的。
Point* point;
// 表示立方体的边界
Point topLeftFront, bottomRightBack;
vector children;
public:
// 构造函数
Octree()
{
// 声明空节点
point = new Point();
}
// 带有三个参数的构造函数
Octree(int x, int y, int z)
{
// 声明点节点
point = new Point(x, y, z);
}
// 带有六个参数的构造函数
Octree(int x1, int y1, int z1, int x2, int y2, int z2)
{
// 这用于构造定义了边界的八叉树
if (x2 < x1
|| y2 < y1
|| z2 < z1) {
cout << "边界点无效" << endl;
return;
}
point = nullptr;
topLeftFront
= new Point(x1, y1, z1);
bottomRightBack
= new Point(x2, y2, z2);
// 将子节点赋值为 null
children.assign(8, nullptr);
for (int i = TopLeftFront;
i <= BottomLeftBack;
++i)
children[i] = new Octree();
}
// 在八叉树中插入一个点的函数
void insert(int x,
int y,
int z)
{
// 如果该点已经存在于八叉树中
if (find(x, y, z)) {
cout << "点已存在于树中" << endl;
return;
}
// 如果该点越界
if (x x
|| x > bottomRightBack->x
|| y y
|| y > bottomRightBack->y
|| z z
|| z > bottomRightBack->z) {
cout << "点越界" << endl;
return;
}
// 二分搜索以插入该点
int midx = (topLeftFront->x
+ bottomRightBack->x)
/ 2;
int midy = (topLeftFront->y
+ bottomRightBack->y)
/ 2;
int midz = (topLeftFront->z
+ bottomRightBack->z)
/ 2;
int pos = –