1

这是一个家庭作业问题。

我的问题很简单：编写一个类型为'a btree ->'的函数btree_deepest，它返回树中最深元素的列表。如果树是空的，那么 deepest 应该返回 []。如果输入树的多个元素处于相同的最大深度，则 deepest 应返回包含这些最深元素的列表，并根据前序遍历进行排序。您的函数必须使用提供的 btree_reduce 函数，并且不能是递归的。

这是我的代码：

(* Binary tree datatype. *)
datatype 'a btree = Leaf | Node of 'a btree * 'a * 'a btree

(* A reduction function. *)
(* btree_reduce : ('b * 'a * 'b -> 'b) -> 'b -> 'a tree -> 'b) *)
fun btree_reduce f b bt =
   case bt of
   Leaf => b
   | Node (l, x, r) => f (btree_reduce f b l, x, btree_reduce f b r)

(* btree_size : 'a btree -> int *)
fun btree_size bt =
    btree_reduce (fn(x,a,y) => x+a+y) 1 bt

(* btree_height : 'a btree -> int *)
fun btree_height bt =
    btree_reduce (fn(l,n,r) => Int.max(l, r)+1) 0 bt

我知道我必须创建一个函数来传递给 btree_reduce 以构建最深元素的列表，这就是我步履蹒跚的地方。

如果允许我使用递归，那么我将只比较左右节点的高度，然后在更高的分支上递归（或者如果它们的高度相同，则在两者上递归），然后在高度为零时返回当前元素和将这些元素放入列表中。

我想我只需要朝着正确的方向努力就可以开始了……

谢谢！

更新：

这是一个无法编译的解决方案的尝试：

fun btree_deepest bt =
let
val (returnMe, height) = btree_reduce (fn((left_ele, left_dep),n,(right_ele, right_dep)) => 
    if left_dep = right_dep 
        then 
            if left_dep = 0 
                then ([n], 1) 
                else ([left_ele::right_ele], left_dep + 1)
        else 
            if left_dep > right_dep
                then (left_ele, left_dep+1) 
                else (right_ele, right_dep+1)
    ) 
    ([], 0) bt
in  
    returnMe
end
4

2 回答 2

3

为了获得最大深度的元素，您需要同时跟踪访问的每个子树的两件事btree_reduce：该子树的最大深度，以及在该深度找到的元素。将这些信息包装在一些数据结构中，你就有了你的类型'b（根据btree_reduce的签名）。

现在，当您需要在提供给 的函数中组合两个子树结果时btree_reduce，您有三种可能的情况：“左”子结果是“更深”、“更浅”或“等深”到“右”子结果。请记住，子结果表示每个子树中最深节点的深度和节点值，并考虑如何将它们组合以获得当前树的深度和最深节点的值。

如果您需要更多指针，我有一个btree_deepestready 的实现，我很想分享；我还没有发布它，因为你特别（并且光荣地）要求提示，而不是解决方案。

于 2012-11-09T08:42:52.380 回答
1

看看你的代码；看起来 X_ele 是单个元素还是列表存在一些混淆，这会导致类型错误。尝试在上面的第一个“else”分支中使用“@”运算符：

        if left_dep = 0 
            then ([n], 1) 
            else (left_ele @ right_ele, left_dep + 1)
于 2012-11-10T22:37:47.140 回答