对于家庭作业,我编写了一些scala代码,其中包含以下类和对象(用于对二叉树进行建模):
object Tree {
def fold[B](t: Tree, e: B, n: (Int, B, B) => B): B = t match {
case Node(value, l, r) => n(value,fold(l,e,n),fold(r,e,n))
case _ => e
}
def sumTree(t: Tree): Tree =
fold(t, Nil(), (a, b: Tree, c: Tree) => {
val left = b match {
case Node(value, _, _) => value
case _ => 0
}
val right = c match {
case Node(value, _, _) => value
case _ => 0
}
Node(a+left+right,b,c)
})
}
abstract case class Tree
case class Node(value: Int, left: Tree, right: Tree) extends Tree
case class Nil extends Tree
我的问题是关于
sumTree
函数,该函数创建一棵新树,其中节点的值等于其子项的值之和加上它自己的值。我觉得它看上去很丑陋,我想知道是否有更好的方法可以做到这一点。如果我使用自顶向下的递归功能,会更容易,但是我无法提供这样的功能。
我必须使用代码中的签名来实现
fold
函数,以计算sumTree
我觉得可以用更好的方法来实现,也许您有建议?
最佳答案
首先,我相信,如果可以这样说,您做得很好。我可以建议对您的代码进行一些细微更改:
abstract class Tree
case class Node(value: Int, left: Tree, right: Tree) extends Tree
case object Nil extends Tree
Nil
是单例,最好定义为案例对象而不是案例类。 Tree
限定父类(super class)sealed
。 sealed
告诉编译器该类只能从同一源文件内继承。这使编译器在以下匹配表达式未穷尽时发出警告-换句话说,并不包括所有可能的情况。密封的抽象类树
接下来的几处改进可以对
sumTree
进行:def sumTree(t: Tree) = {
// create a helper function to extract Tree value
val nodeValue: Tree=>Int = {
case Node(v,_,_) => v
case _ => 0
}
// parametrise fold with Tree to aid type inference further down the line
fold[Tree](t,Nil,(acc,l,r)=>Node(acc + nodeValue(l) + nodeValue(r) ,l,r))
}
nodeValue
辅助函数也可以定义为(我上面使用的另一种表示法是可能的,因为花括号中的一系列情况被视为函数文字):def nodeValue (t:Tree) = t match {
case Node(v,_,_) => v
case _ => 0
}
接下来的一点改进是使用
fold
(Tree
)参数化fold[Tree]
方法。因为Scala类型推断器通过表达式从左到右顺序地工作,所以很早就告诉我们将要使用Tree进行处理,因此在定义函数文字时,我们将省略类型信息,该信息将进一步传递给fold
。因此,这里是完整的代码,包括建议:
sealed abstract class Tree
case class Node(value: Int, left: Tree, right: Tree) extends Tree
case object Nil extends Tree
object Tree {
def fold[B](t: Tree, e: B, n: (Int, B, B) => B): B = t match {
case Node(value, l, r) => n(value,fold(l,e,n),fold(r,e,n))
case _ => e
}
def sumTree(t: Tree) = {
val nodeValue: Tree=>Int = {
case Node(v,_,_) => v
case _ => 0
}
fold[Tree](t,Nil,(acc,l,r)=>Node(acc + nodeValue(l) + nodeValue(r) ,l,r))
}
}
您想出的递归是使您遍历树并生成不可变数据结构的修改副本的唯一可能方向。必须先创建任何叶节点,然后再将其添加到根节点,因为树的各个节点是不可变的,并且在构造之前必须知道构造节点所需的所有对象:在创建根节点之前,必须先创建叶节点节点。
关于scala - 创建二叉树scala的求和树,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/9658731/