haskell - 树遍历

问题描述

我需要在具有最大深度的树上实现 DFS 遍历（例如，如果深度为 0，那么您只显示根）。

后继节点将返回 (Int,Tree) 列表，其中 Tree 基本上是我的节点 sa 中的“s”

limitedDfsRec :: (ProblemState s a, Ord s, Ord a) => [Node s a] -> Int -> S.Set (Node s a)-> [Node s a] -> [Node s a]
limitedDfsRec [] _ _ result = reverse result
limitedDfsRec (node:coada) max_depth visited result | adancime node > max_depth = limitedDfsRec coada max_depth visited result
                                                    | S.member node visited = limitedDfsRec coada max_depth visited result
                                                    | otherwise =
                                                    let succesori = [(Nod copil (Just actiune_copil) (Just $ stare node) ((adancime node) + 1) []) | (actiune_copil,copil) <- successors (stare node)]
                                                    in limitedDfsRec (succesori ++ coada) max_depth (S.insert node visited) (node : result)

您从一个节点开始，如果它的深度大于允许您转到列表中的下一个元素（coada）的最大深度。如果该元素已被访问过，则转到列表中的下一个元素。否则，你得到所有的孩子（succesori）并将它们放在列表中（coada），你将元素添加到访问和最终结果中。该功能与此功能一起使用：

instance ProblemState Tree Int where
    successors (Tree n)
        | n == 2    = [(1, Tree 4), (2, Tree 6)]  -- 4 instead of 5 => cycle
        | otherwise = [(1, Tree $ 2 * n + 1), (2, Tree $ 2 * n + 2)]

    isGoal (Tree n) = n == 13

这会产生孩子。好吧，问题是上面的函数仍然访问节点，即使它们在访问集中，我不明白为什么。

因此，例如，从最大深度为 2 的树 0 开始，您应该得到 [0,1,3,4,2,6] 但我的函数得到 [0,1,3,4,2,4,6]因为当它到达 2 时，它会将 4 和 6 放入列表中，但是当它到达 4 时，它会看到 4 尚未访问并将其放入输出（结果）中。我想看看这个代码的问题，而不是它的其他工作方式，因为我需要在两个以上的孩子身上使用它。

标签： haskell

您将整个节点保留在visited集合中

| S.member node visited = ...
        -- ^ Node s a

因此，您可以将多个节点标记为 4，但具有不同的额外信息。你可能只想要一个visited :: S.Set s.

haskell - 树遍历 - DFS

问题描述

解决方案

推荐阅读