创建二叉树斯卡拉

Question

对于家庭作业的总和树我写了一些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

我得到这个能够以更好的方式来实现的感觉，也许你有什么建议？

Answer 1

首先，我相信，如果我可以这么说，你已经做了很做得好。我可以建议一对夫妇的细微变化对你的代码：

abstract class Tree 
case class Node(value: Int, left: Tree, right: Tree) extends Tree 
case object Nil extends Tree 

1. 树并不需要是一个案例类，除了使用的情况下，作为类非叶节点，因为可能的错误已被弃用自动生成方法的行为。
2. Nil是一个单例，最好定义为case-object而不是case-class。

3. 另外考虑合格的超类Tree与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辅助函数也可以被定义为（I上面所用的替代的符号是可能是因为花括号中的一系列案例被视为函数文字）：

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)) 
    } 
} 

你想出了递归是唯一可能的方向，让你遍历树并产生不可变数据结构的修改后的副本。任何叶节点必须在被添加到根之前被首先创建，因为树的单个节点是不可变的，并且在构建之前必须知道构造节点所需的所有对象：在创建根之前需要创建叶节点节点。

Answer 2

您的解决方案可能是更有效的（当然使用较少的堆栈），但这里有一个递归解决方案，FWIW

def sum(tree:Tree):Tree ={ 
    tree match{ 
    case Nil =>Nil 
    case Tree(a, b, c) =>val left = sum(b) 
         val right = sum(c) 
         Tree(a+total(left)+total(right), left, right) 
    } 
} 

def total(tree:Tree):Int = { 
    tree match{ 
    case Nil => 0 
    case Tree(a, _, _) =>a 
} 

Answer 3

弗拉德写道，您的解决方案有关于这种折叠的唯一一般形状。

还有一种摆脱节点值匹配的方法，不仅仅是将其分解出来。我个人更喜欢这种方式。

您使用匹配，因为不是你从递归折叠得到的每个结果都带有一个和数。是的，不是每一棵树都可以承载它，零无价值的地方，但你的褶皱不仅限于树木，是吗？

因此，让我们：

case class TreePlus[A](value: A, tree: Tree) 

现在，我们可以把它折叠这样的：

def sumTree(t: Tree) = fold[TreePlus[Int]](t, TreePlus(0, Nil), (v, l, r) => { 
    val sum = v+l.value+r.value 
    TreePlus(sum, Node(sum, l.tree, r.tree)) 
}.tree 

当然是不是真的需要TreePlus因为我们在标准库中的经典产品Tuple2。

Answer 4

您可能已经开始做家庭作业了，但我认为仍然值得指出的是，您的代码（以及其他人的答案中的代码）的样子是您如何建模二叉树的直接结果。如果不是使用代数数据类型（Tree,Node,Nil），而是使用递归类型定义，则不必使用模式匹配来分解二叉树。这是我的一个二叉树的定义：

case class Tree[A](value: A, left: Option[Tree[A]], right: Option[Tree[A]]) 

正如你可以看到有没有必要Node或Nil这里（后者只是荣耀null反正 - 你不想在你的代码像这样的东西，你？）。

通过这样的定义，fold基本上是一个班轮：

def fold[A,B](t: Tree[A], z: B)(op: (A, B, B) => B): B = 
    op(t.value, t.left map (fold(_, z)(op)) getOrElse z, t.right map (fold(_, z)(op)) getOrElse z) 

而且sumTree也短和甜：

def sumTree(tree: Tree[Int]) = fold(tree, None: Option[Tree[Int]]) { (value, left, right) => 
    Some(Tree(value + valueOf(left, 0) + valueOf(right, 0), left , right)) 
}.get 

其中valueOf助手被定义为：

def valueOf[A](ot: Option[Tree[A]], df: A): A = ot map (_.value) getOrElse df 

无需任何模式匹配e - 全都是因为二叉树的递归定义很好。