我正在尝试在 Scala 中制作一个非常简单的二叉树,用于数据存储和遍历。
现在我有:
trait Tree
case class Node(left: Tree, value: String, right: Tree) extends Tree
我的问题:
我怎样才能包含一个指向父级的指针?
我可以以任何方式将左指针和右指针设置为空吗?或者根节点的父指针?
我怎样才能真正遍历这棵树?
更新节点的值容易吗?
不适用于不可变的案例类。这是一种循环依赖:您需要父级来创建子级,但也需要子级来创建父级。另一方面,大多数树遍历算法实际上并不需要父级,因为父级通常位于堆栈上或可以存储在某个地方。
-
是的,我们通常用单例实例来表示这些(object
) 的特征:
case object EmptyNode extends Tree
-
有很多算法,广度优先搜索和深度优先搜索是最常见的。实施它们是一个很好的练习。但在 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
}
不,您的猜测是正确的,在树中使用不可变的案例类很难更新,因为如果您更新叶节点,则必须重新创建其上方的所有内容。有所谓的镜头和镜头库可以帮助您解决此问题,尽管它们可能更先进一些。 Scala 中流行的一种是Monocle https://github.com/julien-truffaut/Monocle.
看起来你刚刚开始编程或者是 Scala 新手,所以我建议使用var
-s 代替val
s:
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
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)