Ausgabe
Ich lerne Scala und das Buch, das ich benutze, enthält eine Übung, die mich auffordert, einige Funktionen in einer Baumstruktur zu definieren.
Der Baum ist definiert als:
sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
Eine der Übungen besteht darin, die Anzahl der Knoten im Baum zu zählen. Ich habe die Funktion geschrieben, aber ich kann nicht überprüfen, ob sie funktioniert, weil ich kein Beispiel für einen Baum habe.
Wie kann ich einen kleinen Baum generieren, mit dem ich meinen Code testen kann?
Es ist wahrscheinlich möglich, dem Baum jeweils ein Element hinzuzufügen, aber es scheint eine Menge Arbeit zu sein.
Lösung
Nur so etwas
val tree = Branch(
Branch(
Leaf(12),
Branch(
Leaf(3),
Leaf(4))),
Leaf(8))
Das sollte der Baum sein
* / \ * 8 / \ 12 * / \ 3 4
Sie können das in einem größeren Baum wiederverwenden. Der Punkt ist, dass Sie von unten nach oben aufbauen, Sie können nicht etwas unten, das erfordert, dass Sie einen neuen Baum von Grund auf neu erstellen
val biggerTree = Branch(Branch(something, tree), stillSomethingElse)
Ergänzend zur Antwort von @dhg eine Variante, die einen Baum mit einer bestimmten Anzahl von Zweigen generiert (Hinweis: Es gibt immer ein Blatt mehr als Zweige, daher ist die Gesamtzahl der Zweige + Blätter immer ungerade). Das sollte das Testen einfach machen
def randomTree(branchCount: Int): Tree[Int] =
if(branchCount == 0) Leaf(0) // whatever, you can put a random here
else {
val branchCountAtLeft = util.Random.nextInt(branchCount)
// between 0 and branchCount - 1
val branchCountAtRight = branchCount - 1 - branchCountAtLeft
Branch(randomTree(branchCountAtLeft), randomTree(branchCountAtRight))
}
Beantwortet von – Didier Dupont
Antwort geprüft von – Marilyn (FixError Volunteer)