### 如何用 Python 实现 kd 树 kd 树是一种用于高效存储和查询 k 维空间数据的树形结构。以下是基于已有引用内容以及专业知识构建的一个完整的 `kd` 树实现。 #### 定义节点类 首先定义一个表示树中节点的类，该类包含当前节点的值、左右子树指针以及划分维度的信息： ```python class KdNode: def __init__(self, point=None, dim=None, left=None, right=None): self.point = point # 节点坐标 self.dim = dim # 划分维度 self.left = left # 左子树 self.right = right # 右子树 ``` 此部分描述了节点的核心属性[^2]。 #### 构建 kd 树 接下来是一个函数来递归地构建 kd 树。它通过不断选择最佳分割轴并按顺序排列点集来进行操作。 ```python import numpy as np def build_kdtree(points, depth=0): n = len(points) if n == 0: return None # 当前维度由深度决定 (循环遍历各维) axis = depth % len(points[0]) # 对当前维度上的点进行排序 sorted_points = sorted(points, key=lambda point: point[axis]) # 找到中间点作为当前节点 median_idx = n // 2 median_point = sorted_points[median_idx] # 创建新节点，并递归构造其左右子树 node = KdNode( point=median_point, dim=axis, left=build_kdtree(sorted_points[:median_idx], depth + 1), right=build_kdtree(sorted_points[median_idx + 1:], depth + 1) ) return node ``` 这段代码实现了动态调整分裂方向的功能[^3]。 #### 遍历 kd 树 为了验证树是否正确建立，可以编写一个简单的先序遍历方法打印所有节点信息。 ```python def traverse_kdtree(node, depth=0): if node is not None: indent = ' ' * depth print(f"{indent}Depth {depth}, Dimension {node.dim}: Point {node.point}") traverse_kdtree(node.left, depth + 1) traverse_kdtree(node.right, depth + 1) ``` 以上逻辑展示了如何逐层访问整个树状结构中的每一个元素[^1]。 #### 测试案例 最后提供一段测试脚本展示上述功能的实际应用效果。 ```python if __name__ == "__main__": points = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]] root = build_kdtree(points) traverse_kdtree(root) ``` 运行结果会按照预期输出各个层次下的具体位置关系[^4]。 ---