Sml 折叠一棵树

本文介绍了Sml 折叠一棵树的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

到目前为止，我正在尝试使用 fold 函数来获取树的乘积，这就是我所拥有的.我对如何在遍历树时使用折叠方法感到困惑

datatype 'a bin_tree = 'a 的叶子|'a bin_tree * 'a bin_tree 的节点有趣的树折 g z 空 = z|treefold g z (Node (l, x, r)) = g(x, g(treefold g z l, treefold g z r)

解决方案

折叠二叉树时，

datatype 'a tree = Leaf |'a tree * 'a * 'a tree的分支

您可以通过

用法

val treelist = treefold op:: []val treeproduct = treefold op* 1val treecount = treefold (fn (_, count) => count + 1) 0

额外

如果每个分支/节点都没有 'a 值，则中序遍历没有意义.

另请参阅如何在树上应用尾递归以避免堆栈溢出.>

对于一些涉及树遍历的问题，提供遍历的上下文可能很有用，例如 paramorphisms 做:

fun treecata_preorder f acc1 Leaf = acc1|treecata_preorder f acc1 (branch as Branch (left, a, right)) =让 val acc2 = treecata_preorder f acc1 离开val acc3 = f (a, 分支, acc2)val acc4 = treecata_preorder f acc3 right在 acc4 结束

这是对 treefold_preorder 的一个小小的概括，其中 f 被馈送到整个 branch.

这可以让您例如在祖先树中找到谓词对其子树成立的人，

有趣的 treefilter pred =treecata_preorder (fn (x, xtree, acc) => if pred xtree then x::acc else acc) []fun branchValue Leaf = NONE|branchValue (Branch (_, value, _)) = 一些值有趣的父母叶 = []|父母(分支(左，_，右))=List.mapPartial (fn xopt => xopt) [branchValue left, branchValue right]类型名称 = 字符串类型年龄 = int数据类型 person = 姓名人 * 年龄乐趣退休(人(_，年龄))=年龄>= 70fun hasRetiredParent 树 = List.exists 已退休(父树)val peopleWithRetiredParents = treefilter hasRetiredParent

树遍历的另一个简洁概念是zippers(LYAH 章节).

I am trying to get the product of a tree by using the fold function so far this is what I have. I am confused on how to use the fold method while transversing the tree

datatype 'a bin_tree = Leaf of 'a | Node of 'a bin_tree * 'a bin_tree fun treefold g z Empty = z | treefold g z (Node (l, x, r)) = g(x, g(treefold g z l, treefold g z r)

解决方案

When folding a binary tree,

datatype 'a tree = Leaf | Branch of 'a tree * 'a * 'a tree

you may traverse it in different ways. Among common strategies you have,

(* Pre-order *) fun treefold_preorder f acc1 Leaf = acc1 | treefold_preorder f acc1 (Branch (left, a, right)) = let val acc2 = treefold_preorder f acc1 left val acc3 = f (a, acc2) val acc4 = treefold_preorder f acc3 right in acc4 end (* In-order *) and treefold_inorder f acc1 Leaf = acc1 | treefold_inorder f acc1 (Branch (left, a, right)) = let val acc2 = f (a, acc1) val acc3 = treefold_inorder f acc2 left val acc4 = treefold_inorder f acc3 right in acc4 end (* Post-order *) and treefold_postorder f acc1 Leaf = acc1 | treefold_postorder f acc1 (Branch (left, a, right)) = let val acc2 = treefold_postorder f acc1 left val acc3 = treefold_postorder f acc2 right val acc4 = f (a, acc3) in acc4 end

which Wikipedia nicely illustrates as,

Usage

val treelist = treefold op:: [] val treeproduct = treefold op* 1 val treecount = treefold (fn (_, count) => count + 1) 0

Extra

In-order traversal isn't meaningful if each branch/node doesn't have an 'a value.

See also how to apply tail-recursion on trees to avoid stack overflows.

For some problems that involve tree traversal, it may be useful to supply the context of the traversal like paramorphisms do:

fun treecata_preorder f acc1 Leaf = acc1 | treecata_preorder f acc1 (branch as Branch (left, a, right)) = let val acc2 = treecata_preorder f acc1 left val acc3 = f (a, branch, acc2) val acc4 = treecata_preorder f acc3 right in acc4 end

This is a slight generalisation of treefold_preorder in which f is fed the entire branch.

This lets you e.g. find people in an ancestry tree for which a predicate holds for their subtree,

fun treefilter pred = treecata_preorder (fn (x, xtree, acc) => if pred xtree then x::acc else acc) [] fun branchValue Leaf = NONE | branchValue (Branch (_, value, _)) = SOME value fun parents Leaf = [] | parents (Branch (left, _, right)) = List.mapPartial (fn xopt => xopt) [branchValue left, branchValue right] type name = string type age = int datatype person = Person of name * age fun retired (Person (_, age)) = age >= 70 fun hasRetiredParent tree = List.exists retired (parents tree) val personsWithRetiredParents = treefilter hasRetiredParent

Another neat notion for tree traversal are zippers (LYAH chapter).