public class KDTreeNode
  {
    /// <summary>
    /// 分裂點
    /// </summary>
    public Point DivisionPoint { get; set; }

    /// <summary>
    /// 分裂類型
    /// </summary>
    public EnumDivisionType DivisionType { get; set; }

    /// <summary>
    /// 左子節(jié)點
    /// </summary>
    public KDTreeNode LeftChild { get; set; }

    /// <summary>
    /// 右子節(jié)點
    /// </summary>
    public KDTreeNode RightChild { get; set; }
  }

private KDTreeNode CreateTreeNode(List<Point> pointList)
{
  if (pointList.Count > 0)
  {
    // 計算方差
    double xObtainVariance = ObtainVariance(CreateXList(pointList));
    double yObtainVariance = ObtainVariance(CreateYList(pointList));

    // 根據(jù)方差確定分裂維度
    EnumDivisionType divisionType = SortListByXOrYVariances(xObtainVariance,    yObtainVariance, ref pointList);

    // 獲得中位數(shù)
    Point medianPoint = ObtainMedian(pointList);
    int medianIndex = pointList.Count / 2;

    // 構(gòu)建節(jié)點
    KDTreeNode treeNode = new KDTreeNode()
    {
      DivisionPoint = medianPoint,
      DivisionType = divisionType,
      LeftChild = CreateTreeNode(pointList.Take(medianIndex).ToList()),
      RightChild = CreateTreeNode(pointList.Skip(medianIndex + 1).ToList())
    };
    return treeNode;
  }
  else
  {
    return null;
  }
}

public Point FindNearest(Point searchPoint)
{
  // 按照查找方式尋找最近點
  Point nearestPoint = DFSSearch(this.rootNode, searchPoint);
  
  // 進(jìn)行回溯
  return BacktrcakSearch(searchPoint, nearestPoint);
}


private Point DFSSearch(KDTreeNode node,Point searchPoint,bool pushStack = true)
{
  if(pushStack == true)
  {
    // 利用堆棧記錄查詢的路徑，由于樹節(jié)點中沒有記載父節(jié)點的原因
    backtrackStack.Push(node);
  }
  if (node.DivisionType == EnumDivisionType.X)
  {
    return DFSXsearch(node,searchPoint);
  }
  else
  {
    return DFSYsearch(node, searchPoint);
  }
}

private Point BacktrcakSearch(Point searchPoint,Point nearestPoint)
{
  // 如果記錄路徑的堆棧為空則表示已經(jīng)回溯到根節(jié)點，則查到的最近點就是真正的最近點
  if (backtrackStack.IsEmpty())
  {
    return nearestPoint;
  }
  else
  {
    KDTreeNode trackNode = backtrackStack.Pop();
    
    // 分別求回溯點與最近點距查找點的距離
    double backtrackDistance = ObtainDistanFromTwoPoint(searchPoint,     trackNode.DivisionPoint);
    double nearestPointDistance = ObtainDistanFromTwoPoint(searchPoint, nearestPoint);
    
    if (backtrackDistance < nearestPointDistance)
    {
      // 深拷貝節(jié)點的目的是為了避免損壞樹
      KDTreeNode searchNode = new KDTreeNode()
      {
        DivisionPoint = trackNode.DivisionPoint,
        DivisionType = trackNode.DivisionType,
        LeftChild = trackNode.LeftChild,
        RightChild = trackNode.RightChild
      };
      nearestPoint = DFSBackTrackingSearch(searchNode, searchPoint);
   }
   // 遞歸到根節(jié)點
   return BacktrcakSearch(searchPoint, nearestPoint);
  }
}