在Scala中製作一個非常基本的二叉樹

Question

我想在Scala中製作一個非常簡單的二叉樹用於數據存儲和遍歷。

現在我有：

trait Tree 
case class Node(left: Tree, value: String, right: Tree) extends Tree 

我的問題：

1. 我怎麼能還包括一個指向父？

2. 我能以任何方式將左右指向爲空嗎？或者是根節點的父指針？

3. 我該如何遍歷樹？

4. 是否容易更新節點的值？

Answer 1

1. 不能與不變的情況下類。這是一種循環依賴：您需要父級創建子級，但您還需要子級創建父級。另一方面，大多數樹遍歷算法並不需要父對象，因爲父對象通常在堆棧中，或者可以存儲在某個地方。

2. 是的，我們通常有一個特徵的單一實例（object）表示這些：

   case object EmptyNode extends Tree 
   

3. 有很多的算法在那裏，廣度優先搜索和深度優先搜索是最常見的。實施它們是一項很好的練習。但在斯卡拉側一點幫助的left和right，我們通常模式匹配，看看我們下一步需要做：

   tree: Tree match { 
       case EmptyNode => // do nothing, return, etc. 
       case Node(left, value, right) => 
       // Do inorder, preorder, postorder operation order 
       // You will also probably be processing left and right as well 
   } 
   

4. 不，你的猜測是正確的，在樹上用不變的情況下，類很難更新，因爲如果你更新葉節點，那麼你必須重新創建它上面的所有東西。有所謂的鏡頭和鏡頭庫，可以幫助你，雖然他們可能會更先進一些。在Scala中流行的一個是Monocle。

---

好像你只是用編程或新斯卡拉開始，所以我會建議使用var -s代替val S：

case class Node(var left: Tree, var value: String, var right: Tree) extends Tree 

此外，如果你的特質是密封的（ sealed trait Tree），那麼編譯器會告訴你，如果你沒有在模式匹配中處理其中一個子類型。

編輯：

基礎上的評論開始這方面的工作：

sealed trait Tree 
case class Node(var left: Tree, var value: String, var right: Tree, var parent: Tree) extends Tree 
case object EmptyNode extends Tree 

Answer 2

如果它是一個需要二叉樹設施的程序員有用的，我寫了一些Scala的特性，可以被繼承和/或混合以提供基本的紅黑樹功能以及一些其他基於樹的算法：

http://erikerlandson.github.io/blog/2015/09/26/a-library-of-binary-tree-algorithms-as-mixable-scala-traits/