創建二叉樹斯卡拉

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 - 全都是因爲二叉樹的遞歸定義很好。