Writing traversal methods

You will create two files in the csc403 package: one called A3SimplerBST.java and the other TestA3.java. Details on these programs appears below.

Copy the file SimplerBST.java from the week 1 examples package and rename the file and class A3SimplerBST. Add two public methods:

• one named twoChildrenCount that takes no parameters and that, when called, traverses every node of the tree to count how many nodes have two children.
• one named sameValueCount that takes a paremeter of generic type V, and that, when called, traverses every node of the tree to count the number of nodes whose value (not its key) is equal to the value passed as a parameter. To check equality you must use the equals method and not the == operator.

As with the get, put, and delete methods, you will need each of the public methods described above to call a corresponding private recursive method.

Next, write a program called TestA3 that:

• Reads the words in the file data/tale.txt into an array using the StdIn.readAllStrings() method.
• Fills a A3SimplerBST symbol table object with counts of words in that array. It should also keep a count of the number of unique words by adding 1 to a counter whenever a word is first added to the symbol table.
• Prints the unique word count, which also is the number of nodes in the BST.
• Calls the twoChildrenCount method for the A3SimplerBST symbol table and prints the value returned.
• Calls the sameValueCount method for the A3SimplerBST symbol table to count and print how many words occur once and then again how many words occur 5 times.

Some difficulty in using node class in methods.

package week1examples;

/* * This is a simplified version of the BST class * from the algs32 package. * */ import stdlib.*; import algs13.Queue;

public class SimplerBST, V> { private Node root; // root of BST

private static class Node,V> { public K key; // sorted by key public V val; // associated data public Node left, right; // left and right subtrees

public Node(K key, V val) { this.key = key; this.val = val; } } public SimplerBST() {}

/* ********************************************************************* * Search BST for given key, and return associated value if found, * return null if not found ***********************************************************************/ // does there exist a key-value pair with given key? public boolean contains(K key) { return get(key) != null; }

// return value associated with the given key, or null if no such key exists public V get(K key) { return get(root, key); } private V get(Node x, K key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp < 0) return get(x.left, key); else if (cmp > 0) return get(x.right, key); else return x.val; }

/* ********************************************************************* * Insert key-value pair into BST * If key already exists, update with new value ***********************************************************************/ public void put(K key, V val) { if (val == null) { delete(key); return; } root = put(root, key, val); }

private Node put(Node x, K key, V val) { if (x == null) return new Node<>(key, val); int cmp = key.compareTo(x.key); if (cmp < 0) x.left = put(x.left, key, val); else if (cmp > 0) x.right = put(x.right, key, val); else x.val = val; return x; }

/* ********************************************************************* * Delete ***********************************************************************/

public void delete(K key) { root = delete(root, key); } private Node delete(Node x, K key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp < 0) x.left = delete(x.left, key); else if (cmp > 0) x.right = delete(x.right, key); else { // x is the node to be deleted. // The value returned in each of these cases below // becomes the value of the child reference from // the parent of x. Returning a null makes that // reference a null and so cuts x off, causing its // automatic deletion. // Determine how many children x has. if (x.right == null && x.left == null){ // This is a leaf node. return null; } else if (x.right == null) { // One child, to the left. return x.left; } else if (x.left == null) { // One child, to the right. return x.right; } else { // Node x has two children. // Find the node in x's right subtree with // the minimum key. Node rightTreeMinNode = findMin(x.right); x.key = rightTreeMinNode.key; x.val = rightTreeMinNode.val; x.right = delete(x.right, rightTreeMinNode.key); } } return x; } private Node findMin(Node x) { if (x.left == null) return x; else return findMin(x.left); }

public void printKeys() { printKeys(root); } private void printKeys(Node x) { if (x == null) return; printKeys(x.left); StdOut.println(x.key); printKeys(x.right); } public Iterable keys() { Queue q = new Queue<>(); inOrder(root, q); return q; }

private void inOrder(Node x, Queue q) { if (x == null) return; inOrder(x.left, q); q.enqueue(x.key); inOrder(x.right, q); } public int height() { return height(root); } private int height(Node x) { if (x == null) return -1; return 1+Math.max(height(x.left), height(x.right)); }

/* *************************************************************************** * Visualization *****************************************************************************/

public void drawTree() { if (root != null) { StdDraw.setPenColor (StdDraw.BLACK); StdDraw.setCanvasSize(1200,700); drawTree(root, .5, 1, .25, 0); } } private void drawTree (Node n, double x, double y, double range, int depth) { int CUTOFF = 10; StdDraw.text (x, y, n.key.toString ()); StdDraw.setPenRadius (.007); if (n.left != null && depth != CUTOFF) { StdDraw.line (x-range, y-.08, x-.01, y-.01); drawTree (n.left, x-range, y-.1, range*.5, depth+1); } if (n.right != null && depth != CUTOFF) { StdDraw.line (x+range, y-.08, x+.01, y-.01); drawTree (n.right, x+range, y-.1, range*.5, depth+1); } } }