在 Scala 中制作一个非常基本的二叉树

我正在尝试在 Scala 中制作一个非常简单的二叉树，用于数据存储和遍历。

现在我有：

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

我的问题：

1. 我怎样才能包含一个指向父级的指针？

2. 我可以以任何方式将左指针和右指针设置为空吗？或者根节点的父指针？

3. 我怎样才能真正遍历这棵树？

4. 更新节点的值容易吗？

1. 不适用于不可变的案例类。这是一种循环依赖：您需要父级来创建子级，但也需要子级来创建父级。另一方面，大多数树遍历算法实际上并不需要父级，因为父级通常位于堆栈上或可以存储在某个地方。

2. 是的，我们通常用单例实例来表示这些（object) 的特征：

   case object EmptyNode extends Tree
   

3. 有很多算法，广度优先搜索和深度优先搜索是最常见的。实施它们是一个很好的练习。但在 Scala 方面有一点帮助，我们通常在left and 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 https://github.com/julien-truffaut/Monocle.

看起来你刚刚开始编程或者是 Scala 新手，所以我建议使用var-s 代替vals:

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

另外如果你的特质被封印了（sealed trait Tree）那么编译器会告诉您是否没有处理模式匹配中的子类型之一。

EDIT:

根据评论开始处理：

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