Lab 12

CSS 162 : Programming Methodology

 Winter 2012, Instructor Rob Nash

K-nary Trees & Binary Search Trees with Generics

Introduction

We have discussed a wide range of static (array-based) and dynamic data structures.  In this lab, we’ll take our knowledge of linked lists and extend it to build a set structure known as a Tree.  Trees are DAGS (directed acyclic graphs) that are composed of Node elements (just as in our linked lists).  Trees come in multiple flavors, but we’ll focus on K-nary trees where k==2, also known as a Binary Tree.   We’ll introduce more restrictions as we go and in turn, produce a Binary Tree with an ordering constraint, known as a Binary Search Tree.

Getting Started

Download all of the files associated with this lab, read them and then compile them.  We will build the tree pictured above by reading the morse code data from a text file, and then calling our add() function for each symbol we wish to encode in our tree.

Building the Tree from a File (TODO1)

(1) Download the sample MorseTreeSkeleton driver and read the setupTreeFromFile() function.

(2) In this function, create a Scanner that reads in each line from the morse.txt file

a. Trim each line as you go

b. Add the current line to your tree by calling the add() function (which we build below)

Adding to a Binary Tree with Ordering Constraints (TODO2)

(1) Find the add() function in the MorseTreeSkeleton driver.

a. Notice you need no root=null checks, as I’ve already made a Node for root.

(2) Inside the for loop that traverses the Morse string, locate the TODO

(3) Finish this function by walking over the tree and building new nodes where null used to be

a. Go left if the current char is a ‘.’

b. Go right if the char is a ‘-‘

Translating from Morse Code to Symbols using our Binary Tree (TODO3)

(1) Find the translate() function in the MorseTreeSkeleton driver. (aka, get())

(2) Inside the for loop that iterates over the Morse string, locate the TODO

(3) Finish this function by walking over the tree

a. Go left for a ‘.’

b. Go right for a ‘-‘

(4) Once you’ve walked the tree, current should be at the node you are looking for, so return current.data

Testing the Software

Uncomment the appropriate code in main to test your software.  If you have built your tree correctly, you will be able to translate morse code strings (such as “…”) into corresponding symbols (such as “S”) by invoking the translate function after the tree is set up.

(1) Make sure you build a tree in main

(2) If your tree is called foo, then invoke foo.setupTreeFromFile(“morse.txt”)

(3) Finally, try translating a few known symbols using the translate function

Constraints are Guarantees

Notice that in the above tree we enforce the following class invariant : dots go to the left, and dashes go to the right.  By imposing constraints on our trees in this fashion, we can build even more powerful  data structures that provide quick gets for data stored in these trees.  Searching a nonordered list requires a linear traversal – when we sort the list, can search using the Binary search and speed things up exponentially.  We’ll leverage the sorting trick here,  but in a slightly different fashion.  Let’s  add the following  rule (or class invariant) to our Tree  :  Given a node x with value y, every value in the left subtree is less than x (ie, x->left and all sub-children), and every value in the right subtree is greater than x (ie, x->right and all sub-children).  This invariant is demonstrated visually by the Binary Search Tree below.  Notice that, for a given node (say 3), all child nodes to the left of that node are less than 3 (1 here), and the child nodes to the right of that node are greater than 3 (6,4, and 7 here).

Above left is a reasonably balanced tree, but note that depending on the patterns of input, less than balanced (so-called degenerate Trees) can be built, effectively reducing the “quick” search time to a linear search!  This is demonstrated by the “tree” to the right (what does it look like?).

Making a Binary Search Tree

Let’s start by modifying your existing code; copy your morse code tree to a new java file, and change the type parameter when creating Nodes to be of type Integer.

Modifying the Tree Building Code

Change the code in the setupTreeFromFile() so that you read from a second file a set of random integers that we will use to build our BST.  Name this text file “ints.txt”, and put it next to the “morse.txt” file.

Modifying the Add Function

Note that add() only accepts one parameter, and not two pieces of data like in the morse code problem.  Modify the add function so that you traverse the tree similarly to how we did in the Morse Code example, with the following differences:

(a) Start current at the root

(b) Rather than going left if we see a dot, instead if the element to be added is less than the root, go left.

(c)  Rather than going right if we see a dash, instead if the element is greater than the root, go right. 

(d) Now that current is pointing to the left (or right child) of root, repeat steps a and b until you try to go left or right and encounter a null

1. You tried to go left but its null; make a new node with your integer and attach it to current->left

2. You tried to go right but its null; make a new node with your integer and attach it to current->right

Modifying the Get Function (aka, Translate)

Find the translate function and rename it get(targetInt).  This function will walk the tree looking for the node with the same value passed to get, and will return the node if found, null otherwise.  Follow the invariants above to start at the root and walk the tree.  Note that if you go to walk left or right and no node is there (ie, null), then your tree doesn’t have the item and you should return null.