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

Question

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

现在我有:

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

我的问题:

1. 我怎样才能同时包含指向父对象的指针？

2. 我能以任何方式让左右指向 null 吗？还是根节点的父指针？

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

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

Answer 1

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

2. 是的，我们通常用特征的单例实例(对象)来表示这些:

   case object EmptyNode extends Tree
   

3. 有很多算法，广度优先搜索和深度优先搜索是最常见的。实现它们是一个很好的练习。但是在 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
   }
   

4. 不，您的猜测是正确的，在树中使用不可变的案例类很难更新，因为如果您更新叶节点，则必须重新创建它上面的所有内容。有所谓的 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
case class Node(var left: Tree, var value: String, var right: Tree, var parent: Tree) extends Tree
case object EmptyNode extends Tree