Создание дерева сумм двоичного дерева scala

Ответ 1

Прежде всего, я верю, и если я могу так сказать, вы проделали очень хорошую работу. Я могу предложить пару небольших изменений в вашем коде:

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

• Дерево не обязательно должно быть классом case, кроме использования case-класса, поскольку не-лист node устарел из-за возможного ошибочного поведения автоматически генерируемых методов.
• Nil является одноэлементным и лучше всего определяется как case-объект вместо case-class.

• Дополнительно рассмотрим квалификационный суперкласс 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 type inferer работает через выражение последовательно слева направо, говоря ему рано, что мы собираемся иметь дело с 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)) 
  }
}

Рекурсия, с которой вы столкнулись, - это единственное возможное направление, которое позволяет вам пересекать дерево и создавать измененную копию неизменяемой структуры данных. Любые листовые узлы должны быть созданы сначала перед добавлением в корень, потому что отдельные узлы дерева неизменяемы, и все объекты, необходимые для построения node, должны быть известны до начала строительства: необходимо создать листовые узлы, прежде чем вы сможете создайте root node.

Ответ 2

Как пишет Влад, ваше решение имеет единственную общую форму, которую вы можете иметь с такой складкой.

Тем не менее существует способ избавиться от соответствия значения node, а не только его фактора. И лично я бы предпочел это именно так.

Вы используете соответствие, потому что не каждый результат, полученный из рекурсивной складки, несет с собой сумму. Да, не каждое дерево может нести его, Нилу не место для значения, но ваша своя не ограничивается деревьями, не так ли?

Итак, пусть:

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.

Ответ 3

Ваше решение, вероятно, более эффективно (конечно, использует меньше стека), но здесь рекурсивное решение, 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
}

Ответ 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

Никакое сопоставление шаблонов не требуется везде - все из-за хорошего рекурсивного определения бинарных деревьев.