本算法思想来自于李航的《统计学习方法》本文主要实现其kd树最近邻的搜索
构造代码已经发表过了，现在也还是写一下，
//为了方便储存数据 public class Data { public double x1; public double x2; } //kd树的代码 public class Tree { public Tree left;//左节点 public Tree father;//父节点 public Tree right;//右节点 public Data mData;//节点的数据 public int split;//判断维数 public void setSplit(int split) { this.split = split; } public int getSplit() { return split; } } //构造kd树 private static void builtTree(Tree root, Data[] datas) { if (datas == null) return;//当没有的时候说明这个不能成为节点 if (datas.length == 1) { //只有一个就是他自己了，它和第一个判断不能换位置 root.mData = datas[0];//设置数据 return; } else { dataSort(datas, root.getSplit() % 2); //进行数据的排列，注意传参判断其是第几维划分 root.left = new Tree();root.left.father = root; root.left.setSplit(root.getSplit() + 1);//不要忘记写其左右节点的维度 int middle = datas.length / 2; //进行数据的对分 root.mData = datas[middle]; Data leftData[] = new Data[middle]; for (int j = 0; j < middle; j++) { leftData[j] = datas[j]; } Data rightData[]; if (datas.length == 2) { rightData = null; } else { root.right = new Tree();root.right.father = root; root.right.setSplit(root.getSplit() + 1); rightData = new Data[datas.length - 1 - middle]; for (int k = middle + 1, j = 0; k < datas.length; k++, j++) { rightData[j] = datas[k]; } } builtTree(root.left, leftData); //递归 builtTree(root.right, rightData); } } private static void dataSort(Data[] datas, int i) {//冒泡排序法 if (i == 0) { for (int k = 0; k < datas.length - 1; k++) { for (int j = 0; j < datas.length - 1 - k; j++) { if (datas[j].x1 > datas[j + 1].x1) { Data temp = datas[j]; datas[j] = datas[j + 1]; datas[j + 1] = temp; } } } } else { for (int k = 0; k < datas.length - 1; k++) { for (int j = 0; j < datas.length - 1 - k; j++) { if (datas[j].x2 > datas[j + 1].x2) { Data temp = datas[j]; datas[j] = datas[j + 1]; datas[j + 1] = temp; } } } } } //寻找叶节点 private static Tree find(Tree root, Data testData) {//查找叶节点 int s = root.split%2; if(root.left==null)return root; else { if(s==0){ if(root.mData.x1>testData.x1)root = find(root.left,testData); else root = find(root.right,testData); }else{ if(root.mData.x2>testData.x2)root = find(root.left,testData); else root = find(root.right,testData); } } return root; } private static double range(Data mData, Data testData) {//计算欧式距离 double sum = (mData.x1 - testData.x1)*(mData.x1 - testData.x1)+(mData.x2 - testData.x2)*(mData.x2 - testData.x2); return Math.sqrt(sum); } private static Data findmin(Tree test, Data testData) { double minran = range(test.mData,testData); Tree minTree = test; Tree nowTree = test; while(nowTree.father!=null){ int s = nowTree.split%2; double nowran = range(nowTree.mData,testData);//判断当前节点距离，如果小于就取当前点 if(nowran<minran) { minran = nowran; minTree = nowTree; } if(s==0){ //根据维数判断其半径是否相交，越界就从父节点的另一节点开始 if(nowTree.father.mData.x2 - testData.x2<=minran){ if(nowTree == nowTree.father.left) { Tree temp = find(nowTree.father.right,testData); nowran = range(temp.mData,testData); if(nowran<minran) { minran = nowran; minTree = temp; } nowTree = nowTree.father; } else { Tree temp = find(nowTree.father.left,testData); nowran = range(temp.mData,testData); if(nowran<minran) { minran = nowran; minTree = temp; } nowTree = nowTree.father; }; } else{ //没有相交，可以继续倒退 nowTree = nowTree.father; } } else{ if(nowTree.father.mData.x1 - testData.x1<=minran){//于上面类似 if(nowTree == nowTree.father.left) { Tree temp = find(nowTree.father.right,testData); nowran = range(temp.mData,testData); if(nowran<minran) { minran = nowran; minTree = temp; } nowTree = nowTree.father; } else { Tree temp = find(nowTree.father.left,testData); nowran = range(temp.mData,testData); if(nowran<minran) { minran = nowran; minTree = temp; } nowTree = nowTree.father; }; } else{ nowTree = nowTree.father; } } } return minTree.mData; }