3

我正在尝试编写一个函数来搜索玫瑰树中的给定元素并返回它的位置。

当我向您展示我已经得到的东西时，可能会更清楚：

给定具有定义的树：

数据树文本 = 节点值 [树值]

例如：

test = Node "1" [
          Node "11" [
               Node "111" [], 
               Node "112" [
                  Node "1121" [], Node "1122" [], Node "1123" []
               ]
          ], 
          Node "12" []
      ]


            1
      11         12
111      112    
     1121 1122 1123

我正在寻找功能搜索：

search :: String -> Tree String -> [Integer]

搜索 1123 测试 -> 应返回 [1,2,3]
- 1=11 的第一个子树 -> 11=112 的第二个子树，112=1123 的第三个子树

我知道如何遍历树，

display (Node v xs) = v ++ concatMap display xs

但是不知道如何为子树数组的每个元素分配整数值，并另外从树的上部到下部递归地传递它。你们能指导我在哪里/如何寻找解决方案吗？我对 Haskell 很陌生..

4

1 回答 1

4

最简单的方法是让函数首先返回具有所需数据的节点的所有路径列表（我想，树中最多应该只有一个，但这没关系），然后使用第一个：

searchList :: (Eq a) => a -> Tree a -> [[Integer]]
searchList val (Node dat subs)
    | val == dat = [[]]  -- empty path
    | otherwise  = concat [map (c:) (searchList val t) | (c,t) <- zip [1 .. ] subs]

search :: Eq a => a -> Tree a -> [Integer]
search val t = case searchList val t of
                 (p:_) -> p
                 _ -> error "Value not found"

如果 Daniel Wagner 的怀疑是正确的并且您的树是尝试的，那么您可以更有效地搜索，但原理保持不变，但是，由于我们现在知道我们要么有一个节点具有所需的数据，要么没有，结果更合适的是Maybe [Integer]：

import Data.List (isPrefixOf)
import Control.Monad -- for the MonadPlus instance of Maybe

searchTrie :: String -> Tree String -> Maybe [Integer]
searchTrie target (Node val subs)
    | val == target = Just []
    | val `isPrefixOf` target = case dropWhile smaller (zip [1 .. ] subs) of
                                  ((c,t):_) -> fmap (c:) $ searchTrie target t
                                  _ -> Nothing
    | otherwise = Nothing
      where
        smaller (_,Node v _) = v < take (length v) target
于 2012-06-02T18:26:44.943 回答