用模板类函数写KDtree

当使用模板类函数来实现KD树时，可以按照以下方式编写代码:

#include <iostream>
#include <vector>

template <typename T, size_t K>
struct KDNode {
    std::array<T, K> point;
    KDNode<T, K>* left;
    KDNode<T, K>* right;
    
    KDNode(const std::array<T, K>& p) : point(p), left(nullptr), right(nullptr) {}
};

template <typename T, size_t K>
class KDTree {
private:
    KDNode<T, K>* root;

    KDNode<T, K>* buildTree(std::vector<std::array<T, K>>& points, size_t depth) {
        if (points.empty()) {
            return nullptr;
        }

        size_t axis = depth % K;
        auto cmp = [axis](const std::array<T, K>& a, const std::array<T, K>& b) {
            return a[axis] < b[axis];
        };
        std::sort(points.begin(), points.end(), cmp);

        size_t median = points.size() / 2;
        KDNode<T, K>* node = new KDNode<T, K>(points[median]);
        node->left = buildTree(std::vector<std::array<T, K>>(points.begin(), points.begin() + median), depth + 1);
        node->right = buildTree(std::vector<std::array<T, K>>(points.begin() + median + 1, points.end()), depth + 1);

        return node;
    }

public:
    KDTree() : root(nullptr) {}

    void build(std::vector<std::array<T, K>>& points) {
        root = buildTree(points, 0);
    }
};

使用示例代码：

int main() {
    std::vector<std::array<int, 2>> points{{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}};
    KDTree<int, 2> tree;
    tree.build(points);
    return 0;
}

以上代码实现了一个简单的KD树，其中`T`表示点的坐标数据类型，`K`表示点的维度。`KDNode`结构体表示KD树的节点，`KDTree`类则表示整个KD树的数据结构。`buildTree`函数用于递归地构建KD树，`build`函数用于构建整个KD树。

注意：以上代码只是一个简单的示例，实际应用中可能需要根据具体情况进行更多的优化和功能扩展。