使用二叉搜索树实现一组点

我的任务使用java.util.TreeSet使用二叉查找树实现点集API类。所述点集API概况如下所示：使用二叉搜索树实现一组点

public class PointSET { 
    public PointSET() {}        // construct an empty set of points 
    public boolean isEmpty() {}      // is the set empty? 
    public int size() {}        // number of points in the set 
    public void insert(Point2D p) {}     // add the point p to the set (if it is not already in the set) 
    public boolean contains(Point2D p) {}    // does the set contain the point p? 
    public Collection<Point2D> range(RectHV rect) {} // all points in the set that are inside the rectangle 
    public Point2D nearest(Point2D p) {}    // a nearest neighbor in the set to p; null if set is empty 
}

的Point2对象是一个简单的点，其中x和y坐标以及一些其他方法的两个点之间的计算距离。
RectHV对象表示在矩形内的点的范围搜索中使用的矩形。

我想我不确定如何在BST中实现这个API类。我们已经在课堂上了解了BST的知识，但只是从广义上讲;它们是什么以及后序/前序/中序的搜索方式。

我也很困惑API是什么和它本身。是什么让这个API成为一种API而不是而不是？

“实施”API涉及什么？以及如何使用java.util.TreeSet来做到这一点？

我将不胜感激任何帮助。

来源

2014-02-23 Kestrel

您将使用BST作为数据结构来存储所有点，而不是将它们存储在另一个结构中，例如数组 – AlexBrand

'TreeSet' *是一个二叉查找树;在内部它被实现为红黑树。所以'TreeSet'如何与实现自己的BST连接并不是很清楚，但有关如何使用'TreeSet'的详细信息，请参阅[它的文档]（http://docs.oracle.com/javase/7/docs/ API/JAVA/util的/ TreeSet.html）。 –

您可以将应用程序编程接口（API）视为合同。它指定对象与对方交互的方式。

为了说明一个API是什么，考虑接口Dictionary：

public interface Dictionary { 
    List<String> loadWords(); 
}

接口Dictionary建立合同（API），所有字典的实现必须遵循。字典实现的两个示例可以是：

public class TextFileDictionary implements Dictionary { 
    public List<String> loadWords() { 
     // load words from a text file and return them 
     return words; 
    } 
} 

public class DatabaseDictionary implements Dictionary { 
    public List<String> loadWords() { 
     // load words from database and return them 
     return words; 
    } 
}

现在我们以您的PointSET类为例。正如你所看到的，它有一大堆方法来定义PointSET类型的对象的行为。

public class PointSET { 

    // private ... <- your data structure goes here. 

    public PointSET() {} 
    public boolean isEmpty() {} 
    public int size() {} 
    public void insert(Point2D p) {} 
    public boolean contains(Point2D p) {} 
    public Collection<Point2D> range(RectHV rect) {} 
    public Point2D nearest(Point2D p) {} 
}

正如@alexBrand指出的，一个好的起点是定义您的数据结构。在你的情况下，明显的选择是BST。然后，为了与提供的API保持一致，您将不得不操纵您的数据结构来实现PointSET的预期行为。

来源

2014-02-23 00:51:31 Trein

使用二叉搜索树实现一组点

回答

相关问题