Difference between revisions of "CSC212 Homework 6 Solutions 2014"

From dftwiki3
Jump to: navigation, search
(Created page with "--~~~~ ---- =Problem 1= <br /> <source lang="java"> </source> <br /> =Problem 2= <br /> <source lang="java"> </source> <br /> =Problem 3= <br /> <source lang="java"> </so...")
 
 
Line 1: Line 1:
 
--[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 12:13, 31 October 2014 (EDT)
 
--[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 12:13, 31 October 2014 (EDT)
 
----
 
----
 +
<onlydft>
 
=Problem 1=
 
=Problem 1=
 
<br />
 
<br />
 
<source lang="java">
 
<source lang="java">
 +
        private void generateDotLowKey( IntBSTNode p ) {
 +
        if ( p==null )
 +
        return;
 +
        if ( p.left != null )
 +
        System.out.println( p.key + " -> " + p.left.key +";"  );
 +
        if ( p.right != null )
 +
        System.out.println( p.key + " -> " + p.right.key +";"  );
 +
       
 +
        generateDot( p.left );
 +
        generateDot( p.right );
 +
        }
 +
  
 
</source>
 
</source>
Line 11: Line 24:
 
<br />
 
<br />
 
<source lang="java">
 
<source lang="java">
 +
 +
        private void generateDot( IntBSTNode p ) {
 +
        if ( p==null )
 +
        return;
 +
        if ( p.left != null )
 +
        System.out.println( p.key + " -> " + p.left.key +";"  );
 +
        else {
 +
        String nullNode = "null" + p.key + "left [label=\"\",width=.1,style=invis]";
 +
        System.out.println( nullNode + ";" );
 +
        System.out.println( p.key + " -> " + nullNode + " [style=invis];" );
 +
        }
 +
        if ( p.right != null )
 +
        System.out.println( p.key + " -> " + p.right.key +";"  );
 +
        else {
 +
        String nullNode = "null" + p.key + "right [label=\"\",width=.1,style=invis]";
 +
        System.out.println( nullNode + ";" );
 +
        System.out.println( p.key + " -> " + nullNode + " [style=invis];" );       
 +
        }
 +
       
 +
        generateDot( p.left );
 +
        generateDot( p.right );
 +
        }
  
 
</source>
 
</source>
Line 18: Line 53:
 
<br />
 
<br />
 
<source lang="java">
 
<source lang="java">
 +
/**
 +
* StringBST.java
 +
* @author D. Thiebaut
 +
* All material taken, and adapted from Drozdek's
 +
* Data Structures and Algorithms in Java.
 +
*
 +
*/
 +
import java.util.ArrayList;
 +
import java.util.Collections;
 +
import java.util.LinkedList;
 +
import java.util.Queue;
 +
 +
/**
 +
* A class implementing a BST node, with an integer key, and a left and right
 +
* pointer.
 +
*
 +
* @author thiebaut
 +
*
 +
*/
 +
class StringBSTNode {
 +
 +
public String key;
 +
public int counter;
 +
public StringBSTNode left, right;
 +
 +
StringBSTNode(String el, StringBSTNode l, StringBSTNode r) {
 +
key = el;
 +
left = l;
 +
right = r;
 +
counter = 1;
 +
}
 +
 +
StringBSTNode(String el) {
 +
this(el, null, null);
 +
}
 +
}
 +
 +
/**
 +
* The tree class. Implements most useful methods.
 +
*
 +
* @author thiebaut
 +
*
 +
*/
 +
public class StringBST {
 +
protected StringBSTNode root;
 +
protected int nodeCounter;
 +
private ArrayList<String> mostFrequentStrings;
 +
private int mostFrequentCounter;
 +
 +
/**
 +
* constructor creates an empty tree.
 +
*/
 +
StringBST() {
 +
root = null;
 +
}
 +
 +
protected void setRoot(StringBSTNode p) {
 +
root = p;
 +
}
 +
 +
public void clear() {
 +
root = null;
 +
}
 +
 +
public int length() {
 +
nodeCounter = 0;
 +
visitCountNodes(root);
 +
return nodeCounter;
 +
}
 +
 +
private void visitCountNodes(StringBSTNode p) {
 +
if (p == null)
 +
return;
 +
nodeCounter++;
 +
visitCountNodes(p.left);
 +
visitCountNodes(p.right);
 +
}
 +
 +
/**
 +
* Just use for debugging... Recursively visits the tree and display
 +
* information about what it finds.
 +
*/
 +
protected void debugVisit() {
 +
debugVisit(root);
 +
}
 +
 +
protected void debugVisit(StringBSTNode p) {
 +
if (p == null)
 +
return;
 +
String leftString = "has no left child", rightString = "has no right child";
 +
if (p.left != null)
 +
leftString = "has " + p.left.key + " as left child";
 +
if (p.right != null)
 +
rightString = "has " + p.right.key + " as right child";
 +
System.out.println("Node " + p.key + ", " + leftString + ", and "
 +
+ rightString);
 +
debugVisit(p.left);
 +
debugVisit(p.right);
 +
}
 +
 +
/**
 +
* Iteratively searches for an element in the tree. Returns the node
 +
* containing the element if found, or null otherwise.
 +
*
 +
* @param el
 +
* @return
 +
*/
 +
public StringBSTNode search(String el) {
 +
StringBSTNode p = root;
 +
while (p != null) {
 +
if (el.equals(p.key))
 +
return p;
 +
if (el.compareTo(p.key) < 0)
 +
p = p.left;
 +
else
 +
p = p.right;
 +
}
 +
return null;
 +
}
 +
 +
/**
 +
* recursively searches for an element in the tree. Returns the node
 +
* containing the element, or null if not found.
 +
*
 +
* @param el
 +
* @return
 +
*/
 +
public StringBSTNode recSearch(String el) {
 +
return recSearch(root, el);
 +
}
 +
 +
private StringBSTNode recSearch(StringBSTNode p, String el) {
 +
if (p == null)
 +
return null;
 +
if (el.equals(p.key))
 +
return p;
 +
if (el.compareTo(p.key) < 0)
 +
return recSearch(p.left, el);
 +
else
 +
return recSearch(p.right, el);
 +
}
 +
 +
/**
 +
* Find most frequent words in tree.
 +
* findMostFrequent() is the main entry point for this set of 3 functions
 +
* findMostFrequent( StringBSTNode ) is the one that explores recursively and
 +
*    computes the max frequency found in the nodes
 +
* findMostFrequent( StringBSTNode, int ) is the one we call after the previous
 +
*    one, once we know the max frequency, and this function locates all the nodes
 +
*    that have counters equal to the max frequency, and insert the keys in the
 +
*    member variable (field) that is an arrayList of strings.
 +
*
 +
public ArrayList<String> findMostFrequent() {
 +
mostFrequentCounter = 0;
 +
findMostFrequent( root );
 +
//System.out.println( "mostFrequentCounter = " + mostFrequentCounter );
 +
mostFrequentStrings = new ArrayList<String>();
 +
findMostFrequent( root, mostFrequentCounter );
 +
return mostFrequentStrings;
 +
}
 +
 +
public void findMostFrequent( StringBSTNode p ) {
 +
if ( p==null )
 +
return;
 +
if ( p.counter > mostFrequentCounter )
 +
mostFrequentCounter = p.counter;
 +
findMostFrequent( p.left );
 +
findMostFrequent( p.right );
 +
}
 +
 +
public void findMostFrequent( StringBSTNode p, int maxFreq ) {
 +
if ( p==null )
 +
return;
 +
if ( p.counter == maxFreq )
 +
mostFrequentStrings.add( p.key );
 +
findMostFrequent( p.left, maxFreq );
 +
findMostFrequent( p.right, maxFreq );
 +
}
 +
 +
    /**
 +
    * visits the tree in order and list the keys along with their frequencies.
 +
    */
 +
public void inOrderVisitDuplicates() {
 +
inOrderVisitDuplicates(root);
 +
System.out.println();
 +
}
 +
 +
private void inOrderVisitDuplicates(StringBSTNode p) {
 +
if (p == null)
 +
return;
 +
inOrderVisitDuplicates(p.left);
 +
System.out.println(p.key + " (" + p.counter + ") " );
 +
inOrderVisitDuplicates(p.right);
 +
}
 +
 +
/**
 +
* Traveral methods inOrderVisit preOrderVisit postOrderVisit
 +
*/
 +
public void inOrderVisit() {
 +
inOrderVisit(root);
 +
System.out.println();
 +
}
 +
 +
private void inOrderVisit(StringBSTNode p) {
 +
if (p == null)
 +
return;
 +
inOrderVisit(p.left);
 +
System.out.print(p.key + " ");
 +
inOrderVisit(p.right);
 +
}
 +
 +
public void preOrderVisit() {
 +
preOrderVisit(root);
 +
System.out.println();
 +
}
 +
 +
private void preOrderVisit(StringBSTNode p) {
 +
if (p == null)
 +
return;
 +
System.out.print(p.key + " ");
 +
preOrderVisit(p.left);
 +
preOrderVisit(p.right);
 +
}
 +
 +
public void postOrderVisit() {
 +
postOrderVisit(root);
 +
System.out.println();
 +
}
 +
 +
private void postOrderVisit(StringBSTNode p) {
 +
if (p == null)
 +
return;
 +
postOrderVisit(p.left);
 +
postOrderVisit(p.right);
 +
System.out.print(p.key + " ");
 +
}
 +
 +
/**
 +
* visits the tree breadth-first. Display the key in all the nodes, in
 +
* breadth-first order.
 +
*/
 +
public void breadthFirst() {
 +
StringBSTNode p = root;
 +
Queue<StringBSTNode> queue = new LinkedList<StringBSTNode>();
 +
 +
if (p == null)
 +
return;
 +
 +
queue.add(p);
 +
while (!queue.isEmpty()) {
 +
p = queue.poll();
 +
// --- do some work with the key. Here we just print it...
 +
System.out.print(p.key + " ");
 +
if (p.left != null)
 +
queue.add(p.left);
 +
if (p.right != null)
 +
queue.add(p.right);
 +
}
 +
}
 +
 +
/**
 +
* Inserts an element in the tree. We assume that the element is not already
 +
* there.
 +
*
 +
* @param el
 +
*/
 +
public void insert(String el) {
 +
// is the tree empty? if so, create 1 node
 +
if (root == null) {
 +
root = new StringBSTNode(el);
 +
return;
 +
}
 +
 +
// go down to the leaf that will be the parent
 +
// of the new node
 +
StringBSTNode p = root, prev = null;
 +
while (p != null) {
 +
prev = p;
 +
if (p.key.compareTo(el) < 0)
 +
p = p.right;
 +
else
 +
p = p.left;
 +
}
 +
 +
// add element as new leaf of prev's node
 +
if (el.compareTo(prev.key) < 0)
 +
prev.left = new StringBSTNode(el);
 +
else
 +
prev.right = new StringBSTNode(el);
 +
}
 +
 +
/**
 +
* inserts an element in the tree, and if it is already there, then increment
 +
* a counter for that already existing node.  OTherwise create a new node and
 +
* set its counter to 1.
 +
* @param el
 +
*/
 +
public void insertWithDuplicates(String el) {
 +
// is the tree empty? if so, create 1 node
 +
if (root == null) {
 +
root = new StringBSTNode(el);
 +
return;
 +
}
 +
 +
// go down to the leaf that will be the parent
 +
// of the new node
 +
StringBSTNode p = root, prev = null;
 +
while (p != null) {
 +
prev = p;
 +
if (p.key.equals(el)) {
 +
p.counter++;
 +
return;
 +
}
 +
if (p.key.compareTo(el) < 0)
 +
p = p.right;
 +
else
 +
p = p.left;
 +
}
 +
 +
// add element as new leaf of prev's node
 +
if (el.compareTo(prev.key) < 0)
 +
prev.left = new StringBSTNode(el);
 +
else
 +
prev.right = new StringBSTNode(el);
 +
}
 +
 +
/**
 +
* Delete element by merging. Finds the element, then the largest of its
 +
* left-subtree, and attaches the right-subtree of the node to delete to
 +
* this largest element.
 +
*
 +
* @param el
 +
*            : the key we want to remove.
 +
*/
 +
public void delete(String el) {
 +
StringBSTNode tmp, node, p = root, prev = null;
 +
 +
if (root == null) {
 +
System.out.println("Trying to delete from an empty tree");
 +
return;
 +
}
 +
 +
// find the node containing el
 +
while (p != null && p.key.equals(el) == false) {
 +
prev = p;
 +
if (p.key.compareTo(el) < 0)
 +
p = p.right;
 +
else
 +
p = p.left;
 +
}
 +
 +
if (p == null) {
 +
System.out.println("Key " + el + " not in tree");
 +
return;
 +
}
 +
 +
// we found the element. p is pointing to it. prev is pointing to
 +
// parent (or is null if el is in root).
 +
node = p;
 +
 +
// no right sub-tree?
 +
if (node.right == null) {
 +
// yes, then pick the left subtree
 +
node = node.left;
 +
} else if (node.left == null) {
 +
// yes, then pick the right subtree
 +
node = node.right;
 +
} else {
 +
// two existing subtrees.
 +
// go to left subtree
 +
tmp = node.left;
 +
 +
// and find the right-most node that doesn't have a right child.
 +
while (tmp.right != null)
 +
tmp = tmp.right;
 +
 +
// tmp points to right-most node (blue node)
 +
 +
// attach right subtree of node we're deleting (yellow node)
 +
// to right most node (blue node)
 +
tmp.right = node.right;
 +
 +
node = node.left;
 +
}
 +
 +
if (p == root)
 +
root = node;
 +
else if (prev.left == p)
 +
prev.left = node;
 +
else
 +
prev.right = node;
 +
}
 +
 +
/**
 +
* balance the tree by copying all the keys into an array first, then
 +
* sorting the array, then doing some binary split operation, going to the
 +
* middle of the array to find the root, then to the middle of the two
 +
* halves to find the children of the root, etc... and rebuilding the tree
 +
* that way.
 +
*
 +
* @return
 +
*/
 +
private void addNodeToArray(StringBSTNode p, ArrayList<String> allNodes) {
 +
if (p == null)
 +
return;
 +
addNodeToArray(p.left, allNodes);
 +
allNodes.add(p.key);
 +
addNodeToArray(p.right, allNodes);
 +
}
 +
 +
public void balance() {
 +
// visit the tree and copy all the nodes into an ArrayList
 +
// visit in in-order fashion, so as to create a sorted list of keys in
 +
// the array
 +
ArrayList<String> allNodes = new ArrayList<String>();
 +
addNodeToArray(root, allNodes);
 +
 +
// recursively reconstruct the tree
 +
clear();
 +
recursiveBalance(allNodes, 0, allNodes.size() - 1);
 +
}
 +
 +
private void recursiveBalance(ArrayList<String> allNodes, int low, int high) {
 +
if (low <= high) {
 +
int mid = (low + high) / 2;
 +
insert(allNodes.get(mid));
 +
recursiveBalance(allNodes, low, mid - 1);
 +
recursiveBalance(allNodes, mid + 1, high);
 +
}
 +
}
 +
 +
/**
 +
* generateDot: generates the dot representation of the tree.
 +
*/
 +
public void generateDot() {
 +
System.out.println("digraph T {\nlabel = \"Mickey Mouse\";");
 +
generateDot(root);
 +
System.out.println("}");
 +
}
 +
 +
private void generateDotLowKey(StringBSTNode p) {
 +
if (p == null)
 +
return;
 +
if (p.left != null)
 +
System.out.println(p.key + " -> " + p.left.key + ";");
 +
if (p.right != null)
 +
System.out.println(p.key + " -> " + p.right.key + ";");
 +
 +
generateDot(p.left);
 +
generateDot(p.right);
 +
}
 +
 +
private void generateDot(StringBSTNode p) {
 +
if (p == null)
 +
return;
 +
if (p.left != null)
 +
System.out.println(p.key + " -> " + p.left.key + ";");
 +
else {
 +
String nullNode = "null" + p.key
 +
+ "left [label=\"\",width=.1,style=invis]";
 +
System.out.println(nullNode + ";");
 +
System.out.println(p.key + " -> " + nullNode + " [style=invis];");
 +
}
 +
if (p.right != null)
 +
System.out.println(p.key + " -> " + p.right.key + ";");
 +
else {
 +
String nullNode = "null" + p.key
 +
+ "right [label=\"\",width=.1,style=invis]";
 +
System.out.println(nullNode + ";");
 +
System.out.println(p.key + " -> " + nullNode + " [style=invis];");
 +
}
 +
 +
generateDot(p.left);
 +
generateDot(p.right);
 +
}
 +
 +
/**
 +
* M A I N P R O G R A M
 +
*
 +
*/
 +
static public void main(String[] args) {
 +
 +
}
 +
}
  
 
</source>
 
</source>
 
<br />
 
<br />
 
<br />
 
<br />
 +
</onlydft>
 
<br />
 
<br />
 
<br />
 
<br />

Latest revision as of 11:21, 31 October 2014

--D. Thiebaut (talk) 12:13, 31 October 2014 (EDT)


...














Retrieved from "http://dominiquethiebaut.com/dftwiki3/index.php?title=CSC212_Homework_6_Solutions_2014&oldid=23969"