Union of Trees in Scala

问题:

I am trying to take union of two trees using the union method. For the purposes of checking the code I added the print statements inside the method. But the print of acc shows that it is not changing with the recrsion. I do not understand why is this happening. Can someone please explain.

class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {

    def union(that: TweetSet): TweetSet =
    {
      def unionRec(set:TweetSet,acc:TweetSet): TweetSet =
      {
        if (set.isEmpty)
          return acc
        else
        {
          acc.foreach(x=> println(x))
          println("####################")
          set.foreach(x=>println(x))
          println("####################")
          unionRec(set.takeRight,unionRec(set.takeLeft,acc.incl(set.rootTweet)))
          return acc
        }
      }
      unionRec(this,that)
    }

    def takeLeft: TweetSet =
    {
      return left
    }

    def takeRight: TweetSet =
    {
      return right
    }
    def rootTweet: Tweet =
    {
      return 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
  }
  def isEmpty: Boolean = false
  def foreach(f: Tweet => Unit): Unit = {
    f(elem)
    left.foreach(f)
    right.foreach(f)
  }
}
class Empty extends TweetSet {
 def isEmpty: Boolean = true
}

回答1:

You are doing the exact same mistake as you did in your last question (Adding an element to a tree in scala). You are throwing away the result of your unionRec-call. Remember that TweetSet is immutable, so acc will never change!

These two lines:

unionRec(set.takeRight,unionRec(set.takeLeft,acc.incl(set.rootTweet)))
return acc

Has to be changed to this:

return unionRec(set.takeRight,unionRec(set.takeLeft,acc.incl(set.rootTweet)))