Удалить узел из двоичного дерева - Возвращение Set of Trees Назад

Question

Я был просто привязан к этой проблеме для удовольствия и своего рода ударил по дорожному блоку с ней и не мог найти много информации об этом в Интернете. Я хочу создать алгоритм в Scala, где, когда вы удаляете узел некоторого значения из дерева, он будет возвращать набор деревьев, которые он создает. Например, дерево

1 
/\ 
3 4 
/\ /\ 
4 5 6 2 

Если удалить 4, то было бы вернуть деревья следующим образом:

[ 1  , 6 , 2 ] 
[/   ] 
[ 3    ] 
[ \    ] 
[ 5    ] 

То, что я до сих пор выглядит следующим образом:

object TreeStructure { 

    trait Tree { 
    def isEmpty(): Boolean 

    def equals(other: Tree): Boolean 

    def diff(other: Tree): Tree 

    def remove(value: Int): List[Tree] 

    def removeNode(value: Int): Tree 
    } 

    case class Node(var left: Tree, var right: Tree, value: Int) extends Tree { 
    override def isEmpty = false; 

    override def equals(other: Tree): Boolean = other match { 
     case x: Node => this.value == x.value && this.left.equals(x.left) && this.right.equals(x.right) 
     case _ => false 
    } 

    override def diff(other: Tree): Tree = { 
     if (this.equals(other)) new EmptyNode() 
     else new Node(this.left.diff(other), this.right.diff(other), this.value) 
    } 

    override def removeNode(value: Int): Tree = { 
     if (this.value == value) { 
     EmptyNode() 
     } else { 
     new Node(this.left.removeNode(value),this.right.removeNode(value), this.value) 
     } 
    } 

    override def remove(value: Int): List[Tree] = { 
     (List(this.removeNode(value)) ++ left.remove(value) ++ right.remove(value)) 
    } 
    } 

    case class Leaf(var value: Int) extends Tree { 
    override def isEmpty(): Boolean = false 

    override def equals(other: Tree): Boolean = other match { 
     case y: Leaf => this.value == y.value 
     case _ => false 
    } 

    override def diff(other: Tree): Tree = { 
     if (this.equals(other)) EmptyNode(); 
     else this 
    } 

    override def remove(value: Int): List[Tree] = { 
     if(this.value == value) Nil 
     else List(this) 
    } 

    override def removeNode(value:Int): Tree = { 
     if(this.value == value) EmptyNode() 
     else this 
    } 
    } 

    case class EmptyNode() extends Tree { 
    override def isEmpty(): Boolean = true 

    override def equals(other: Tree): Boolean = other match { 
     case x: EmptyNode => true 
     case _ => false 
    } 

    override def diff(other: Tree): Tree = new EmptyNode() 

    override def remove(value: Int): List[Tree] = Nil 

    override def removeNode(value:Int): Tree = new EmptyNode() 
    } 


    val t1 = new Node(new Leaf(15), new Leaf(13), 0) 
    val t2 = new Node(new Leaf(15), new Leaf(13), 0) 
    val t3 = new Node(new Node(new Leaf(3), new Leaf(13), 0), new Leaf(25), 30) 

    val t4 = new Leaf(13) 
    val boo = t1.equals(t2) 
    t3.diff(t1) 
    t3.remove(30) 
} 

Я относительно новее к Scala, любая помощь будет оценена по достоинству.

Приветствия

Answer 1

Вот ответ, который, вероятно, можно было бы написать более лаконично, но я надеюсь, что он несколько четко выражает алгоритм:

case class N[T](value: T, children: List[N[T]] = Nil) { 
    def remove(t: T) = { 
    val r = _remove(t) 
    r._1.toList ++ r._2 
    } 

    def _remove(t: T): (Option[N[T]], List[N[T]]) = 
    if(value == t) (None, children.map(_._remove(t)).flatMap{ case (c, o) => c.toList ++ o}) 
    else { 
     val results = children.map(_._remove(t)) 
     val me = this.copy(children = results.flatMap(_._1)) 
     val others = results.flatMap(_._2) 
     (Some(me), others) 
    } 
}