搜索二叉樹并回傳值的級別

我正在嘗試創建一個函式，該函式在樹中搜索一個值并回傳該值所在的級別，如果找不到該值則回傳 -1。為了嘗試這個，我寫了以下內容：

tree_search (NODE a t1 t2) x = tree_search_helper (NODE a t1 t2) x 1
tree_search_helper (NODE a t1 t2) x h = tree_search_helper t1 x h
  where
    tree_search_helper (NODE a t1 t2) x h 
      | not (tree_search_helper t1 x h 1 == -1) = tree_search_helper t1 x h 1  
      | (a == x) = h
      | otherwise = tree_search_helper t2 x h 1
    tree_search_helper (LEAF a) x h 
      | (a == x) = h 
      | otherwise = -1

但是，無論輸入如何，它都會回傳“1”。任何人都可以找到存在的問題！

uj5u.com熱心網友回復：

定義一個函式tree_search_helper，然后用 using 定義一個同名的區域函式，where勢必會帶來麻煩。讓我們考慮一下這個問題。

您有一個樹型別定義如下：

data Tree a = LEAF a | NODE a (Tree a) (Tree a) 
  deriving (Show, Read, Eq) 

您想找出給定值的位置有多深，或者回傳一些表明它沒有找到的值。正如@chepner 在評論中指出的那樣，這是該Maybe型別的一個很好的用途，因為我們可能會找到一個級別。

最簡單的情況是我們查看一片葉子，看看它是否具有我們想要的值。如果是，我們回傳當前級別，我們將其作為引數傳入。否則，我們回傳Nothing以指示未找到該值。

level (LEAF a) v cur_level 
  | a == v    = Just cur_level
  | otherwise = Nothing

另一種可能性是我們查看一個節點。如果它具有我們正在尋找的價值，它就像葉子一樣容易。如果不是，那么我們必須查看左側或右側分支，每次將當前級別增加一。

請記住，該函式回傳Maybe，因此我們對遞回呼叫level左分支的結果進行模式匹配以確定它是否找到了該值。如果沒有，我們可以搜索正確的分支。

level (NODE a l r) v cur_level
  | a == v    = Just cur_level
  | otherwise =
      case level l v (cur_level   1) of
        Just l  -> Just l
        Nothing -> level r v (cur_level   1)

0如果每次第一次通過當前級別很煩人，我們可以隱藏它。

level t v = level' t v 0
  where
    level' (LEAF a) v cur_level
      | a == v    = Just cur_level
      | otherwise = Nothing
    level' (NODE a l r) v cur_level
      | a == v    = Just cur_level
      | otherwise = 
          case level' l v (cur_level   1) of
            Just l  -> Just l
            Nothing -> level' r v (cur_level   1)

uj5u.com熱心網友回復：

如果您使用tree_search_helper t2 x h 1它進行呼叫將被解釋為(tree_search_helper t2 x h) 1，因此您使用相同級別進行呼叫，并將其加一。結果， thenot (tree_search_helper t1 x h 1 == -1)將永遠為真，因為 thetree_search_helper t1 x h 1永遠不會回傳-1。

因此，您可以將代碼重寫為：

tree_search_helper :: Eq a => Tree a -> a -> Int -> Int
tree_search_helper (NODE a t1 t2) x h 
  | tree_left != -1 = tree_left
  | a == x = h
  | otherwise = tree_search_helper t2 x (h 1)
  where tree_left = tree_search_helper t1 x (h 1)
tree_search_helper (LEAF a) x h 
  | a == x = h 
  | otherwise = -1

這tree_search只是：

tree_search :: Eq a => Tree a -> a -> Int
tree_search t x = tree_search_helper t x 1

然而，在 Haskell 中使用-1并不是很常見，通常回傳 a Maybe Int，并Nothing在找不到專案的情況下使用，所以：

import Data.Maybe(isJust)

tree_search_helper :: Eq a => Tree a -> a -> Int -> Maybe Int
tree_search_helper (NODE a t1 t2) x h 
  | isJust tree_left = tree_left
  | a == x = Just h
  | otherwise = tree_search_helper t2 x (h 1)
  where tree_left = tree_search_helper t1 x (h 1)
tree_search_helper (LEAF a) x h 
  | a == x = Just h
  | otherwise = Nothing

uj5u.com熱心網友回復：

更好的回傳型別是Maybe Int，其中Just h表示搜索成功并Nothing表示搜索失敗。這使您Monoid可以利用.AltMaybe

tree_search :: Eq a => Tree a -> a -> Maybe Int
tree_search t x = go x 1 t
    where go h (Leaf y) | x == y = Just h
                        | otherwise = Nothing
          go h (Node y l r) | x == y = Just h
                            | otherwise = let rec = go (h 1)
                                          in getAlt (Alt (rec l) <> Alt (rec r))

Alt x <> Alt y，當與Maybe值一起使用時，其行為類似于or布林值：Alt x如果x是一個Just值，Alt y否則。

標籤：哈斯克尔 二叉树

上一篇：使用高階函式在Haskell中查找可能值串列的最大值

下一篇：Haskell中的種類級別身份