四叉树是一种用于递归地将二维空间划分为四个部分的数据结构。它可以用来表示图像、地形等分层数据，并广泛应用于计算机图形学等领域。 下面是一个简单的 Python 示例，展示如何创建并编码一个基本的四叉树： ```python class QuadTreeNode: def __init__(self, x, y, w, h): self.children = [] # 子节点列表 self.x = x # 当前节点矩形区域左上角x坐标 self.y = y # 当前节点矩形区域左上角y坐标 self.w = w # 宽度 self.h = h # 高度 def subdivide(self): """对当前节点进行划分""" half_w = self.w / 2 half_h = self.h / 2 child1 = QuadTreeNode(self.x, self.y, half_w, half_h) child2 = QuadTreeNode(self.x + half_w, self.y, half_w, half_h) child3 = QuadTreeNode(self.x, self.y + half_h, half_w, half_h) child4 = QuadTreeNode(self.x + half_w, self.y + half_h, half_w, half_h) self.children.extend([child1, child2, child3, child4]) def build_quadtree(root, depth=0, max_depth=3): if depth >= max_depth or root.w <= 1 or root.h <= 1: return root.subdivide() for child in root.children: build_quadtree(child, depth+1, max_depth) # 创建根节点 (假设整个图像是从(0,0)开始宽高各为8单位的空间） root_node = QuadTreeNode(x=0, y=0, w=8, h=8) build_quadtree(root_node, max_depth=3) # 打印每个叶子节点的信息（仅作为验证用途） for node in get_all_leaves(root_node): print(f"Node at ({node.x}, {node.y}), size: {node.w}x{node.h}") def get_all_leaves(node): leaves = [] if not node.children: leaves.append(node) else: for child in node.children: leaves.extend(get_all_leaves(child)) return leaves ``` ### 解释： - `QuadTreeNode` 类代表了四叉树的一个节点。 - 每次调用 `subdivide()` 方法会将该节点分成四个更小的部分。 - `build_quadtree` 函数负责递归构建整棵四叉树直到达到最大深度或其他停止条件为止。 - 最后的打印函数遍历所有叶节点并且输出它们的位置和尺寸信息。 注意，在实际应用中可以根据需要添加更多功能如插入元素到对应的象限内等等操作；此外还需要考虑边界情况处理以及性能优化等问题。