search - 尝试为 Haskell 二叉树搜索实现路径记录

Question

我一直在玩 Haskell 中的二叉树，我正在尝试实现一个 dfs 变体，它返回从根节点到包含搜索值的节点的路径(由左和右组成)。我认为最好返回 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 instance of Maybe .这是对可能的左偏选择。这里我们用它来挑选返回 Just [Direction] 的子树。 (如果有的话)。

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