CODEWITHSUNDEEP
scalab-treeinorder
Alonzo Robbe
Alonzo Robbe

Reputation: 475

In order traversal for this BTree implementation?

New learner in scala. I have these base classes for all Nodes and BTree 

abstract sealed class Node[T](implicit val ord : Ordering[T])

abstract sealed class BTree[T](implicit ord : Ordering[T])
extends Node[T] {
def size : Int
def depth : Int

And heres the base case clases

object BTree {
//empty node
final case class EmptyNode[T]()(implicit ord : Ordering[T])
  extends BTree[T] {
val size : Int = 0
val depth : Int = 0
}
//node with 1 child
final case class OneNode[T](t : BTree[T])(implicit ord : Ordering[T])
  extends Node[T] {
val size : Int = t.size
val depth : Int = t.depth + 1
}
//node with 2 children
final case class TwoNode[T](t1 : BTree[T], u1 : T, t2 : BTree[T])
                      (implicit ord : Ordering[T]) extends BTree[T] {
val size : Int = t1.size + t2.size + 1
val depth : Int = max(t1.depth, t2.depth) + 1
}

And they continue the pattern for ThreeNode and FourNode

Now in the BTree class, I have to implement an In Order function, which returns a list of the entries sorted. 

// Return List of values sorted alphabetically/smallest to largest
def inOrder() : List[T] =

Can anyone help in how to implement this? Im thinking inside the inOrder function, I have another function that is recursively called. But I dont know what to do with the List. Do I append to it before every recursive call?

Any help appreciated

Upvotes: 0

Views: 782

Answers (2)

Dima
Dima

Reputation: 40500

I don't quite understand the intent of your structures. I would expect a B-Tree node to look something like this: 

case class Node[T](smaller: Seq[Node[T]] = Nil, data: Seq[([T], Seq[Node[T]])] = Nil) {
  def inOrder: Seq[T] = smaller.flatMap(_.inOrder) ++ 
    data.flatMap { case (value, children) => 
      children.flatMap(_.inOrder) :+ value
    } 
}

This assumes that "children" are always "to the right" from the corresponding data (thus the need for smaller to keep the subtree that is to the left of everything else in the page.

Upvotes: 0

Tim
Tim

Reputation: 27356

Trying to sort the values as you read them from an unsorted tree is going to be unnecessarily complicated.

So you have two options:

1) Read all the values from the tree into a List and then sort the List

2) Keep the tree sorted as you build it so that for each node, all the values in the left branch are < the node value and all the values in the right branch are >= the node value. You can then get a sorted list by traversing the tree left-to-right in depth-first order. In this case you would never use ThreeNode or FourNode which (as I pointed out in a earlier answer) make things much more complicated.

This is the classic way to sort data using a Binary Tree.

Upvotes: 1

Related Questions