KD-Tree点重复出现，并给了我错误的输出

Question

我（尝试）在Processing / Java中实现KD-Tree，并遵循了我在数十篇文章和Wikipedia文章中所看到的逻辑，但是由于输出看起来像这样，我必须做错了什么：

代替此：

由于节点在重复，并且看起来根本不像维基百科树，因此显然已关闭。

这是我的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树类，节点类和点类：

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

除了提供一些可能会出现问题的提示以外，我还建议您自己解决此问题的一些步骤：