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

Question

我试图在Scala中创建一个非常简单的二叉树，用于数据存储和遍历。

现在我有：

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

我的问题：

>

我怎样才能包含指向家长的指针？

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

我怎样才能真正穿越这棵树？

更新节点的值容易吗？

Answer 1

>

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

是的，我们通常用一个trait的单例实例（对象）来表示：

case object EmptyNode extends Tree

有很多算法，广度优先搜索和深度优先搜索是最常见的。这是一个很好的实践。但在Scala方面，我们通常会在左侧和右侧进行模式匹配，以查看下一步需要做什么：

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
}

不，您的猜测是正确的，在树中使用不可变大小写类很难更新，因为如果您更新叶节点，那么您必须重新创建它上面的所有内容。有所谓的镜头和镜头库可以帮助您解决这个问题，尽管它们可能更高级一点。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