3

我正在创建一些基本的抽象数据类型和算法来复习我的 CS 基础知识，并在此过程中学习 Scala。我的 BinarySearchTree 数据类型遇到了麻烦，这是一个更抽象的 BinaryTree 的实现：

abstract class BinaryTree[T](stored_value: T) { 
  var contents = stored_value
  var l: this.type = _
  var r: this.type = _
  ...
}

class BinarySearchTree[T <: Ordered[T]](stored_value: T) extends BinaryTree(stored_value) {  
  def insert(newval: T) {
    if (newval <= contents) {
      if (l == null) {
        throw new NotDefinedError("Still trying to work around type erasure.")
      } else {
        l.insert(newval)
      }
    } else {
      if (r == null) {
        throw new NotDefinedError("Still trying to work around type erasure.")
      } else {
        r.insert(newval)
      }
    }
  }

在抛出 NotDefinedErrors 的块中，我尝试了一些方法，例如l = new this.type(newval)，替换this.type以及BinarySearchTree[T]我能想到的任何其他方法。根据我尝试表达该类型的方式，我会得到类似的东西：

class type required but BinarySearchTree.this.type found

或者：

type mismatch;  found   : trees.BinarySearchTree[T]  required: BinarySearchTree.this.type

我是否需要在 BinarySearchTree 的定义中用不同类型覆盖 l 和 r？或者只是在我为它们附加新值时调用不同类型的构造函数？还是其他选择？

4

2 回答 2

7

我同意 @dhg 的建议，即探索不可变树数据结构作为当前方向的替代方案。但是，如果您确实需要可变树，请继续阅读...

你的直接问题是，this.type在定义中BinaryTree[T]并不意味着你认为它意味着什么。它实际上是封闭实例的单例类型，即。居住的类型，仅此this而已。这是一个说明这一点的例子，

scala> class Foo { def self : this.type = this /* OK */ }
defined class Foo

scala> class Bar { def self : this.type = new Bar /* Does not compile */ }
<console>:7: error: type mismatch;
 found   : Bar
 required: Bar.this.type
       class Bar { def self : this.type = new Bar /* Does not compile */ }
                                          ^

这显然是一种比你真正想要的更具体的类型。

要解决这个问题，一种选择是削弱l和rto的类型BinaryTree[T]，就像@dhg 的回答一样。但是，我认为您在使用时最初this.type的目的是让树节点自类型化，并在子类中改进为 BinarySearchTree[T]。您可以像在 Java 中使用递归类型绑定一样执行此操作，也可以使用抽象类型成员执行此操作，例如，

abstract class BinaryTree[T] {
  type Self <: BinaryTree[T]
  var contents : T
  var l: Self = _
  var r: Self = _
}

class BinarySearchTree[T <: Ordered[T]](stored_value : T) extends BinaryTree[T] {
  type Self = BinarySearchTree[T]
    var contents = stored_value
    def insert(newval: T) {
      if (newval <= contents) {
        if (l == null) {
          new BinarySearchTree(newval)
        } else {
          l.insert(newval)
        }
      } else {
        if (r == null) {
          new BinarySearchTree(newval)
        } else {
          r.insert(newval)
        }
      }
  }
}
于 2012-05-06T09:16:31.577 回答
6

我会这样定义它：

class BinaryTree[T](
  val item: T,
  val left: Option[BinaryTree[T]] = None,
  val right: Option[BinaryTree[T]] = None) {

  override def toString() = "Tree(%s,%s,%s)".format(item,left,right)
}

class BinarySearchTree[T: Ordering](
  override val item: T,
  override val left: Option[BinarySearchTree[T]] = None,
  override val right: Option[BinarySearchTree[T]] = None) extends BinaryTree[T](item, left, right) {

  def insert(newval: T): BinarySearchTree[T] = {
    val (newLeft, newRight) =
      if (implicitly[Ordering[T]].lteq(newval, item))
        (insertSubtree(newval, left), right)
      else
        (left, insertSubtree(newval, right))
    new BinarySearchTree(item, newLeft, newRight)
  }

  private def insertSubtree(newval: T, subtree: Option[BinarySearchTree[T]]) =
    Option(subtree
      .map(_.insert(newval))
      .getOrElse(new BinarySearchTree(newval, None, None)))
}

有一些基本的东西我已经改变为更像 Scala：

  • val通过使用所有字段使结构不可变。返回insert一个新的，修改过的树。尽可能多地保留旧的（不可变的）树以避免浪费内存。
  • null通过使用来避免使用Option。因此，left和right子树是Option[Binary(Search)Tree[T]]，明确表示它们可能存在或不存在。
  • 在子树上使用，map因为它是一个Option. 这段代码insertSubtree基本上是说“如果子树存在，则插入其中。否则，获取一棵新树。”

以下是它的工作原理：

scala> var t = new BinarySearchTree(5, None, None)
t: BinarySearchTree[Int] = Tree(5,None,None)

scala> t = t.insert(3)
t: BinarySearchTree[Int] = Tree(5,Some(Tree(3,None,None)),None)

scala> t = t.insert(4)
t: BinarySearchTree[Int] = Tree(5,Some(Tree(3,None,Some(Tree(4,None,None)))),None)

scala> t = t.insert(7)
t: BinarySearchTree[Int] = Tree(5,Some(Tree(3,None,Some(Tree(4,None,None)))),Some(Tree(7,None,None)))
于 2012-05-06T01:52:57.707 回答