list - SML - 如何从树的后序扫描中创建列表

Question

如何在 SML 中实现一个获取树并返回列表的函数。根据树的后序扫描，该列表由树节点中的值组成。

树datatype是：

datatype 'a Tree = Leaf | Branch of 'a * 'a Tree * 'a Tree;

Answer 1

这可以通过以下方式简单地完成：

 fun createList(Leaf) = []
=   | createList(Branch(el, left, right)) = createList(left) @ createList(right) @ [el];

如果你有一个分支首先访问它的左子树（createList(left)），然后是右子树（createList(right)），然后附加元素el，所以基本上做后序树遍历所做的事情。如果您想从Leaf（一棵空树）创建一个列表，结果将是一个空列表。

Answer 2

更有效的解决方案：

local
   fun helper Leaf result = result
     | helper (Branch (el, left, right)) result = helper left (helper right (el::result))
in
   fun createList tree = helper tree nil
end

这更有效，因为@必须完全展开其左侧参数以将其添加到右侧参数，如果您反复将其应用于越来越长的列表，这将变得非常昂贵。相比之下，通过使用helper将子树的后序遍历添加到传入列表的函数，您可以只构建整个列表一次。