1

Haskell 库中是否存在这种数据结构？我做了一些搜索，但找不到任何有用的东西。我想使用现有类型而不是定义我自己的类型——它似乎应该存在。

data MyTree e n = Node { rootLabel :: n
                       , subForest :: Map e (MyTree e n)
                       }

这个想法是它与 Data.Tree 非常相似，但边可以像节点一样保存信息。

如果你有一条穿过树的路径（[e] 类型），你可以在 O(log(n)) 中找到 rootLabel（n 类型）。据我所知，您不能使用 Data.Tree 执行此操作，因为您必须扫描每个节点的子节点以查找它是否是路径前进到的节点。这是因为 Data.Tree 的 subForest 的类型是 [Tree a]。

特别是，我对公开具有类似于以下类型的函数的实现感兴趣：

getNextLevel :: e -> MyTree e n -> MyTree e n

这将在树中更深一层，给定一个遍历的边缘。

4

2 回答 2

4

这种数据类型看起来很像一个 trie，在 Hackage 上有很多可用的包。

于 2012-04-07T23:53:28.870 回答
-1

您始终可以使用图形库，并确保自己将其保留为树。

于 2012-04-07T23:09:39.627 回答