我将以二叉树为例进行说明,它与您的结构非常相似。您需要把它转换成适用于您的数据类型。假设我有一棵二叉树。
data Tree a
= Leaf a
| Node (Tree a) (Tree a)
deriving (Eq, Show)
我希望找到具有最大深度的值(可能有多个!)。 我解决这个问题的方法是递归地遍历每个分支,记录我走过的深度,然后将底部的值及其深度返回。
首先,我将定义函数结构
import Data.List (sortBy, groupBy)
import Data.Ord (comparing)
import Data.Function (on)
getDeepest :: Tree a -> [a]
getDeepest tree
= map fst
. head
. groupBy ((==) `on` snd)
. sortBy (flip (comparing snd))
$ go tree 0
where
go :: Tree a -> Int -> [(a, Int)]
go (Leaf a) n = undefined
go (Node l r) n = undefined
这是Haskell中常见的递归格式。我有一个本地辅助函数,它携带一个额外的值,我想将其初始化为特定的值,在这种情况下为深度
0
。我已经包含了我知道的逻辑,以便以良好的格式获得输出。
flip (comparing snd)
将进行反向排序,因此最大深度将首先出现。然后,我们按深度分组,提取第一组,然后从值中剥离深度。
现在我们只需要定义
go
的操作。我们知道当我们到达底部时,我们想要将该值与我们找到的深度添加到累加器中,所以
go (Leaf a) n = [(a, n)]
这个案例很简单,我们只需要将值和深度制作成元组并将其包装为列表即可。对于另一种情况,我们想要遍历每个分支,找到最深的元素,并从两个分支中返回最深的元素。
go (Node l r) n = go l (n + 1) ++ go r (n + 1)
这里就是递归的发生地。虽然这并不是最高效的算法(因为Haskell列表对此并不擅长,但为了简单起见我们将使用它们),但仍然相当简单。我们只需要沿着每一侧向下移动,并通过1
增加深度。因此整个算法如下:
getDeepest :: Tree a -> [a]
getDeepest tree
= map fst
. head
. groupBy ((==) `on` snd)
. sortBy (flip (comparing snd))
$ go tree 0
where
go :: Tree a -> Int -> [(a, Int)]
go (Leaf a) n = [(a, n)]
go (Node l r) n = go l (n + 1) ++ go r (n + 1)
例如:
myTree :: Tree Int
myTree =
Node
(Node
(Leaf 1)
(Node
(Leaf 2)
(Leaf 3)))
(Leaf 4)
可以将其视为:
Node
/ \
Node Leaf 4
/ \
Leaf 1 Node
/ \
Leaf 2 Leaf 3
然后将
getDeepest
应用于它,返回
[2, 3]
。我建议您从
getDeepest
中删除类型签名,并尝试在
go tree 0
之前删除各种函数(从顶部开始),以便您可以看到每个步骤的样子,这应该有助于您更好地理解算法。
[1, 2, 3]
?为什么不是1
、2
或3
?顺便说一下,这不是由您的值构造函数Elem
和List
构造的值。 - Lee Duhem