knn之构造kd树和最近邻求取c++实现_数据结构kd树最近邻c++

这份代码测试样例为 

6
7 2
2 3
5 4
4 7
9 6
8 1
 
 
8 2

这样，通过中位数来选取根节点(这样的方法其实在一定程度上是有很大问题的，因为根节点的选取方法不同，会导致整棵树的结构不同，这里由于数据的关系，不能构成完全二叉树，所以在对于特殊的样例来说是会出错的，比如说(10,10)这个测试样例，根本无法找到包含他的子节点（区域），所以会导致出错))。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
struct node{
    pair<int,int>x;
	int dim;
	node*left;
	node*right;
	node*father;
	node(pair<int,int>p=make_pair(0,0),int dim=0,node*left=0,node*right=0,node*father=0)
	:dim(dim),left(left),right(right),father(father)
	{
	 x=p;	
	}
};
bool cmp1(node*a,node* b)
{
	return a->x.first<b->x.first;
}
bool cmp2(node*a,node*b)
{
	return a->x.second<b->x.second;
}
vector<node*>vec;
node* buildtree(vector<node*>temp,int cnt)
{ 
 
if(temp.size()==0)
return 0;
else if(temp.size()==1)
return temp[0];
else{
 
    if(cnt==1)
 	sort(temp.begin(),temp.end(),cmp1);
 	else
 	sort(temp.begin(),temp.end(),cmp2);
 	
 	int mid=temp.size()/2;
    vector<node*>p;
    for(int i=0;i<mid;i++)
    {
    	p.push_back(temp[i]);
    }
    vector<node*>q;
    for(int i=mid+1;i<temp.size();i++)
    {
    	q.push_back(temp[i]);
    }
    node*left=buildtree(p,(cnt+1)%2);
    node*right=buildtree(q,(cnt+1)%2);
    node*fat=new node(make_pair(temp[mid]->x.first,temp[mid]->x.second),cnt,left,right,0);
    if(left!=0)
	left->father=fat;
	if(right!=0)
    right->father=fat;
    //cout<<fat->x.first<<" "<<fat->x.second<<endl;
    return fat;
}
}
void traverse(node*root) 
{
	if(root==0)
	{
	}
	else
	{
		cout<<root->x.first<<" "<<root->x.second<<endl;
		traverse(root->left);
		traverse(root->right);
	}
}
node*find_first_belong(node*key,node*root)
{
	node*temp=root; 
	while(true) //遍历找到其归属的叶节点 
	{
		if(temp->left==0&&temp->right==0)
		{
			
			break;
		}
		else
		{
			int dim=temp->dim;//选择维度比较 
			if(dim==1)//选择x1比较 
			{
				if(key->x.first<=temp->x.first)
				temp=temp->left;
				else
				temp=temp->right;
			}
			else //选择x2比较 
			{
				if(key->x.second<=temp->x.second)
				 temp=temp->left;
				 else
				 temp=temp->right;
			}
		}
	}
	return temp;
}
double distance(node*a,node*b)
{
	double ax1=a->x.first;
	double ax2=a->x.second;
	double bx1=b->x.first;
	double bx2=b->x.second;
	return sqrt(pow(ax1-bx1,2)+pow(ax2-bx2,2));
	
}
node*query(node*key,node*root,double mindis)
//这里就是最不明白的一点，当另一区域跟圆相交，书上说是递归进行最近邻搜索，
//没搞懂到底怎么递归搜索，所以这里就直接用了很简单的遍历比较，希望以后能搞懂 
{
	node*rec=root;
	double mind=mindis;
	queue<node*>q;
	q.push(root);
	while(!q.empty())
	{
		node*temp=q.front();
		double dis=distance(key,temp);
		if(dis<mind)
		{
			mind=dis;
			rec=temp;
		}
		q.pop();
		if(temp->left!=0)
		q.push(temp->left);
		if(temp->right)
		q.push(temp->right);
		
	}
	return rec;
}
node*find_nearest(node*key,node*belong)
{
	node *nearest=belong;
 	double mindis=distance(key,belong);
 	//cout<<mindis<<" mindis"<<endl;
 	while(true)
 	{
 	//cout<<belong->x.first<<" "<<belong->x.second<<endl;
 	node*fat=belong->father;
 	if(fat==0)
 	break;
 	int fdim=fat->dim;
 	if(distance(fat,key)<mindis)
 	{
 		mindis=distance(fat,key);
 		nearest=fat;
 	}
 	if(fdim==1) //判断圆是否与x1=fat->x.first相交 
 	{
 		int fx1=fat->x.first;
 		int kx1=key->x.first;
 		if(abs(fx1-kx1)<mindis)
 		{
 			node*res=query(key,fat->right,mindis);
 			if(res!=0&&distance(res,key)<mindis)
 			{
 				nearest=res;
 				mindis=distance(res,key);
 			}
 			
 		}
 	}
 	else //反之 
 	{
 		 int fx2=fat->x.second;
 		 int kx2=key->x.second;
 		 if(abs(fx2-kx2)<mindis)
 		 {
 		 	node*res=query(key,fat->right,mindis);
 			if(res!=0&&distance(res,key)<mindis)
 			{
 				nearest=res;
 				mindis=distance(res,key);
 				
 			}
 		 }
 	}
 	belong=fat;
 	if(belong==0)
 	break;
  }
  return nearest;
}
node*search(node*key,node*root)
{
	node* belong=find_first_belong(key,root);
	//cout<<belong->x.first<<" "<<belong->x.second<<endl;
	node* nearest=find_nearest(key,belong);
}
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		node* temp=new node(make_pair(x,y));
		vec.push_back(temp);
	}
	node*root=buildtree(vec,1);
	//traverse(root);
	int x,y;
	cin>>x>>y;
	node *key=new node(make_pair(x,y));
    node*near=search(key,root);
	cout<<near->x.first<<" "<<near->x.second<<endl;
	
} 

以上代码，经过测试，除了(10,10)这种类似的特殊数据会出错，别的基本正确，代码写的很乱。。。。

这里还有一个很大的问题在于，我不知道一旦判定了圆和其他区域相交之后该怎么进行递归搜索，所以这里直接用了遍历。。。。

总算搞懂了什么递归搜索：

下面的是第二个版本：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
struct node{
    pair<int,int>x;
	int dim;
	node*left;
	node*right;
	node*father;
	node(pair<int,int>p=make_pair(0,0),int dim=0,node*left=0,node*right=0,node*father=0)
	:dim(dim),left(left),right(right),father(father)
	{
	 x=p;	
	}
};
bool cmp1(node*a,node* b)
{
	return a->x.first<b->x.first;
}
bool cmp2(node*a,node*b)
{
	return a->x.second<b->x.second;
}
vector<node*>vec;
node* buildtree(vector<node*>temp,int cnt)
{ 
 
if(temp.size()==0)
return 0;
else if(temp.size()==1)
return temp[0];
else{
 
    if(cnt==1)
 	sort(temp.begin(),temp.end(),cmp1);
 	else
 	sort(temp.begin(),temp.end(),cmp2);
 	
 	int mid=temp.size()/2;
    vector<node*>p;
    for(int i=0;i<mid;i++)
    {
    	p.push_back(temp[i]);
    }
    vector<node*>q;
    for(int i=mid+1;i<temp.size();i++)
    {
    	q.push_back(temp[i]);
    }
    node*left=buildtree(p,(cnt+1)%2);
    node*right=buildtree(q,(cnt+1)%2);
    node*fat=new node(make_pair(temp[mid]->x.first,temp[mid]->x.second),cnt,left,right,0);
    if(left!=0)
	left->father=fat;
	if(right!=0)
    right->father=fat;
    //cout<<fat->x.first<<" "<<fat->x.second<<endl;
    return fat;
}
}
void traverse(node*root) 
{
	if(root==0)
	{
	}
	else
	{
		cout<<root->x.first<<" "<<root->x.second<<endl;
		traverse(root->left);
		traverse(root->right);
	}
}
node*find_first_belong(node*key,node*root)
{
	node*temp=root; 
	while(true) //遍历找到其归属的叶节点 
	{
		if(temp->left==0&&temp->right==0)
		{
			
			break;
		}
		else
		{
			int dim=temp->dim;//选择维度比较 
			if(dim==1)//选择x1比较 
			{
				if(key->x.first<=temp->x.first)
				temp=temp->left;
				else
				temp=temp->right;
			}
			else //选择x2比较 
			{
				if(key->x.second<=temp->x.second)
				 temp=temp->left;
				 else
				 temp=temp->right;
			}
		}
	}
	return temp;
}
double distance(node*a,node*b)
{
	double ax1=a->x.first;
	double ax2=a->x.second;
	double bx1=b->x.first;
	double bx2=b->x.second;
	return sqrt(pow(ax1-bx1,2)+pow(ax2-bx2,2));
	
}
node*query(node*key,node*root,double mindis)//没有用的函数
 
{
	node*rec=root;
	double mind=mindis;
	queue<node*>q;
	q.push(root);
	while(!q.empty())
	{
		node*temp=q.front();
		double dis=distance(key,temp);
		if(dis<mind)
		{
			mind=dis;
			rec=temp;
		}
		q.pop();
		if(temp->left!=0)
		q.push(temp->left);
		if(temp->right)
		q.push(temp->right);
		
	}
	return rec;
}
node*find_nearest(node*key,node*belong,node*root)
{
	node *nearest=belong;
 	double mindis=distance(key,belong);
 	//cout<<belong->x.first<<" belong "<<belong->x.second<<endl;
 	//cout<<mindis<<" mindis"<<endl;
 	while(true)
 	{
 	//cout<<belong->x.first<<" "<<belong->x.second<<endl;
 	node*fat=belong->father;
 	if(fat==0||fat==root->father)
 	break;
 	node*other=new node(); //相比第一个这里还更加对了，因为这里还考虑到了万一归属的叶节点不是左节点的情况
 	if(fat->left==belong)
 	{
 		other=fat->right;
 		
 	}
 	else
 	other=fat->left;
 	
 	//cout<<fat->x.first<<" "<<" fat  "<<fat->x.second<<endl;
 	int fdim=fat->dim;
 	if(distance(fat,key)<mindis)
 	{
 		mindis=distance(fat,key);
 		nearest=fat;
 	}
 	if(fdim==1) //判断圆是否与x1=fat->x.first相交 
 	{
 		int fx1=fat->x.first;
 		int kx1=key->x.first;
 		if(abs(fx1-kx1)<mindis)
 		{
 			node*tm=find_first_belong(key,other);
 			node*res=find_nearest(key,tm,other); //传说中的递归搜索在这里，利用他之前的函数
 			if(res!=0&&distance(res,key)<mindis)
 			{
 				nearest=res;
 				mindis=distance(res,key);
 			}
 			
 		}
 		//cout<<fx1<<" xxxx   "<<kx1<<" "<<mindis<<endl;
 	}
 	else //反之 
 	{
 		 int fx2=fat->x.second;
 		 int kx2=key->x.second;
 		 if(abs(fx2-kx2)<mindis)
 		 {
 		 	node*tm=find_first_belong(key,other);
 		 	//cout<<tm->x.first<<" **** "<<tm->x.second<<endl;
 		 	//cout<<other->x.first<<" other "<<other->x.second<<endl;
 			node*res=find_nearest(key,tm,other);
 			if(res!=0&&distance(res,key)<mindis)
 			{
 				nearest=res;
 				mindis=distance(res,key);
 				//cout<<mindis<<"  mindis"<<endl;
 			}
 		 }
 	}
 	belong=fat;
 	if(belong==0)
 	break;
  }
  return nearest;
}
node*search(node*key,node*root)
{
	node* belong=find_first_belong(key,root);
	//cout<<belong->x.first<<" "<<belong->x.second<<endl;
	node* nearest=find_nearest(key,belong,root);
	return nearest;
}
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		node* temp=new node(make_pair(x,y));
		vec.push_back(temp);
	}
	node*root=buildtree(vec,1);
	//traverse(root);
	int x,y;
	cin>>x>>y;
	node *key=new node(make_pair(x,y));
    node*near=search(key,root);
	cout<<"the nearest point is "<<near->x.first<<" "<<near->x.second<<endl;
	
} 

然而还是没有解决(10,10)的情况，明天再说！！！！