为什么 Java Collections API 没有 Tree 实现 [已关闭]

data-structures collections java

2022-09-01 23:19:29

只是出于好奇，我最近不得不在我的一个程序中使用一棵树，我不得不自己构建一个二叉树，但是为什么集合API没有树（甚至是二叉树）的默认实现？

我认为他们应该有一些强有力的理由来决定不将其包含在集合API中。

答案 1

我认为他们应该有一些强有力的理由来决定不将其包含在集合API中。

我认为原因是没有人为树提出一个好的API，这两者兼而有之。

通用性足以涵盖广泛的用例，以及
足够有用，可以补偿一般性能开销。

（你在哪里停下来？树？二叉树？N-ary树？达格？图形？）

值得注意的是，Apache Commons Collections和Google Collections（又名Guava）都没有树API。但是，在这个话题上有一个活跃的番石榴问题 - http://code.google.com/p/guava-libraries/issues/detail?id=174 - 所以很明显至少有些人同意你的观点。

更新

从15.0版本开始，番石榴现在以和类的形式提供了树支持。但这可能不是你所期望的。实际上，这些类实际上并不实现树数据结构。相反，您必须在泛型类型参数中执行此操作。此外，这些类甚至避免对节点类型的 API 进行假设。它们通过抽象类来实现这一点，并要求具体的遍历器子类型来实现查询树的操作;例如，获取节点的子节点。TreeTraverserBinaryTreeTraverserTraverser

FWIW，而不是“树 API”。它们是和 API 的基于树的实现。树性被公共API完全隐藏，使得这两个类完全不适合用作通用树。TreeMapTreeSetMapSet

答案 2

恕我直言，从理论上讲，Tree不是一种集合，它只是一种实现类型。我的意思是有抽象的集合，如Set（无序的条目集），List（有序的条目集），Map（两组条目之间有关系），并且有它们的实现：数组，列表（例如ArrayList和LinkedList），HashSet等，它们都有自己的优点和缺点。因此，Tree只是实现之一（例如，对于列表），它可以让你（大致）比数组更快地搜索，但不能按索引访问。

顺便说一句，Java中有TreeMap（“基于红黑树的NavigableMap实现”）和TreeSet（“基于TreeMap的NavigableSet实现” ）类。