SML - 如何通过树的后序扫描创建列表

发布于 2024-11-04 07:24:49 字数 167 浏览 7 评论 0原文

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

树数据类型是：

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

原文

How to implement a function in SML which gets a tree and returns a list. The list consists of the values in the tree nodes according to postorder scan of the tree.

The tree datatype is:

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

若水微香 2024-11-11 07:24:49

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

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

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

That can be done simply by:

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

If you have a branch first visit it's left subtree (createList(left)), then it's right subtree (createList(right)) and afterwards append the element el, so basically do what a postorder tree traversal does. If you want to create a list from a Leaf (an empty tree) the result would be an empty list.

回复收藏 0 原文

那些过往 2024-11-11 07:24:49

更有效的解决方案：

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 函数，您只需构建整个列表一次。

A more efficient solution:

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

This is more efficient because @ has to completely unwind its left-hand argument to prepend it to the right-hand argument, which becomes very expensive if you are repeatedly applying it to longer and longer lists. By contrast, by using a helper function that prepends a subtree's postorder traversal onto a passed-in list, you can build the entire list just once.

回复收藏 0 原文

~没有更多了~