确定 Haskell 中元素出现次数最多的二叉树级别

Question

给定一个二叉树，我试图找到元素出现次数最多的二叉树级别，例如Apple。

以下是规格：

data Fruit = Peach | Apple
data BTree a = Empty | Node a (BTree a) (BTree a)
levelWithMaxApples :: BTree Fruit -> Int

我能够创建一个函数，给定一个二叉树，它将计算其中Apple的出现次数。尽管如此，我还是无法弄清楚如何找到Apple出现次数最多的水平，有什么提示吗？

以下是一些测试：

tree1 = Node Peach Empty Empty
tree2 = Node Peach 
          (Node Peach
            (Node Apple
              Empty
              Empty)
            (Node Peach
              (Node Peach
                Empty
                Empty)
              (Node Peach
                Empty
                Empty)))
          (Node Apple
            (Node Apple
              Empty
              (Node Peach
                Empty
                Empty))
            Empty)
> levelWithMaxApples tree1
Nothing
> levelWithMaxApples tree2
2

这是我的尝试(在这种情况下，函数的名称应该countApples：

levelWithMaxApples Empty = 0
levelWithMaxApples (Node Apple l r) = 1 + levelWithMaxApple l + levelWithMaxApple r
levelWithMaxApples (Node Peach l r) = levelWithMaxApple l +   levelWithMaxApple r

感谢您的帮助！

Answer 1

这个答案是有文化的哈斯克尔。您可以使用.lhs扩展名保存它并将其加载到 GHCi 中。

> import Data.Ord (comparing)
> import Data.List (maximumBy)
> data Fruit = Peach | Apple
> data BTree a = Empty | Node a (BTree a) (BTree a)

尝试将其分解成更小的部分。首先，编写一个函数，该函数将生成树中所有级别的列表：

> levels :: BTree a -> [[a]]
> levels Empty = []
> levels (Node x l r) = [x] : combine (levels l) (levels r)
>   where combine [] ys = ys
>         combine xs [] = xs
>         combine (x:xs) (y:ys) = (x ++ y) : combine xs ys

(请注意，这里的combine辅助函数就像zipWith (++)一样，但在最短输入用尽后继续(。

一旦有了它，就很容易在列表中找到Apple的实例(如果你在Fruit定义中添加deriving Eq，会更容易(：

> countEach :: (a -> Bool) -> [[a]] -> [Int]
> countEach pred = map (length . filter pred)
> countApples :: [[Fruit]] -> [Int]
> countApples = countEach isApple
>   where isApple Apple = True
>         isApple _ = False

接下来，您可以使用 zip 简单地使用索引号标记列表中的每个项目，然后使用 maximumBy 选择计数最大的项目：

> levelWithMaxApples :: BTree Fruit -> Int
> levelWithMaxApples t = let ls = levels t
>                            counts = countApples ls
>                            labeled = zip [0..] counts
>                        in fst . maximumBy (comparing snd) $ labeled

Answer 2

这是另一种方式。

1. 从帮助程序函数开始。这将简单地构建该节点的原始列表和Apple计数。但是，这是为每个子树中的每个节点单独完成的，即列表将类似于[(根，1(，(L1,1(，(L2,0(，(R1,1(]

   import qualified Data.Map as M (fromListWith,toList)
   import qualified Data.List as L (sortBy)
   countApples' :: BTree Fruit -> Int -> [(Int,Int)]
   countApples' Empty _ = []
   countApples' (Node Apple l r) n = (n,1) : (countApples' l (n+1)) ++ (countApples' r (n+1))
   countApples' (Node Peach l r) n = (n,0) : (countApples' l (n+1)) ++ (countApples' r (n+1))
   

2. 接下来，我们使用上述步骤中的内容创建一个地图。在此步骤中，我们将聚合树的每个级别的值。然后我们转换回列表，并按元组的值部分降序排序。然后，具有最大苹果实例的级别将是列表顶部元组中的第一个元素。

   levelWithMaxApples  :: BTree Fruit -> Int
   levelWithMaxApples  Empty = error "Empty tree"
   levelWithMaxApples  x = fst $ head $ L.sortBy ((k1,v1) (k2,v2) -> compare v2 v1) $ M.toList $ M.fromListWith (+) $ countApples' x 0
   

演示

但是，您应该注意，这可能不是一个非常有效的解决方案，因为除了排序之外，还要与 Map 进行转换。

注意：排序部分主要基于此答案。

更新：这是一种完全使用地图的方法。

import qualified Data.Map as M
countApples :: BTree Fruit -> Int -> M.Map Int Int
countApples Empty _ = M.empty
countApples (Node Apple l r) n = M.unionsWith (+) [(M.singleton n 1 ),(countApples l (n+1)),(countApples r (n+1))] 
countApples (Node Peach l r) n = M.unionsWith (+) [(M.singleton n 0 ),(countApples l (n+1)),(countApples r (n+1))]
levelWithMaxApples  :: BTree Fruit -> Int
levelWithMaxApples t = fst $ M.foldWithKey (k v acc@(k',v') -> if v >= v' then (k,v) else acc) (-1,-1) $ countApples t 0

演示