为什么Java Collections API没有Tree实现

Question

出于好奇,我最近不得不为我的一个程序使用树,我不得不自己构建一个二叉树,但为什么Collections API没有树的默认实现(甚至是二叉树)？

我认为应该有一些强有力的理由为什么他们决定不将它包含在集合API中.

Answer 1

我认为应该有一些强有力的理由为什么他们决定不将它包含在集合API中.

我认为原因是没有人为树木提供良好的API

• 一般用途足以涵盖广泛的用例,和
• 足够有用,以弥补一般的性能开销.

(你在哪里停下来？树？二叉树？N-ary树？DAG？图？)

值得注意的是,Apache Commons Collections或Google Collections(aka Guava)都没有树API.但是,关于这个主题存在一个活跃的Guava问题 - http://code.google.com/p/guava-libraries/issues/detail?id=174 - 所以至少有些人同意你的观点.

UPDATE

从版本15.0开始,Guava现在以类TreeTraverser和BinaryTreeTraverser类的形式提供树支持.但这可能不是你所期望的.实际上,这些类实际上并不实现树数据结构.相反,您必须在泛型类型参数中执行此操作.除此之外,这些Traverser类甚至避免对节点类型的API做出假设.他们通过作为抽象类来实现这一点,并要求具体的遍历器子类型来实现询问树的操作; 例如,获取节点的孩子.

FWIW,TreeMap而TreeSet不是"树API".他们是基于树的实现Map和SetAPI的.树状结构完全被公共API隐藏,使得这两个类完全不适合用作通用树.

Answer 2

恕我直言,理论上,Tree不是一种集合,它只是一种实现.我的意思是有抽象集合,如Set(无序条目集),List(有序条目集),Map(两组条目之间有关系),还有它们的实现:array,list(例如ArrayList和LinkedList) ),HashSet等,它们都有各自的优缺点.因此,Tree只是一种实现(例如,用于列表),它可以(大致)提供比数组更快的搜索但不能通过索引访问.

顺便说一句,在Java中有TreeMap("基于红黑树的NavigableMap实现")和TreeSet("基于TreeMap的NavigableSet实现")类.

Answer 3

java.util.TreeMap是红黑树的实现。