5

我是一名 IT 学生，也是 OCaml 的新手

最近，为了考试而学习，我发现了这个练习。

给定： type 'a tree = Tree of 'a * 'a tree list

定义一个函数 mtree : 'a tree ->'a，它返回多路树中所有节点的最大值，遵循 OCaml 中通常的顺序关系 (<=)

我来做下面这样的事情，当然，这是行不通的。

let rec mtree (Tree (r, sub)) =
        let max_node (Tree(a, l1)) (Tree(b, l2)) =
            if a >= b then (Tree(a, l1)) else (Tree(b, l2)) in
        List.fold_left max_node r sub;;

在阅读对此的答案后，我将发布固定代码。

let rec mtree (Tree(r,sub)) =
    let max_node (Tree(a, l1)) (Tree(b, l2)) =
        if a >= b then a else b in
    List.fold_left (max_node) r (List.map mtree sub);;

想法是一样的，折叠列表比较节点，使用我的本地函数这样做，并通过在连续级别的节点列表上调用函数本身来遍历树。

但是，仍然无法正常工作。现在抱怨 fold_left 部分中的 max_node 。

Error: This expression has type 'a tree -> 'a tree -> 'a
       but an expression was expected of type 'a tree -> 'a tree -> 'a tree

在这里我肯定迷路了，因为我不明白为什么它期望返回一棵树

4

2 回答 2

4

这段代码非常可信（恕我直言）。缺少的关键是它不会遍历子树的子树。请注意，您将函数定义为递归的（这是非常合理的），但它从不调用自身。

另一个需要指出的问题是，问题陈述需要树中的“值”，但您的代码返回的是整个树节点。

于 2013-06-28T18:13:11.877 回答
2

回答我自己的问题有点蹩脚，但有了这里收到的提示，我可以完成它我将我的代码留在这里给任何面临类似问题的人。

let maxt (Tree(r,b)) =
    let rec aux (Tree(r,b)) =
        match b with
        [] -> [r]
        |l -> [r]@( List.fold_right (@) (List.map aux b) [])
    in List.fold_left max r (aux (Tree(r,b)));;
于 2013-06-29T08:29:14.627 回答