CSC212 Homework 6 2014

--D. Thiebaut (talk) 12:17, 30 October 2014 (EDT)

---

This assignment is due Friday Nov 7, 2014, at 11:55 p.m.

Problem #1

• Add a new method to your BST program that will output the DOT version of the tree it contains. Refer to Lab 10 for how we generate the DOT version of a tree.
• Your function must be called generateDot()
• It must be public so that my test program can access and use it
• It doesn't need any parameters passed to it.
• It outputs your name as a label.
• Here is an example of the type of output it will generate for a given tree, for User Mickey Mouse:

digraph T {
label = "Mickey Mouse";
8 -> 3;
8 -> 10;
3 -> 1;
3 -> 6;
6 -> 4;
6 -> 7;
10 -> 14;
14 -> 13;
}

Submission to Moodle

• Submit IntBST.java to Moodle, Problem 1 of Homework 6.

Problem #2

• The tree generated in the first problem is not balanced well when the number of children is 1.
• Modify your generateDot() function so that it outputs "invisible nodes" for null children.
• Here is an example of the type of output to expect from your function for the same tree:

digraph T {
label = "Mickey Mouse";
8 -> 3;
8 -> 10;
3 -> 1;
3 -> 6;
null1left [label="",width=.1,style=invis];
1 -> null1left [style=invis];
null1right [label="",width=.1,style=invis];
1 -> null1right [style=invis];
6 -> 4;
6 -> 7;
null4left [label="",width=.1,style=invis];
4 -> null4left [style=invis];
null4right [label="",width=.1,style=invis];
4 -> null4right [style=invis];
null7left [label="",width=.1,style=invis];
7 -> null7left [style=invis];
null7right [label="",width=.1,style=invis];
7 -> null7right [style=invis];
null10left [label="",width=.1,style=invis];
10 -> null10left [style=invis];
10 -> 14;
14 -> 13;
null14right [label="",width=.1,style=invis];
14 -> null14right [style=invis];
null13left [label="",width=.1,style=invis];
13 -> null13left [style=invis];
null13right [label="",width=.1,style=invis];
13 -> null13right [style=invis];
}

Submission

• Submit your IntBST.java program to Moodle, Problem 2 of Homework 6 section.

Problem 3

• Create a new class called StringBST.java. This will be the program you submit.
• Instead of keeping track of a tree of ints, StringBST.java will maintain a binary-search tree of Strings. You may want to copy the contents of IntBST.java into StringBST.java and modify all the operations on the keys to be string operations.

• Note 1: when you compare two strings for equality, you must use the .equals() method.
• Note 2: when you compare two strings for whether one is less than the other, use the String .compareTo() method.

with ints	with Strings
int key, el; ... if ( el == key ){ ... }	String key, el; ... if ( el.equals( key ) ){ ... }
int key, el; ... if ( el < key ){ ... }	String key, el; ... if ( el.compareTo( key ) < 0 ){ ... }

• Your StringBST.java code must support several public methods that will be used by the test program:

• inOrderVisit(): will print a list of all the words contained in the tree, one per line.
• length(): will return an int that is the number of unique words in the tree.
• insertWithDuplicates(): this function works just like the insert() method, but it allows one to insert an element that is already in the tree. You have to figure out how to keep track of duplicate keys. We talked briefly about this in class, but because all we are interested in is the number of duplicated strings (see findMostFrequent() method below), there may be a much simpler solution than what we discussed in class...
• findMostFrequent(): will return the list of word(s) that was/were inserted by insertDuplicate() most often.

Submission

Submit your StringBST.java tree to Moodle, in the Homework 6 Problem 3 section.

Example Test Program

• Here is a test program called Hw6_3Test.java you can use to test your StringBST.java code with. All you need to do is create a new class with Eclipse, in the same 212 project where StringBST.java resides, and the Hw6_3Test program will automatically have access to your StringBST.java.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;


public class Hw6_3Test {

	public static void main(String[] args) {
		// use a string with a good number of words...
		String text = "ULYSSES\n"
				   +"by James Joyce\n"
				   +"-- I --\n"
				   +"Stately, plump Buck Mulligan came from the stairhead, bearing a bowl of\n"
				   +"lather on which a mirror and a razor lay crossed. A yellow dressinggown,\n"
				   +"ungirdled, was sustained gently behind him on the mild morning air. He\n"
				   +"held the bowl aloft and intoned:\n"
				   +"--_Introibo ad altare Dei_.\n"
				   +"Halted, he peered down the dark winding stairs and called out coarsely:\n"
				   +"--Come up, Kinch! Come up, you fearful jesuit!\n"
				   +"Solemnly he came forward and mounted the round gunrest. He faced about\n"
				   +"and blessed gravely thrice the tower, the surrounding land and the\n"
				   +"awaking mountains. Then, catching sight of Stephen Dedalus, he bent\n"
				   +"towards him and made rapid crosses in the air, gurgling in his throat\n"
				   +"and shaking his head. Stephen Dedalus, displeased and sleepy, leaned\n"
				   +"his arms on the top of the staircase and looked coldly at the shaking\n"
				   +"gurgling face that blessed him, equine in its length, and at the light\n"
				   +"untonsured hair, grained and hued like pale oak.\n"
				   +"Buck Mulligan peeped an instant under the mirror and then covered the\n"
				   +"bowl smartly.\n"
				   +"--Back to barracks! he said sternly.\n"
				   +"He added in a preacher's tone:\n"
				   +"--For this, O dearly beloved, is the genuine Christine: body and soul\n"
				   +"and blood and ouns. Slow music, please. Shut your eyes, gents. One\n"
				   +"moment. A little trouble about those white corpuscles. Silence, all.\n"
				   +"He peered sideways up and gave a long slow whistle of call, then paused\n"
				   +"awhile in rapt attention, his even white teeth glistening here and there\n"
				   +"with gold points. Chrysostomos. Two strong shrill whistles answered\n"
				   +"through the calm.\n"
				   +"--Thanks, old chap, he cried briskly. That will do nicely. Switch off\n"
				   +"the current, will you?\n"
				   +"He skipped off the gunrest and looked gravely at his watcher, gathering\n"
				   +"about his legs the loose folds of his gown. The plump shadowed face and\n"
				   +"sullen oval jowl recalled a prelate, patron of arts in the middle ages.\n"
				   +"A pleasant smile broke quietly over his lips.\n"
				   +"toto toto toto toto toto toto toto toto toto toto toto \n"
				   +"toto toto toto toto toto toto toto toto toto toto toto \n";
		
		// split the string into lower case words, and strip all punctuation marks and white space.
		// This recipe is taken from StackOverflow
		// http://stackoverflow.com/questions/23332146/remove-punctuation-preserve-letters-and-white-space-java-regex
		String[] words = text.replaceAll("\\s+", " ").replaceAll("[^a-zA-Z\\s]", "").toLowerCase().split("\\s+");
		
		// create a new tree
		StringBST tree = new StringBST();
		
		// insert words and allow duplicates.  
		// int wordCounter = 0;
		for (int i = 0; i < words.length; i++) {
			tree.insertWithDuplicates( words[i] );
			// wordCounter++;
		}
		
		// display the tree (for debugging purposes)
		//tree.inOrderVisitDuplicates();
		//System.out.println( wordCounter + " words inserted" );
		
		// display unique words
		System.out.println( tree.length() );
		
		// display list of most frequent word(s)
		ArrayList<String> mostFreq = tree.findMostFrequent();
		if ( mostFreq.isEmpty() )
			System.out.println( "empty tree" );
		else {
			Iterator<String> it = mostFreq.iterator();
			while ( it.hasNext() ) 
			    System.out.print( it.next() + " " );
			System.out.println();
		}
	
	}

}

Output

214
the toto