你好。类中有一些递归函数的代码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
}
}
合并集合时,有两种情况:合并空集合(将给出第一个集合)和非空集合。
要解释加入非空集合的过程,请考虑 incl(x: Tweet) 方法。每次调用它都会根据参数递归地重建左子树或右子树。
union(that: TweetSet) 方法递归地将当前树的一棵子树与那棵树合并,然后另一棵子树也与结果合并,最后将根添加到结果树中。
为了举例说明,您可以添加可视化结果的方法。
这是测试代码本身: