KD树构建异常：根节点无预期子节点的递归问题排查求助

问题根源 #

你遇到的根节点无有效子节点问题，核心有两处错误：

1. Node类初始化逻辑错误：__init__方法接收了left和right参数，但强制将self.left和self.right赋值为None，导致传入的子节点被直接丢弃。
2. 递归未切换分割轴：KD-Tree要求每层递归使用不同坐标轴分割，原代码始终用初始轴，不符合树结构规则。

修正后的完整代码 #

import numpy as np

class Node():
    def __init__(self, point, min_ax, max_ax, axis, left=None, right=None):
        self.point = point
        self.min_ax = min_ax
        self.max_ax = max_ax
        self.axis = axis
        # 直接使用传入的子节点参数，不再强制置空
        self.left = left
        self.right = right

def construct_kd_tree(points, axis=0):
    if len(points) == 0:
        return None

    # 按当前轴排序点集
    vals = list(sorted(points, key=lambda x: x[axis]))
    median = len(points) // 2
    # 递归时切换到下一个坐标轴（循环遍历所有维度）
    next_axis = (axis + 1) % len(points[0])
    left = construct_kd_tree(vals[:median], next_axis)
    right = construct_kd_tree(vals[median+1:], next_axis)

    return Node(vals[median],
                vals[0][axis],
                vals[-1][axis],
                axis,
                left=left,
                right=right)


points = np.random.rand(10,3)
node = construct_kd_tree(points)

print(node.left)  # 现在会输出子节点对象，而非None
print(node.right) # 现在会输出子节点对象，而非None

关键修正说明 #

• 修复Node类初始化：删除self.left = None和self.right = None，保留传入的子节点引用，确保子节点能正确挂载到父节点。
• 递归切换分割轴：每次递归调用时，通过(axis + 1) % 维度数切换到下一个坐标轴，符合KD-Tree的分层分割逻辑。

内容的提问来源于stack exchange，提问作者cabbage_queen