为什么Java Collection Framework不包含Tree和Graph

Question

我熟悉Java Collection Framework，它包含基本接口：Collection和Map。我想知道为什么框架不包含树和图等基本集合的结构。两者都可以被视为Collection的子类型。

顺便说一句，我知道TreeSet是由红黑树底层实现的。然而，TreeSet 不是一个 Tree，而是一个 Set，因此框架中没有真正的 Tree。

Answer 1

我想知道为什么框架不包含树和图等基本集合的结构。两者都可以被视为Collection的子类型。

这是一个很好的问题。我认为这只是归结为范围界定。 Collections API 提供的类的核心功能包括：

• 迭代顺序：列表和排序映射具有指定的迭代顺序，大多数集合没有。

• 重复：列表允许重复，集合不允许

• 索引 ：列表值由整数索引，地图值由其他对象索引。

这让我们走得很远，我认为 Joshua Bloch 等人认为可以在这三个之上实现更多功能丰富的集合（需要元素之间内部关系的图和树、具有多重性的集合、双向映射……）核心功能，因此在图书馆中效果更好。

Answer 2

java.util 包包含用于组织任何类型数据的数据结构。它基本上处理通过其方法和定义的抽象数据结构（如List、Set、Map）行为（例如，Set 两次不包含任何元素，List 保持顺序并允许重复，等等）。

作为开发人员，您可以自由选择最适合您处理的数据类型的这些数据结构的实现（HashSet 与 TreeSet / LinkedList 与 ArrayList / 等）。例如，对于集合和映射，您可以在基于散列的实现和基于树的实现之间进行选择，这可能适合也可能不适合您想要做的事情（在大多数情况下，基于散列的实现将是最佳选择，而有时，当顺序很重要时，树可能更适合您的需求 - 另请参阅 HashSet 与 TreeSet（此处位于 Stackoverflow） ）。

如果您将树视为一种特殊的图（事实确实如此），那么您对适用于图的特定属性感兴趣，而不是一般的集合（本质上是列表，并且依次使用来实现诸如图表之类的东西）。

正如本线程中提到的，如果您对图形建模感兴趣，那么图形库有很多选择。我个人可以推荐 JGraphT。

我不知道为什么 JDK 中没有图形库（而且我不知道这是否是一件好事？），但我猜 Sun 决定将其留给开发人员，因为大多数需要图形的应用程序也需要非常独特的实现。

Answer 3

我怀疑答案是它是两件事的组合：

• 通用树或图形界面将“功能匮乏”。
• 使用字段来表示子指针和（如果需要的话）父指针来实现树或图会更容易、更有效。

请注意，Apache commons 或 Google commons 都没有通用图或树支持。然而，我确实遇到了一些通用的树/图层次结构：

• JavaNet 上的 jsfcompounds 项目具有 "com.truchsess.util" 图和树框架。
• SourceForge 上的 OpenJGraph 项目（非活动）包含树库和图形库。

Answer 4

原始答案

图（更具体地说，树，如您所知，一种特殊情况，只有一个根，不能有循环并且所有节点都连接）的主要问题是，该假设的集合应该保存在另一个结构中：节点。很难制定标准这种处理方式，因为它需要双层“容器”。

如果有人碰巧使用过JTree的TreeModel，就会注意到几乎不可能避免这样一个事实：后面有TreeNode（内部） ？）并且您必须同时操作节点和树。

不管怎样，我同意这个结构是有用的，但是很难使其成为标准，只需注意，例如，Apache Commons Collections 和 Google Guava 这两个大的API 的集合扩展，也没有。

更新

根据概述API的：

主要设计目标是生成一个相当小的 API，
不仅在尺寸上，而且更重要的是在“概念重量”上。原来是
至关重要的是，新功能似乎与当前的 Java 并不陌生
程序员；它必须扩大现有设施，而不是
替换它们。同时，新的 API 必须强大
足以提供上述所有优点。

因此，虽然图表是正确的集合，但也许可以使按照标准，由于之前解释过需要双层容器，因此实施的规模和复杂性太大，无法满足此设计目标。

此外，Google Guava 添加了对图表的支持。 Apache 有一个用于图表的沙箱（正在开发中），但自 2011 年以来似乎处于休眠状态。

Answer 5

恐怕答案是：设计和维护通用的树结构和接口太麻烦了（参见

Answer 6

有一个树接口 - javax.swing.tree.TreeModel，它实际上适用于任意有向图（具有显着的“根”节点）。不过，它没有实现Collection 接口（因为 Swing 比集合框架要老一些，而且目前还不清楚这里是否真的适合作为一个集合）。
（TreeModel 的一个实现是 DefaultTreeModel，它使用从 TreeNode 对象构建的树，它本身就是一个可由用户实现的接口。）

另一种类型的树由 XML 给出-DOM框架。
一些特定的使用树（或主要是“树节点”）由 java.io.File、java.awt.Component（和子类）、编译器树 API（ com.sun.source.tree.*)、Doclet API (com.sun.javadoc.*)、反射 API (java.lang.Class），语言模型 API (javax.lang.**)。

如果你比较这些API，

问题是，对于树来说，没有明确的通用有用接口——这样的树应该能够做什么？
一棵树只是其他树（低一级的树）的集合，还是只是指向根节点的指针，其中每个节点本身包含更多节点？或者树是所有节点的集合？还是所有节点所有内容的集合？所有节点都必须有“内容”，还是只有叶节点？如果树是一些内容元素（而不是节点本身）的集合，那么迭代器应该如何表现？一棵树有多大？

这是对树节点（或者实际上它可以是通用有向图节点，如果不是父指针）接口的建议：

/**
 * A general interface for a tree node.
 * @param <N> the concrete node type.
 */
public interface Node<N extends Node<N>> {

   /**
    * equivalent to {@link #children children()}.{@link Collection#isEmpty isEmpty()}.
    * @returns true, if this is a leaf node, else false.
    */
   public boolean isLeaf();

   /**
    * returns a collection of all children of this node.
    * This collection can be changed, if this node is mutable.
    */
   public Collection<N> children();
   /**
    * returns the parent of this node.
    * @return null, if this is the root node, or the node does not know its parent, or has multiple parents.
    */
   public N parent();
}

/**
 * a tree node with content objects.
 * @param <N> the concrete node type
 * @param <C> the type of the content of this node.
 */
public interface ContentNode<C,N extends ContentNode<C,N>>
          extends Node<N>
{
   /**
    * returns the content of this node, if any.
    */
   public C content();
}

这对于所有类型的树（例如上面列出的树）来说是否足够？我不这么认为。