在O(n)时间复杂度下，如何在SML中将树转换为列表

Question

列表需要按顺序遍历。到目前为止，我拥有的是：

datatype tree =
Empty 
| Node of (tree * int * tree)
fun combine (t1 : tree, t2 : tree) : tree =
case t1 of
Empty => t2
| Node(l1,x1,r1) => Node(combine(l1,r1),x1,t2)
fun TTL (t : tree) : int list =
let val tree = combine(t, Empty) in
case tree of
Empty => []
| Node(l, x, r) => x :: TTL(l)
end

这没有按正确的顺序输出列表，我现在很困。请帮忙。

Answer 1

遍历右子树，然后将节点的值附加到该列表，然后遍历左子树，同时向第二个列表添加元素
您可以使用一个助手函数来完成此操作，该函数接受一个累积参数

fun TTL t =
let fun TTL' Empty ns = ns
| TTL' (Node(l, x, r)) ns = TTL' l (x::TTL' r ns)
in
TTL' t []
end

Answer 2

@molbdnilo发布的答案是有效的，但这是一个进一步的建议，它的格式不能很好地作为注释。利用SML的模式匹配功能、类型推理和泛型类型。

您有一个联合收割机功能：

fun combine (t1 : tree, t2 : tree) : tree =
case t1 of
Empty => t2
| Node(l1,x1,r1) => Node(combine(l1,r1),x1,t2)

让我们先去掉不必要的类型注释：

fun combine (t1, t2) =
case t1 of
Empty => t2
| Node(l1,x1,r1) => Node(combine(l1,r1),x1,t2)

现在，case ... of也不是真正必要的，因为在这种情况下，我们可以直接在函数的参数列表中进行模式匹配。

fun combine (Empty, t2) = t2
| combine (Node(l1, x1, r1), t2) = Node(combine(l1,r1),x1,t2)

最后，您的tree类型没有理由只需要在int上工作。

datatype 'a tree = Empty | Node of ('a tree * 'a * 'a tree)

希望随着学习的深入，其中一些技巧可以帮助您的代码更容易推理，更灵活。