Remove Node von Binary Tree - Zurück Set von Bäumen Zurück

Question

Ich war irgendwie nur um dieses Problem für Spaß und ein Schlag eine Straßensperre damit und konnte nicht viele Informationen online finden. Ich möchte einen Algorithmus in Scala erstellen, in dem, wenn Sie einen Knoten mit einem bestimmten Wert aus einem Baum entfernen, er die Menge der Bäume, die er erstellt, zurückgibt. Zum Beispiel der Baum

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

Wenn wir entfernen 4 dann wäre es Bäume zurück, wie folgt:

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

Was habe ich so weit ist wie folgt:

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) 
} 

Ich bin relativ neuer zu Scala, jede Hilfe wäre willkommen.

Prost

Answer 1

Hier ist eine Antwort, die wahrscheinlich kurz und bündig geschrieben werden kann, aber ich hoffe, es ist etwas klar den Algorithmus zum Ausdruck bringt:

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) 
    } 
}