使用二叉树中的数据记录所有路径

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

这不是一个完整的答案,但这是我考虑它的方式:你可以对树进行深度优先搜索(简单的递归调用),并确保你正在返回正确的东西一路攀升.你知道,当你进入子子树时,你会得到一个回路列表,对吗？然后,您只需要考虑如何根据您的子问题得到答案:在这种情况下,将路径扩展到您目前为止所经历的路径.我写的东西就像

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

也就是说,前面Left是来自左子问题的解决方案,以及Right来自右子问题的解决方案.

Answer 2

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]]

我使用list monad同时"同时"选择L和R,然后下降两个分支.要爱不确定!

说明:

我希望descend很清楚.你给它一棵树和一个方向,它沿那个方向下降树.

findAllLeaves是有趣的.它是如何工作的？

我们将findAllLeaves N = [[]]在一分钟内谈论基本情况.

递归的情况写在列表monad中,带有do表示法.第一行很简单:选择L或R分配给它dir.列表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]]

那么列表monad将这些连接起来

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

我们最终得到了

[[L], [R]]

如果其中任何一项仍不清楚,请在评论中告诉我,我会尽力澄清.