如何以 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)

希望随着您深入学习，其中一些技巧有助于使您的代码更易于推理且更灵活。