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

1. Create a new class called StringBST.java. This will be the program you submit.
2. Instead of keeping track of a tree of ints, StringBST.java keeps track of 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 key 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.

int key, el;
...
if ( el < key ){
   ...
}

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