主页 / 问题 / 591896
Accepted
Vova Polischuck
Asked:2020-11-17 03:18:57 +0000 UTC2020-11-17 03:18:57 +0000 UTC

我无法理解联合函数的 Scala 实现

  • 772

你好。类中有一些递归函数的代码union，NonEmpty将两个二叉搜索树合二为一。如果有人不难详细解释（最好是用例子）它是如何工作的，那就太好了。为了更好地理解，我将添加一个类，其中有一个我感兴趣的函数。

abstract class TweetSet {
  def union(that: TweetSet): TweetSet
  def incl(tweet: Tweet): TweetSet
}

class Empty extends TweetSet {
  override def union(that: TweetSet): TweetSet = that
  def incl(tweet: Tweet): TweetSet = new NonEmpty(tweet, new Empty, new Empty)
}

class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {
  override def union(that: TweetSet): TweetSet =
    (left union (right union that)).incl(elem)

  def incl(x: Tweet): TweetSet = {
    if (x.text < elem.text) new NonEmpty(elem, left.incl(x), right)
    else if (elem.text < x.text) new NonEmpty(elem, left, right.incl(x))
    else this
  }
}
scala

1 个回答

  1. Best Answer

    合并集合时，有两种情况：合并空集合（将给出第一个集合）和非空集合。

    要解释加入非空集合的过程，请考虑 incl(x: Tweet) 方法。每次调用它都会根据参数递归地重建左子树或右子树。

    union(that: TweetSet) 方法递归地将当前树的一棵子树与那棵树合并，然后另一棵子树也与结果合并，最后将根添加到结果树中。

    为了举例说明，您可以添加可视化结果的方法。

    class Tweet(val text: String)
class Empty extends TweetSet {
  ....
  override def toString = "."
}
class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {
  override def union(that: TweetSet): TweetSet = {
    val res = (left union (right union that)).incl(elem)
    println(s"union ${this} and ${that} is " + res)
    res
  }
  ...
  override def toString = "{" + left + "," + right + "}" 
}

    这是测试代码本身：

    object ts {
val emp = new Empty                       //> emp  : Empty = .
def generTweet = new Tweet(scala.util.Random.nextString(10))
                                              //> generTweet: => Tweet
def generTweets(n: Int) = for (i <- 0 until n) yield generTweet
                                              //> generTweets: (n: Int)scala.collection.immutable.IndexedSeq[Tweet]
def generTweetSet(n: Int, acc: TweetSet = new Empty): TweetSet =
    if (n == 0) acc
    else generTweetSet(n-1, acc.incl(generTweet))
                                              //> generTweetSet: (n: Int, acc: TweetSet)TweetSet

val nonEmpty1 = generTweetSet(1)          //> nonEmpty1  : TweetSet = {.,.}
val nonEmpty2 = generTweetSet(1)          //> nonEmpty2  : TweetSet = {.,.}
nonEmpty1 union nonEmpty2                 //> union {.,.} and {.,.} is {.,{.,.}}
                                              //| res0: TweetSet = {.,{.,.}}

val nonEmpty3 = generTweetSet(2)          //> nonEmpty3  : TweetSet = {{.,.},.}
nonEmpty1 union nonEmpty3                 //> union {.,.} and {{.,.},.} is {{.,.},{.,.}}
                                              //| res1: TweetSet = {{.,.},{.,.}}
nonEmpty3 union nonEmpty1                       //> union {.,.} and {.,.} is {{.,.},.}
                                              //| union {{.,.},.} and {.,.} is {{.,{.,.}},.}
                                              //| res2: TweetSet = {{.,{.,.}},.}
val nonEmpty4 = generTweetSet(2)                //> nonEmpty4  : TweetSet = {.,{.,.}}
nonEmpty3 union nonEmpty4                       //> union {.,.} and {.,{.,.}} is {.,{{.,.},.}}
                                              //| union {{.,.},.} and {.,{.,.}} is {.,{{.,{.,.}},.}}
                                              //| res3: TweetSet = {.,{{.,{.,.}},.}}
}
    • 2

相关问题