确定元素在 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

这个答案是literate Haskell。您可以使用 .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 的实例（如果你将 deriving Eq 添加到你的 Fruit 定义中会更容易）：

> 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 到 select 具有最大计数的那个：

> 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

这是另一种方式。

从辅助函数开始。这将简单地构建节点的原始列表和该节点的 Apple 计数。但是，这是针对每个子树中的每个节点分别完成的，即列表将类似于 [(Root,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))

接下来，我们使用上面步骤中的内容创建一个地图。在此步骤中，我们将聚合树的每个级别的值。然后我们转换回列表并按元组的值部分降序排序。具有最大 apple 实例的级别将成为列表头部元组中的第一个元素。
```
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
```

Demo

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

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

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

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

Demo

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

Determine binary tree level with most occurrences of an element in Haskell

binary-tree

haskell