创建二叉树scala的和树

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. Tree不需要是case-class,除了使用case-class作为非叶节点之外,由于自动生成的方法可能存在错误行为,因此不推荐使用.
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 辅助函数也可以定义为(上面使用的替代符号是可能的,因为花括号中的一系列情况被视为函数文字):

def nodeValue (t:Tree) = t match {
  case Node(v,_,_) => v
  case _ => 0
}

接下来的一点改进是fold使用Tree(fold[Tree])的参数化方法.因为Scala类型inferer按顺序从左到右依次告诉它我们将要处理Tree's让我们在定义函数文字时省略类型信息,这些信息将被传递给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)) 
  }
}

您提出的递归是唯一可能的方向,它允许您遍历树并生成不可变数据结构的修改副本.在添加到根之前,必须首先创建任何叶节点,因为树的各个节点是不可变的,构造节点所需的所有对象必须在构造之前知道:在创建根之前需要创建叶节点节点.