kd tree c代码实现

KD树（K-Dimensional Tree）是一种用于高维空间搜索的数据结构，它可以高效地找到给定点的最近邻点。下面是一个简单的KD树C代码实现的示例：

#include <stdio.h>
#include <stdlib.h>

// 结点结构定义
struct Node {
    int point[2];
    struct Node *left;
    struct Node *right;
};

// 创建新结点
struct Node* createNode(int point[]) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    for (int i = 0; i < 2; i++) {
        newNode->point[i] = point[i];
    }
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 插入结点
struct Node* insertNode(struct Node* root, int point[], int depth) {
    if (root == NULL) {
        return createNode(point);
    }
    
    int splitDim = depth % 2;
    if (point[splitDim] < root->point[splitDim]) {
        root->left = insertNode(root->left, point, depth + 1);
    } else {
        root->right = insertNode(root->right, point, depth + 1);
    }
    
    return root;
}

// KD树的遍历
void traverseKdTree(struct Node* root) {
    if (root == NULL) {
        return;
    }
    
    traverseKdTree(root->left);
    printf("(%d, %d) ", root->point[0], root->point[1]);
    traverseKdTree(root->right);
}

int main() {
    struct Node* root = NULL;
    int points[][2] = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}};
    int size = sizeof(points) / sizeof(points[0]);
    
    for (int i = 0; i < size; i++) {
        root = insertNode(root, points[i], 0);
    }
    
    traverseKdTree(root);
    
    return 0;
}

在这个示例中，我们首先定义了一个结点结构，其中包含一个二维点的坐标，以及指向该结点左右子结点的指针。然后，我们实现了创建结点的函数，该函数会根据给定的点坐标创建一个新的结点。接下来，我们实现了插入结点的函数，该函数会根据点在当前维度上的大小，将其插入到适当的子结点中。最后，我们实现了一个遍历KD树的函数，用于按序输出树中的所有点。

在`main`函数中，我们创建了一个空的KD树并初始化了一个点数组。然后，我们依次将数组中的点插入到KD树中，并调用遍历函数输出树中的所有点。

请注意，这只是一个简单的KD树实现示例，可能并没有考虑到所有的情况。实际上，KD树的实现可以更加复杂和灵活，具体取决于应用场景和需求。