我想在 Scala 中实现一棵树。我的特定树使用 Swing Split Pane 来提供地理 map 的多个 View 。拆分 Pane 中的任何 Pane 本身都可以进一步划分以提供额外的 View 。 我说 TreeMap 和 TreeSet 都没有提供树功能是否正确? 如果我误解了这一点,请原谅。我觉得应该有标准的 Tree 集合,而不断重新发明轮子是不好的做法。 是否有任何 Tree 实现可能成为 future 的 Scala 标准?
所有的树都有三种类型的元素:根、节点和叶。叶子和节点必须有一个对父节点的引用。 Root 和 Nodes 可以有多个对子节点和叶子的引用。叶子有零个 child 。节点和根节点不能在不删除其子节点的情况下删除。我可能错过了其他规则/约束。
这似乎足以证明标准集合的合理性。我还建议,对于 Root 和 Nodes 只能有 2 个 child 或单个叶子 child 的情况,应该有一个标准的子类集合。在我的特定情况下,这就是我想要的。
最佳答案
实际上,一棵树本身既无用又很难指定。
从后者开始,严格来说数据结构,一棵树可以有多少个 child ?节点是否存储值?节点是否存储元数据? child 有指向 parent 的指针吗?您是将树存储为带有指针的节点,还是存储为数组上的位置元素?
这些问题的答案都是“视情况而定”。事实上,你说过 child 有指向他们 parent 的指针,但对于任何不可变的树来说都不是这样!您似乎还假设树始终存储为带有引用的节点对象,而某些树实际上存储为单个数组上的节点(例如 Heap )。
此外,并非所有这些要求都可以满足——有些是相互排斥的。即使你忽略了这些,你仍然会得到一个没有针对任何东西进行优化并且使用起来很笨拙的数据结构,因为你必须处理许多与你无关的细节。
然后,还有第二个问题,那就是树本身是无用的。 TreeSet
和 TreeMap
利用特定树的插入/删除/查找算法使其成为排序数据的良好数据结构。然而,这根本不是树木的唯一用途。树可用于搜索空间算法、表示类似树的现实世界信息、组成文件系统等。有时任务是在图中找到一棵树。这些用途中的每一种都需要不同的表示和不同的算法——正是算法使它们变得有用。
而且,最重要的是,编写一个树类是微不足道的。问题是编写算法来操作它。
关于scala - Scala 中的树集合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12018011/