9

是否可以在案例类中实现双向树。这似乎应该很容易，但我被难住了

case class Node(name:String, parent:Option[Node], children:List[Node])

我想添加一个孩子（并获得一个新的根）——比如

def addChild(n:String):Node = {
  Node(name, parent, Node(n, Some(this), Nil)::children)
}

但这不起作用，因为孩子中的“父母”将不再引用将孩子列为孩子的节点。这对于不可变列表和案例类是否可行？

根据下面给出的答案

case class Node(name: String, parent: () => Option[Node], children: List[Node]) {
  def makeChild(name: String) = {
    lazy val newParent:Node = Node(this.name, this.parent, kid :: this.children)
    lazy val kid:Node = Node(name, () => Some(newParent), Nil)
    newParent
  }
}
4

2 回答 2

9

我最近在 Twitter 上向@jamesiry 提出了同样的问题 :-)。

他的回答：

sealed abstract class Tree[T]
case class Node[T](left : Tree[T], right : Tree[T]) extends Tree[T]
case class Leaf[T](value : T, parent : () => Tree[T]) extends Tree[T]

def make = {
   lazy val root = Node(left, right)
   lazy val left : Leaf[Int] = Leaf(1, () => root)
   lazy val right : Leaf[Int] = Leaf(2, () => root)
   root
}
于 2010-09-16T20:40:10.060 回答
0

请注意：考虑案例类是否是您表示树的好选择。

由于案例类是值类型，因此返回父级的唯一方法是返回父级的副本，包括完整子树的副本。然后，例如，如果您枚举它的孩子，您将再次获得完整子树的副本。

如果你想在树中做一些替换，例如在更深层次上替换一个节点，唯一的方法就是复制完整的树并丢弃旧树。

这一切看起来有点笨拙，但例如lift-json使用案例类来表示 JSON AST，所以它可能不是那么大的问题。不确定复制时 Scala 在引用共享方面的表现如何。也许有人可以发表评论？

如果您确实想使用案例类，那么上面带有惰性评估的答案是正确的。

于 2012-07-31T16:38:06.333 回答