如何知道不规则树的最大值？

Question

我有一个不规则定义的树，我如何运行通过它并找到其中的最大值？

我的策略是建立一个列表并取出更大的值，我的问题是，我只知道二叉树，我有左边和右边，像这样：Node x Empty Empty

我现在有这个结构：

tree= No 2 [No 3 [No 6 []], No 4 [No 7 [], No 8 []], No 5 []]

data TreeIrr a = No a [TreeIrr a]

应该如何遍历？

这是我能做的最好的了：

maxi :: ArvIrr a -> [a]
maxi (No a []) = [a]
maxi (No a l@((No b []):z)) = [a]++[b]++(maxis l)
                    where
                     maxis ((No x k):(No y z):ls) = [y]++maxis ls
maxi (No a [k]) = [a]++(maxi k)

Answer 1

只需使用一个简单的类似 dfs 的递归遍历：

data TreeIrr a = No a [TreeIrr a]

findMax :: Ord a => TreeIrr a -> a
findMax (No x []) = x     -- For a tree without subtrees the maximum is it's value
findMax ( No x subtrees ) =
    maximum ( x : map findMax subtrees)      -- For a tree with subtrees the maximum is the maximum among it's root value or the maximum of it's subtrees

然后

>> findMax (No 2 [No 3 [No 6 []], No 4 [No 7 [], No 8 []], No 5 []])
8

更新：稍微思考一下，基本情况在这里是多余的。所以只是

findMax :: Ord a => TreeIrr a -> a
findMax ( No x subtrees ) = maximum ( x : map findMax subtrees)

会很好

Answer 2

假设我们有一个遍历函数：

maxi :: ArvIrr a -> [a]

我们应该如何将其扩展到列表树？

maxiList :: [ArvIrr a] -> [a]

嗯，我们可以使用 map:

maxiList l = map maxi l  -- WRONG type [[a]]

但我们得到的是列表的列表，而不是单个列表。没问题，让我们把它们全部连接起来。

maxiList l = concat (map maxi l)

好的，现在让我们假设我们有 maxiList 工作，并根据它构建 maxi。这很简单：

maxi (No a l) = a : maxiList l

所以，把所有东西放在一起：

maxi :: ArvIrr a -> [a]
maxi (No a l) = a : maxiList l
maxiList :: [ArvIrr a] -> [a]
maxiList l = concat (map maxi l)

我们可以通过删除 maxiList 并内联它来进一步简化它。

maxi :: ArvIrr a -> [a]
maxi (No a l) = a : concat (map maxi l)

而concat (map maxi l)可以改写为concatMap maxi l, 利用 concatMap 库函数。

maxi :: ArvIrr a -> [a]
maxi (No a l) = a : concatMap maxi l

要计算最大值，您可以使用

maxInTree :: Ord a => ArvIrr a -> a
maxInTree t = maximum (maxi t)

如果你愿意，你可以进一步简化这段代码，这样就连中间列表都不建了，直接计算最大值。对于 Haskell 初学者来说，这可能有点挑战，但它可能很有趣。首先替换上面代码中的 concat ...

Answer 3

data TreeIrr a = No a [TreeIrr a]

这样一棵树的最大元素是两个值中的最大值：

根音符处的元素。
其子项的最大值中的最大值。

因此：

treeMaximum :: Ord a => TreeIrr a -> a
treeMaximum (No a []) = a
treeMaximum (No a children) = max a (maximum (map treeMaximum children))

其中 max :: Ord a => a -> a -> a 和 maximum :: Ord a => [a] -> a 是标准库函数。

如何知道不规则树的最大值？

How to know maximum at an irregular tree?

haskell