Java：我应该在实现各种树结构时使用泛型吗？

我刚刚通过了this article，提出了各种泛型技术。Java：我应该在实现各种树结构时使用泛型吗？

作者决定使用下列内容：

public class BinarySearchTree<T extends Comparable<? super T>> {

而且我不明白这一点。为什么作者决定使用private Entry<T> root;

而不只是private Comparable root？

通用树节点带来的特殊优势是否实现了Comparable接口？我是否需要比在二进制搜索树，AVL树，Splay树，红黑树等结构中比较2个元素更多？

来源

2010-10-22 Xorty

你需要了解儿童和树的结构。可比只是给你compareTo。在比较之后，条目至少会给你左右两边的孩子，你会知道如何操纵结构来保持树的一致性。

来源

2010-10-22 19:09:40

@SB您对Comparable进行了部分回答，现在对泛型有何看法？看到我对Kel的文章的评论;） – Xorty 2010-10-22 19:34:30

您不必使用泛型，但它是维护树中类型安全性和对象一致性的好方法。您始终可以使用返回Object的标准Node类，但如果您希望Tree可以跨不同对象重用，则泛型非常棒。有一个原因是Collections API在推出时转用了泛型 - 它们增加了安全性，并帮助开发人员更多地了解他们可以做什么以及不能做什么。 – 2010-10-22 19:37:42

那么我没有考虑使用Object作为节点的数据持有者:)我想使用Comparable来代替:)所以node有：data（Comparable），leftson（Node），rightson（Node） – Xorty 2010-10-22 19:39:19

他决定去Entry<Comparable>，因为Entry是代表树中节点的附加类。最有可能进入的定义类似于

class Entry<T extends Comparable<? super T>> { T value; Entry<T> leftAncestor; Entry<T> rightAncestor; }

然后二叉树结构有树的根，并使用它所需的方法。

来源

2010-10-22 19:09:18 vstoyanov

那么主要思想是允许我插入Comparable实现，但不能将苹果与梨混合？（Apple：Comparable，Pear：Comparable） – Xorty 2010-10-22 19:54:40

这是此示例中泛型背后的主要思想。使用'Entry'而不是'Comparable'后面的想法是因为当你有'class' /'struct'时，这就是基于节点的数据结构的实现。 – vstoyanov 2010-10-22 20:00:06

据我所知，这个例子展示了二叉搜索树的实现细节。树条目不仅必须是Comparable，还必须包含有关左右子实体和（如有必要）父元素的信息。

来源

2010-10-22 19:10:04 Kel

好吧，为什么他不扩展Comparable接口与另一个 - 节点接口？它也可以存储左/右儿子。你能想到泛型使用的任何特定原因吗？ – Xorty 2010-10-22 19:13:18

我觉得，Comparable界面也适合这里。泛型被用来存储任意数据。 – Kel 2010-10-22 19:17:31

但是，除非您创建非常自定义的树实现，否则不会使用任何通用的有限数据的方法，是吗？ – Xorty 2010-10-22 19:22:00

Java：我应该在实现各种树结构时使用泛型吗？

回答

相关问题