0
所以基本上我正在使用二叉树实现整数集合。Integer Set的交集函数
这里的抽象类INTSET
abstract class IntSet {
def incl(x: Int): IntSet
def contains(x: Int): Boolean
def union(other: IntSet): IntSet
def intersect(other: IntSet) : IntSet
}
非空设置:
/********************NonEmpty************************************/
class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
def contains(x: Int): Boolean =
if (x < elem) left contains x
else if (x > elem) right contains x
else true
def incl(x: Int): IntSet =
if (x < elem) new NonEmpty(elem, left incl x, right)
else if (x > elem) new NonEmpty(elem, left, right incl x)
else this
override def toString = "{" + left + elem + right + "}"
def union(other: IntSet): IntSet= {
((left union right) union other) incl elem
}
}
而且EmptySet:
/********************Empty************************************/
class Empty extends IntSet {
def contains(x: Int): Boolean = false
def incl(x: Int): IntSet = new NonEmpty(x, new Empty, new Empty)
def union(other: IntSet): IntSet = other
override def toString = "."
}
正如你所看到的,两套工会已经实施。 我的问题是,我将如何去执行相交功能?
联盟工作正常,你可以从输出中看到:
val t1= new NonEmpty(1, new NonEmpty(2, new Empty(), new Empty()), new NonEmpty(3, new Empty(), new Empty()))
//> t1 : mid.NonEmpty = {{.2.}1{.3.}}
val t2 =new NonEmpty(5, new NonEmpty(6, new Empty(), new Empty()), new NonEmpty(7, new Empty(), new Empty()))
//> t2 : mid.NonEmpty = {{.6.}5{.7.}}
//t1 union t2 //> res0: mid.IntSet = {{{{.1.}2{.3.}}6.}5{.7.}}
为什么不使用Scala标准库中的'TreeSet'?它应该专门用于'Int'。 – Madoc 2014-11-04 11:28:42