在k-d树中进行数据的查找也是特征匹配的重要环节，其目的是检索在k-d树中与查询点距离最近的数据点。这里先以一个简单的实例来描述最邻近查找的基本思路。
星号表示要查询的点（2.1,3.1）。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点（2,3）。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行'回溯'操作：算法沿搜索路径反向查找是否有距离查询点更近的数据点。此例中先从（7,2）点开始进行二叉查找，然后到达（5,4），最后到达（2,3），此时搜索路径中的节点为<（7,2），（5,4），（2,3）>，首先以（2,3）作为当前最近邻点，计算其到查询点（2.1,3.1）的距离为0.1414，然后回溯到其父节点（5,4），并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以（2.1,3.1）为圆心，以0.1414为半径画圆，如图4所示。发现该圆并不和超平面y = 4交割，因此不用进入（5,4）节点右子空间中去搜索。
再回溯到（7,2），以（2.1,3.1）为圆心，以0.1414为半径的圆更不会与x = 7超平面交割，因此不用进入（7,2）右子空间进行查找。至此，搜索路径中的节点已经全部回溯完，结束整个搜索，返回最近邻点（2,3），最近距离为0.1414。
一个复杂点了例子如查找点为（2，4.5）。同样先进行二叉查找，先从（7,2）查找到（5,4）节点，在进行查找时是由y = 4为分割超平面的，由于查找点为y值为4.5，因此进入右子空间查找到（4,7），形成搜索路径<（7,2），（5,4），（4,7）>，取（4,7）为当前最近邻点，计算其与目标查找点的距离为3.202。然后回溯到（5,4），计算其与查找点之间的距离为3.041。以（2，4.5）为圆心，以3.041为半径作圆，如图5所示。可见该圆和y = 4超平面交割，所以需要进入（5,4）左子空间进行查找。此时需将（2,3）节点加入搜索路径中得<（7,2），（2,3）>。回溯至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以最近邻点更新为（2，3），最近距离更新为1.5。回溯至（7,2），以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割，如图6所示。至此，搜索路径回溯完。返回最近邻点（2,3），最近距离1.5。k-d树查询算法的伪代码如下所示。 从root节点开始，DFS搜索直到叶子节点，同时在stack中顺序存储已经访问的节点。 如果搜索到叶子节点，当前的叶子节点被设为最近邻节点。 然后通过stack回溯:
如果当前点的距离比最近邻点距离近，更新最近邻节点.
然后检查以最近距离为半径的圆是否和父节点的超平面相交.
如果相交，则必须到父节点的另外一侧，用同样的DFS搜索法，开始检查最近邻节点。
如果不相交，则继续往上回溯，而父节点的另一侧子节点都被淘汰，不再考虑的范围中. 当搜索回到root节点时，搜索完成，得到最近邻节点。
首先看下二叉排序树的定义：
二叉排序树（Binary Sort Tree）又称二叉查找树，亦称二叉搜索树。 它或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；
由定义可知，采用中序遍历的输出序列，就是“一个由小到大的结点值递增序列”
代码参考如下：
#include?<stdio.h>#include?<malloc.h>
typedef?int?KeyType;
typedef?struct?node?//记录类型
{
KeyType?key;//关键字项 struct?node?*lchild,*rchild;?//左右孩子指针}?BSTNode;
int?InsertBST(BSTNode?*&p,KeyType?k)?
{
if?(p==NULL)?//原树为空,?新插入的记录为根结点
{ p=(BSTNode?*)malloc(sizeof(BSTNode)); p->key=k; p->lchild=p->rchild=NULL; return?1; } else?if?(k==p->key)?//树中存在相同关键字的结点,返回0 return?0; else?if?(k<p->key)? return?InsertBST(p->lchild,k);?//插入到*p的左子树中 else? return?InsertBST(p->rchild,k);?//插入到*p的右子树中}
BSTNode?*CreateBST(KeyType?A[],int?n)?//返回BST树根结点指针
{
BSTNode?*bt=NULL;//初始时bt为空树 int?i=0; while?(i<n)? { InsertBST(bt,A[i]);?//将关键字A[i]插入二叉排序树T中 i++;}
return?bt;?//返回建立的二叉排序树的根指针
}
void?mid_order(BSTNode?*T)//中序遍历二叉树
{
if(T)
{
mid_order(T->lchild);
printf("?%d?",T->key);
mid_order(T->rchild);
}
}
void?main()
{
BSTNode?*bt,*p,*f; int?n=9; KeyType?a[]={1,12,5,8,3,10,7,13,9}; bt=CreateBST(a,n); printf("BST:");mid_order(bt);printf("\n");}
