以下代码展示了如何使用C++中的`std::uniform_real_distribution`和`std::mt19937`生成二维随机空间点数据集，并基于这些点构造一个简单的kd树。 ### 代码实现 ```cpp #include <iostream> #include <vector> #include <random> #include <memory> #include <algorithm> // 定义点结构体 struct Point { double x, y; int id; Point(double x_, double y_, int id_) : x(x_), y(y_), id(id_) {} }; // 定义节点结构体 struct Node { Point point; std::shared_ptr<Node> left, right; Node(Point p) : point(p), left(nullptr), right(nullptr) {} }; // 构造kd树的函数 std::shared_ptr<Node> build_kd_tree(const std::vector<Point>& points, int depth = 0) { if (points.empty()) return nullptr; // 根据当前深度选择轴（x或y） int axis = depth % 2; // 按照选定的轴排序 auto compare_x = [](const Point& a, const Point& b) { return a.x < b.x; }; auto compare_y = [](const Point& a, const Point& b) { return a.y < b.y; }; std::vector<Point> sorted_points = points; if (axis == 0) { std::sort(sorted_points.begin(), sorted_points.end(), compare_x); } else { std::sort(sorted_points.begin(), sorted_points.end(), compare_y); } // 找到中位数作为分割点 size_t median = sorted_points.size() / 2; std::shared_ptr<Node> node = std::make_shared<Node>(sorted_points[median]); // 递归构建左右子树 std::vector<Point> left_points(sorted_points.begin(), sorted_points.begin() + median); std::vector<Point> right_points(sorted_points.begin() + median + 1, sorted_points.end()); node->left = build_kd_tree(left_points, depth + 1); node->right = build_kd_tree(right_points, depth + 1); return node; } // 打印kd树（用于调试） void print_kd_tree(const std::shared_ptr<Node>& node, int depth = 0) { if (!node) return; std::cout << std::string(depth * 2, ' ') << "Point(" << node->point.x << ", " << node->point.y << ", id=" << node->point.id << ")\n"; print_kd_tree(node->left, depth + 1); print_kd_tree(node->right, depth + 1); } int main() { // 随机数生成器 std::random_device rd; std::mt19937 gen(rd()); std::uniform_real_distribution<> dis(-100.0, 100.0); // 生成随机点数据集 std::vector<Point> points; for (int i = 0; i < 10; ++i) { points.emplace_back(dis(gen), dis(gen), i); } // 输出生成的点 std::cout << "Generated Points:\n"; for (const auto& p : points) { std::cout << "Point(" << p.x << ", " << p.y << ", id=" << p.id << ")\n"; } // 构建kd树 std::shared_ptr<Node> root = build_kd_tree(points); // 打印kd树 std::cout << "\nKD Tree Structure:\n"; print_kd_tree(root); return 0; } ``` --- ### 解释 1. **随机点生成**： - 使用`std::mt19937`作为随机数引擎，`std::uniform_real_distribution`定义均匀分布。 - 在`main`函数中，通过循环生成10个随机点，每个点的坐标范围为`[-100.0, 100.0]`。 2. **kd树构建**： - `build_kd_tree`函数递归地构建kd树。 - 每次递归时，根据当前深度`depth`选择切分轴（`x`或`y`）。 - 对点按选定的轴排序后，取中位数作为当前节点，并递归构建左右子树。 3. **打印kd树**： - `print_kd_tree`函数用于递归打印kd树的结构，便于验证结果。 --- ###