-1

我得到了一个 Dictionary 界面，如下所示：

public interface Dictionary<E extends Comparable<E>> extends Iterable<E> {

现在我被要求使用二叉搜索树来实现这个接口，但是我不知道如何开始，因为我对上面实现 Dictionary 接口的理论概念很困惑。

这是我的实现类：

// Red-black binary search tree
public class DictionaryImp implements Dictionary<DictionaryImp>, Comparable<DictionaryImp> {

那么，我该如何实现以下这些方法呢？DictionaryImp 类将携带哪些实例变量？

public boolean isEmpty();
public boolean contains(E item);
public boolean hasPredecessor(E item);
// etc.
4

2 回答 2

0

我不知道你对红黑树的实现，但基本上你提到的所有方法都会调用相应的红黑树方法。

isEmpty：检查树是否为空

contains(E item)：对树执行二分查找以查找元素。如果可以找到则返回 true

add(E item): if (!contains(item)) tree.add(item);

等等等等

于 2012-05-13T08:25:13.227 回答
0

您拥有的类声明没有多大意义。的类型参数Dictionary似乎是针对字典的元素类型的；这就是为什么他们要求元素与它们自身具有可比性。您的声明似乎说那DictionaryImp是一本字典，其元素也是DictionaryImp，这没有意义。您可能想要的是一个DictionaryImp通用的，其元素类型与自身相当，并使用相同的类型参数实现字典，如下所示：

public class DictionaryImp<E extends Comparable<E>> implements Dictionary<E>
于 2012-05-13T22:36:20.247 回答