java - KD-Tree 点重复并给我错误的输出

Question

我(尝试)在Processing/Java中实现KD树，并遵循我在数十篇文章和维基百科文章中看到的逻辑，但我一定做错了什么，因为输出如下所示:

而不是这个:

显然有些东西不对劲，因为节点是重复的，而且看起来根本不像维基百科树。

这是我的 buildKDTree 函数:

  public Node buildKDTree(List<Point> pointList, int depth){

    int size = pointList.size();
    int axis = depth % 2;
    Node newNode = new Node();

    if(pointList.size() == 1)
    {
      System.out.print("I am a leaf \n");
      System.out.print("Size of list:  " + pointList.size() + "\n");
      System.out.print("Point:  " + pointList.get(0) + "\n");
      newNode.point = pointList.get(0);
      newNode.left = null;
      newNode.right = null;
      System.out.print("Node Point:  " + newNode.point + "\n");
      return newNode;    
    }

    if(size <= 0)
    {
      return null;
    }
    if(axis == 0)
    {
      //sort by x
      System.out.print("Sorting by X \n");
      Comparator<Point> com = new xComp();
      Collections.sort(pointList, com);
    }
    else if(axis == 1)
    {
      System.out.print("Sorting by Y \n");
      Comparator<Point> com = new yComp();
      Collections.sort(pointList, com);
    }
    int median = size/2;
    //System.out.print("Median is: " + points.get(median) + " \n");
    List<Point> beforeMedian = pointList.subList(0, median);
    List<Point> afterMedian = pointList.subList(median, size);

    newNode.point = pointList.get(median);
    newNode.left = buildKDTree(beforeMedian, depth + 1);
    newNode.right = buildKDTree(afterMedian, depth + 1);
    return newNode;
  }

我的KD Tree类、Node类和Point类:

class KDTree{
  Node root;

  public KDTree()
  {
    root = null;
  }

}

class Node{
  Node left;
  Node right;
  Point point;

  Node(Point _p, Node l, Node r){
    point = _p;
    left = l;
    right = r;
  }

  Node(Node l, Node r){
    left = l;
    right = r;
  }

  Node(){
    left = null;
    right = null;
    point = null;
  }

  Node(Point _p)
  {
    point = _p;
    left = null;
    right = null;
  }

  void setPoint(Point _p)
  {
    point = _p;
  }
}

class Point {

   public PVector p;
   boolean isNearestNeighbor = false;
   boolean isSearchLocation = false;

   public Point( float x, float y ){
     p = new PVector(x,y);
     isNearestNeighbor = false;
     isSearchLocation = false;
   }

   public Point(PVector _p0 ){
     p = _p0;
   }
}

我如何打印树:

public void printLevelOrder(Node root)
 {
   if(root == null )
   {
     return;
   }
   Queue<Node> q =new LinkedList<Node>();
   q.add(root);
   while(true)
   {
     int nodeCount = q.size();
     if(nodeCount == 0)
     {
       break;
     }

     while(nodeCount > 0)
     {
       Node node = q.peek();
       System.out.print("("+node.point + ")");

       q.remove();

       if(node.left != null)
       {
         q.add(node.left);
       }

       if(node.right != null)
       {
         q.add(node.right);
       }

       if(nodeCount > 1)
       {
         System.out.print(", ");
       }
       nodeCount--;
     }
     System.out.println();
   }
 }

如有任何帮助，我们将不胜感激!我已经看了几个小时了，所以也许我错过了一些简单的东西。

Answer 1

我不想提供一些可能出现问题的提示，而是建议您自己解决此问题的一些步骤:

1. 将 buildKDTree 方法分解为几个较小的方法，执行更小的功能(例如构建叶子、排序子列表等)
2. 对每个单元进行单元测试，确保其完全符合您的预期
3. 使用简单案例转向更复杂的案例对整个功能进行单元测试
4. 如果这些单元测试中的任何一个以异常方式运行，请使用交互式调试器来找出发生了什么
5. 如果您无法理解为什么某些事物会以某种方式表现，请作为关于该案例的问题
6. 最后，一旦一切正常，就可以应用到实际案例

这可能需要更长的时间，但您会在此过程中学到更多东西。