记录在二叉树数据的所有路径

Question

我试图写一个函数，其中记录了导致数据N.所有路径

任何人都可以给我一些指点作为即时通讯越来越糊涂，什么时候记录路径？就好像我从一开始就开始，我可能会以导致知道在哪里的路径结束。 （记录路径为L | R）

任何人都可以给我一些这方面的逻辑！

感谢

我曾经在一个给定的路径树的工作，但这个我不能想出

data Tree = N | F Tree Tree deriving Show 
data Dir = L | R deriving Show 
type Path = [Dir]  

这样一棵树可能是F N (F (F N N) (F N (F N N))) 和路径是[L,L,L,R]

我已经将功能插入有N个节点或给定路径的地方。

但我不能让我的脑袋绕着记录路径的逻辑。

Answer 1

main = print . findAllLeaves $ F N (F (F N N) (F N (F N N))) 

data Tree = N | F Tree Tree deriving Show 
data Dir = L | R deriving Show 
type Path = [Dir]  

descend :: Tree -> Dir -> Tree 
descend (F l _) L = l 
descend (F _ r) R = r 
descend _ _ = undefined 

findAllLeaves :: Tree -> [Path] 
findAllLeaves N = [[]] 
findAllLeaves tree = do dir <- [L, R] 
         map (dir:) $ findAllLeaves (descend tree dir) 

结果

[[L],[R,L,L],[R,L,R],[R,R,L],[R,R,R,L],[R,R,R,R]] 

我使用列表单子挑L和R “同时”，和下降两个分支。得爱不确定性！

---

说明：

我希望descend是非常明显的。你给它一棵树和一个方向，它沿着这个方向下降。

findAllLeaves是有趣的一个。它是如何工作的？

我们将在一分钟内讨论基本情况，findAllLeaves N = [[]]。

递归大小写在列表monad中，使用do表示法。第一行很简单：选择L或R并将其分配给dir。 这个list monad实际上会选择两个，并且将每个结果都连接起来并将它们连接在一起。这是他们理解的关键。这正是你所要求的：什么是以L开头的所有路径，以及从R开始的所有路径是什么？把它们放在一起，你有从当前节点到其后代叶节点的所有路径。

第二行应该从上一段的描述中相当清楚。在给定方向下降树（descend tree dir），从该点找到所有树叶（findAllLeaves），然后将选择的方向预先分配给每个子路径（map (dir:)）。

那么为什么基本情况下[[]]？那么，请考虑一下基本案例之上的案例。所以，例如，findAllLeaves (F N N)。当我们选择dir = L，我们评估了下联：

map (L:) $ findAllLeaves (descend (F N N) L) 

递减留下给我们只是N

map (L:) $ findAllLeaves N 

然后，我们已经打的基本情况：

map (L:) $ [[]] 

现在你能看看为什么我们有这个奇怪的基本情况？列表中有一个空的列表？因为我们要将(L:)映射到它上面，换句话说，将L预先添加到外部列表中的每个列表。结果如下：

[[L]] 

当我们在dir = R时得到了类似的结果。

[[R]] 

那么接下来列表单子串接那些一起

[[L]] ++ [[R]] 

而且我们最终

[[L], [R]] 

如果任何这仍不清楚，请让我知道在评论和我会尽力澄清。

Answer 2

这不是一个完整的答案，但这是我想到的方式：您可以对树进行深度优先搜索（简单递归调用），并确保您返回在正确的事情上。你知道当你递归到一个子树中时，你会得到一个返回路径列表，对吧？然后，您只需要考虑如何针对您的子问题得到答案：在这种情况下，请按照您到目前为止所走过的路线扩展路径。我喜欢写东西

search N = [[]] -- one empty path 
search (F x y) = map (L:) (search x) ++ 
    map (R:) (search y) 

也就是说，在前面加上Left从左侧子问题来的解决方案，并Right到那些从右边子问题来了。