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

Question

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

现在我有：

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

我的问题：

我怎样才能同时包含指向父对象的指针？
我能以任何方式让左右指向 null 吗？还是根节点的父指针？
如何才能真正遍历树？
更新节点的值容易吗？

Answer 1

不可变大小写类。这是一个循环依赖：您需要父对象来创建子对象，但您也需要子对象来创建父对象。另一方面，大多数树遍历算法并不真正需要父级，因为父级通常在堆栈上或可以存储在某处。
是的，我们通常用特征的单例实例（object）表示这些：
```
case object EmptyNode extends Tree
```
有很多算法，广度优先搜索和深度优先搜索是最常见的。实施它们是一个很好的练习。但是在 Scala 方面有点帮助，我们通常在 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
}
```
不，您的猜测是正确的，在树中使用不可变大小写类很难更新，因为如果更新叶节点，则必须重新创建其上方的所有内容。有所谓的 Lenses 和 Lens 库可以帮助您解决这个问题，尽管它们可能更高级一些。 Scala 中流行的一种是 Monocle.

看来您是刚刚开始编程或刚接触 Scala，所以我建议您使用 var-s 而不是 vals:

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

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

Making a very basic binary tree in Scala

tree

binary-tree

scala