如何创建自己的MySet（）特征并通过Vector将其应用于元素？

Question

[我看了Scala中的TreeSet()实现，并尝试编写自己的MyTreeSet()，它可以使用Tree类的各种实现（例如Binary，AVL等）。为此，我尝试使用特征MyTreeSet。我要声明的主要内容是变量mts，它将被识别为类型MyTreeSet的值：

scala> val mts = MyTreeSet(2,3,5,1,0,9)

ts: MyTreeSet[Int] = MyTreeSet(0, 1, 2, 3, 5, 9)

或了解我的问题的另一种方法-查看屏幕截图：

[在这里，您可以看到我创建的是ts，即TreeSet，在该位置您看到ts被定义为IDE中的TreeSet值。您可以看到ts的元素看起来像列表元素。

我需要在MyTreeSet中使用-使IDE中的元素看起来像TreeSet中的元素

为了进行排序，我在自己的类中使用二叉树：根据序列2,3,5,1,0,9生成有序树。但是对我来说主要的问题是写方法，它可以将Tree(Node(3,Node(2,..),Node(3,..)))转换为Scala主库中的TreeSet中的序列。

现在我正在使用这样的代码进行操作：

trait MyTreeSet {

  //Some staff...

  def + (x: Int): SimpleTreeSet
  def foreach (f: Int => Unit): Unit
  def makeFromSeq (xs: Seq[Int]): Tree
  def toSet (root: Tree): SimpleTreeSet
}

object MyTreeSet{

  //Some staff...

  def apply (xs: Int*): MyTreeSet = {
    val tree = new Tree ().makeFromSeq(xs)

    // problem in that method
    val seq = tree.toMySet(tree)
    seq
  }

class Tree extends MyTreeSet {

  //Some staff...

  def makeFromSeq(xs: Seq[Int]): Tree = {
    xs.headOption match {
      case Some(x) =>
      var root = Node(x, Empty, Empty).asInstanceOf[Tree]
      for (next <- xs.tail) root = root + next
      root
      case None => new Tree()
    }
  }

  def toMySet(root: Tree): MyTreeSet = {
    var seq:Seq[Int] = Seq()
    root.foreach((x)=> seq = seq.prepended(x))

    // What do here?
    // How Seq[Int] transform to `MyTreeSet[Int] = MyTreeSet(0, 1, 2, 3, 5, 9)`?
    // ???
  }

}

case object Empty extends Tree
case class Node(value: Int, left: Tree, right: Tree) extends Tree

我需要知道的内容以及我需要在代码中写的内容？

Answer 1

这是一个如何将序列转换为二进制搜索树，以及如何通过有序遍历将BST转换为序列的玩具示例。请注意，此答案仅是为了（可能）给出一些想法，并且是[[not Scala集合如何解决问题的方法。根据Scala集合提供通用而有效的解决方案可能是一个太宽泛的问题。

要理解的关键是树是

递归地定义的结构，因此应该很好地进行处理，递归地。

sealed trait Tree {
  def toSeq: Seq[Int]
}
case object Empty extends Tree {
  def toSeq: Seq[Int] = Nil
  override def toString: String = "Tree()"
}
case class Node(value: Int, left: Tree = Empty, right: Tree = Empty) extends Tree {
  def toSeq: Seq[Int] = toSeq(this)
  private def toSeq(tree: Tree): Seq[Int] = {
    tree match {
      case Empty => Nil
      case Node(value, left, right) => toSeq(left) ++ Seq(value) ++ toSeq(right)
    }
  }
  override def toString: String = toSeq(this).mkString("Tree(", ", ", ")")
}

object Tree {
  def insert(a: Tree, b: Tree): Tree = (a, b) match {
    case (Node(av, al, ar), Node(bv, _, _)) => if (bv > av) Node(av, al, insert(ar, b)) else Node(av, insert(al, b), ar)
    case _ => b
  }

  def apply(xs: Int*): Tree = {
    if (xs.isEmpty) Empty
    else if (xs.size == 1) Node(xs.head)
    else {
      val nodes: Seq[Tree] = xs.map(v => Node(v))
      nodes.tail.foldLeft(nodes.head) { case (acc: Node, next: Node) => insert(acc, next) }
    }
  }
}

给出
Tree(2,3,5,1,0,9)         // res3: Tree = Tree(0, 1, 2, 3, 5, 9)
Tree(2,3,5,1,0,9).toSeq   // res4: Seq[Int] = List(0, 1, 2, 3, 5, 9)

现在，下一步可能要推广到Tree[A]，为此您将需要比较可能隐式召集的T的一般方法。也许在那之后，提供了另一种树的通用实现，然后才开始考虑抽象掉这两种树的实现细节。