使用二叉搜索樹實現一組點

我的任務使用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

使用二叉搜索樹實現一組點

回答

相關問題