尝试实现Haskell二叉树搜索的路径记录

Question

我一直在玩Haskell中的二叉树,我正在尝试实现一个dfs变体,该变量返回从根节点到包含搜索值的节点的路径(由left和rights组成).我认为最好返回一个Maybe Directions类型.

以下是目前已实施的内容.

data Tree a = Empty | Node a (Tree a) (Tree a)
    deriving (Show, Eq)

data Direction = L | R 
    deriving (Show)
type Directions = [Direction] 

inTree :: (Eq a) => a -> Tree a -> [Direction]
inTree val (Node x l r)
    | val == x = []
    | l /= Empty = L:(inTree val l)
    | r /= Empty = R:(inTree val r)
    | otherwise = 

但我不知道如何让它遍历整棵树.我觉得我可能会过于强迫地思考.

Answer 1

你的想法Maybe Direction很好。我会按如下方式重写您的函数：

inTree :: (Eq a) => a -> Tree a -> Maybe [Direction]
inTree val Empty = Nothing
inTree val (Node x l r)
    | val == x = Just []
    | otherwise = (fmap (L:) (inTree val l)) <|> (fmap (R:) (inTree val r))

fmap荷兰国际集团的功能f上Maybe的结果Nothing如果原始值是Nothing和Just (f v)，如果它是Just v。在我们的例子中，如果递归调用找到了值（所以它返回了一个路径Just [Direction]），我们将Direction在当前节点上附加我们获取的值。

该<|>运营商来自Alternative实例Maybe。这是一个偏左的选择。在这里，我们使用它来选择返回的子树Just [Direction]（如果有的话）。

一个很好的练习是修改代码，使其返回x树中 s 的所有路径。