CODEWITHSUNDEEP
scaladata-structurestree
Donbeo
Donbeo

Reputation: 17617

generate a tree in scala

I am learning Scala and the book that I am using provides an exercise that asks me to define some functions on a tree structure.

The tree is defined as:

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]

One of the exercise is to count the number of nodes in the tree. I wrote the function but I can not check if it is working because I do not have any example of tree.

How can I generate a small tree that I can use to test my code?

It is probably possible to add one element at the time to the tree but it seems like a lot of work.

Upvotes: 7

Views: 12741

Answers (3)

GPopat
GPopat

Reputation: 475

You can also move the code of generate method written by @dgh to apply method of Tree comppanion object

package datastructures

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]

  object Tree{
    def apply(p: Double): Tree[Int] = {
      if (util.Random.nextDouble < p)
        Branch(apply(p), apply(p))
      else
        Leaf(util.Random.nextInt(100))        }
  }

and then use it like

val t = Tree(0.5)
println(t)

Upvotes: 1

dhg
dhg

Reputation: 52681

@Didier's answer is good for making your own trees by hand, but if you want to automatically generate trees, you can do so with a little recursive generator:

def generate(p: Double): Tree[Int] = {
  if (util.Random.nextDouble < p)
    Branch(generate(p), generate(p))
  else
    Leaf(0)
}

Then you just do:

val t = generate(0.5)
println(t)

and you'll get a random tree. Lowering p will make the trees tend smaller; raising it will make them tend bigger.

Clearly this will make trees with all leafs the same value. If you want random leaf values, try:

 Leaf(util.Random.nextInt(100))

Upvotes: 7

Didier Dupont
Didier Dupont

Reputation: 29528

Just something like

val tree = Branch(
             Branch(
               Leaf(12),
               Branch(
                 Leaf(3),
                 Leaf(4))),
             Leaf(8))

That should be the tree

      *
    /   \
   *     8
  /  \
 12   *
     /  \
     3   4

You can reuse that in a bigger tree. The point is that you build bottom up, you cannot at something at the bottom, that requires creating a new tree from scratch

val biggerTree = Branch(Branch(something, tree), stillSomethingElse)

In complement of @dhg's answer, a variant which generates a tree with a given number of branches (note: there are always one more leaves than there are branches, so the total number branches + leaves is always odd). That should make testing straightforward

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

Upvotes: 14

Related Questions