BST.java

/*
 * Name:Janan Patel	
 * Date: 12/6/2021
 * Course Number: Data Structures
 * Course Name:Data Structures
 * Problem Number: 12
 * Email: [email protected]
 * Short Description of the Problem
 * BST main class. Source code
 */
package chapter25;

import java.util.*;

public class BST<E extends Comparable<E>> implements Tree<E> {

	protected static class TreeNode<E> {
		public E data;
		public TreeNode<E> left = null;
		public TreeNode<E> right = null;

		public TreeNode(E e) {
			this.data = e;
		}
	}
	
	protected TreeNode<E> root = null;
	protected int size = 0;

	/** Create a default binary tree */
	public BST() {
	}

	/** Create a binary tree from an array of objects */
	public BST(E[] objects) {
		for (int i = 0; i < objects.length; i++)
			add(objects[i]);
	}

	/** Recursively duplicate tree */
	private TreeNode<E> copy(TreeNode<E> p) {
		TreeNode<E> temp = null;
		if (p != null) {
			temp = new TreeNode<E>(p.data);
			temp.left = copy(p.left);
			temp.right = copy(p.right);
		}
		return temp;
	}

	public void copyTree(BST<E> p) {
		root = copy(p.root);
	}


	@Override /** Remove all elements from the tree */
	public void clear() {
		root = null;
		size = 0;
	}

	@Override /** Get the number of nodes in the tree */
	public int getSize() {
		return size;
	}

	/** Returns the root of the tree */
	public TreeNode<E> getRoot() {
		return root;
	}
	
	// **************************************************************************************************
	// Traversals
//	@Override
//	public void inorder() {
//		inorder(root, new Execution<E>() {
//			public void execute(E e) {
//				System.out.println(e);
//			}});
//	}	
	
	@Override
	public void inorder() {
		inorder(root, e -> System.out.println(e));
	}
	
	public void inorder(Execution<E> e) {
		inorder(root, e);
	}	
	
	@Override
	public void preorder() {
		preorder(root, e -> System.out.println(e));
	}

	public void preorder(Execution<E> e) {
		preorder(root, e);
	}

	@Override
	public void postorder() {
		postorder(root, e -> System.out.println(e));
	}
	
	public void postorder(Execution<E> e) {
		postorder(root, e);
	}
	

	private void inorder(TreeNode<E> p, Execution<E> e) {
		if (p != null) {
			inorder(p.left, e);
			e.execute(p.data);
			inorder(p.right, e);
		}
	}

	private void preorder(TreeNode<E> p, Execution<E> e) {
		if (p != null) {
			e.execute(p.data);
			preorder(p.left, e);
			preorder(p.right, e);
		}
	}

	private void postorder(TreeNode<E> p, Execution<E> e) {
		if (p != null) {
			postorder(p.left, e);
			postorder(p.right, e);
			e.execute(p.data);
		}
	}

	// **************************************************************************************************
	// Recursive Counting Routines

	public int treeHeight() {
		return height(root);
	}

	public int treeNodeCount() {
		return nodeCount(root);
	}

	public int treeLeavesCount() {
		return leavesCount(root);
	}

	private int height(TreeNode<E> p) {
		if (p == null)
			return 0;
		else
			return 1 + Math.max(height(p.left), height(p.right));
	}

	private int nodeCount(TreeNode<E> p) {
		if (p == null)
			return 0;
		else
			return 1 + nodeCount(p.left) + nodeCount(p.right);
	}

	private int leavesCount(TreeNode<E> p) {
		if (p == null)
			return 0;
		else if (p.left == null && p.right == null)
			return 1;
		else
			return leavesCount(p.left) + leavesCount(p.right);
	}

	@Override /** Returns true if the data is in the tree */
	public boolean search(E e) {
		TreeNode<E> current = root; // Start from the root

		while (current != null) {
			if (e.compareTo(current.data) < 0) {
				current = current.left;
			} else if (e.compareTo(current.data) > 0) {
				current = current.right;
			} else // data matches current.data
				return true; // data is found
		}

		return false;
	}

	public boolean recSearch(E searchItem) {
		return recSearch(root, searchItem);
	}

	private boolean recSearch(TreeNode<E> ptr, E searchItem) {
		if (ptr == null)
			return false;
		else if (searchItem.equals(ptr.data))
			return true;
		else if (searchItem.compareTo(ptr.data) < 0)
			return recSearch(ptr.left, searchItem);
		else
			return recSearch(ptr.right, searchItem);
	}	
	
	@Override /**
				 * Insert data e into the binary tree Return true if the data is inserted
				 * successfully
				 */
	public boolean insert(E e) {
		if (root == null)
			root =  new TreeNode<E>(e); // Create a new root
		else {
			// Locate the parent node
			TreeNode<E> parent = null;
			TreeNode<E> current = root;
			while (current != null)
				if (e.compareTo(current.data) < 0) {
					parent = current;
					current = current.left;
				} else if (e.compareTo(current.data) > 0) {
					parent = current;
					current = current.right;
				} else
					return false; // Duplicate node not inserted

			// Create the new node and attach it to the parent node
			if (e.compareTo(parent.data) < 0)
				parent.left = new TreeNode<E>(e);
			else
				parent.right = new TreeNode<E>(e);
		}

		size++;
		return true; // data inserted successfully
	}

	public void recinsert(E e) {
		root = recinsertHelper(root, e);
	}

	private TreeNode<E> recinsertHelper(TreeNode<E> p, E e) {
		TreeNode<E> retval;
		if (p == null) {
			TreeNode<E> newNode = new TreeNode<E>(e);
			retval = newNode;
		} else if (e.compareTo(p.data) < 0) {
			p.left = recinsertHelper(p.left, e);
			retval = p;
		} else if (e.compareTo(p.data) == 0)
			retval = p;
		else {
			p.right = recinsertHelper(p.right, e);
			retval = p;
		}
		return retval;
	}

	/** Returns a path from the root leading to the specified data */
	public ArrayList<TreeNode<E>> path(E e) {
		var list = new ArrayList<TreeNode<E>>();
		TreeNode<E> current = root; // Start from the root

		while (current != null) {
			list.add(current); // Add the node to the list
			if (e.compareTo(current.data) < 0) {
				current = current.left;
			} else if (e.compareTo(current.data) > 0) {
				current = current.right;
			} else
				break;
		}

		return list; // Return an array list of nodes
	}

	@Override /**
				 * Delete an data from the binary tree. Return true if the data is deleted
				 * successfully Return false if the data is not in the tree
				 */
	public boolean delete(E e) {
		// Locate the node to be deleted and also locate its parent node
		TreeNode<E> parent = null;
		TreeNode<E> current = root;
		while (current != null) {
			if (e.compareTo(current.data) < 0) {
				parent = current;
				current = current.left;
			} else if (e.compareTo(current.data) > 0) {
				parent = current;
				current = current.right;
			} else
				break; // data is in the tree pointed at by current
		}

		if (current == null)
			return false; // data is not in the tree

		// Case 1: current has no left child
		if (current.left == null) {
			// Connect the parent with the right child of the current node
			if (parent == null) {
				root = current.right;
			} else {
				if (e.compareTo(parent.data) < 0)
					parent.left = current.right;
				else
					parent.right = current.right;
			}
		} else {
			// Case 2: The current node has a left child
			// Locate the rightmost node in the left subtree of
			// the current node and also its parent
			TreeNode<E> parentOfRightMost = current;
			TreeNode<E> rightMost = current.left;

			while (rightMost.right != null) {
				parentOfRightMost = rightMost;
				rightMost = rightMost.right; // Keep going to the right
			}

			// Replace the data in current by the data in rightMost
			current.data = rightMost.data;

			// Eliminate rightmost node
			if (parentOfRightMost.right == rightMost)
				parentOfRightMost.right = rightMost.left;
			else
				// Special case: parentOfRightMost == current
				parentOfRightMost.left = rightMost.left;
		}

		size--;
		return true; // data deleted successfully
	}

	public void recdelete(E e) {
		root = recdeleteHelper(root, e);
	}

	private TreeNode<E> recdeleteHelper(TreeNode<E> p, E e) {
		TreeNode<E> retval;
		if (p == null)
			retval = null;
		else if (e.compareTo(p.data) < 0) { // p.data > insertItem
			p.left = recdeleteHelper(p.left, e);
			retval = p;
		} else if (e.compareTo(p.data) < 0) {
			p.right = recdeleteHelper(p.right, e);
			retval = p;
		} else { // Found Item to delete!!!
			size--;
			if (p.left == null && p.right == null)
				retval = null;
			else if (p.left == null)
				retval = p.right;
			else if (p.right == null)
				retval = p.left;
			else {
				// Find Item whose value is immediately before p.data
				TreeNode<E> current = p.left;
				while (current.right != null)
					current = current.right;
				p.data = current.data;
				p.left = recdeleteHelper(p.left, current.data);
				retval = p;
			}
		}
		return retval;
	}

	// Create code to support Iteration through this data Structure
	@Override 
	public Iterator<E> iterator() {
		return new InorderIterator();
	}

	// Inner class InorderIterator
	private class InorderIterator implements Iterator<E> {
		// Store the elements in a list
		private ArrayList<E> list = new ArrayList<>();
		private int current = 0; // Point to the current data in list

		public InorderIterator() {
			inorder(); // Traverse binary tree and store elements in list
		}

		/** Inorder traversal from the root */
		private void inorder() {
			inorder(root);
		}

		/** Inorder traversal from a subtree */
		private void inorder(TreeNode<E> root) {
			if (root == null)
				return;
			inorder(root.left);
			list.add(root.data);
			inorder(root.right);
		}

		@Override /** More elements for traversing? */
		public boolean hasNext() {
			return current < list.size();
		}

		@Override /** Get the current data and move to the next */
		public E next() {
			return list.get(current++);
		}

		@Override // Remove the data returned by the last next()
		public void remove() {
			if (current == 0) // next() has not been called yet
				throw new IllegalStateException();

			delete(list.get(--current));
			list.clear(); // Clear the list
			inorder(); // Rebuild the list
		}
	}

}

Execution.java

/*
 * Name:Janan Patel	
 * Date: 12/6/2021
 * Course Number: Data Structures
 * Course Name:Data Structures
 * Problem Number: 12
 * Email: [email protected]
 * Short Description of the Problem
 * interface for execution
 */
package chapter25;

interface Execution<E> {
	void execute(E e);
}

KeyValue.java

/*
 * Name:Janan Patel	
 * Date: 12/6/2021
 * Course Number: Data Structures
 * Course Name:Data Structures
 * Problem Number: 12
 * Email: [email protected]
 * Short Description of the Problem
 * Key Value class
 */
package chapter25;


public class KeyValue<K extends Comparable<K>, V> implements Comparable<KeyValue<K, V>> {
	private K key;
	private V value;

	public KeyValue(K key, V value) {
		this.key = key;
		this.value = value;
	}

	public K getKey() {
		return key;
	}

	public V getValue() {
		return value;
	}

	public void setKey(K key) {
		this.key = key;
	}

	public void setValue(V value) {
		this.value = value;
	}

	@Override
	public int compareTo(KeyValue<K, V> o) {
		return this.key.compareTo(o.key);
	}

	@Override
	public String toString() {
		return "[key=" + key + ", value=" + value + "]";
	}

}

TestBST.java

package chapter25;
/*
 * Name:Janan Patel	
 * Date: 12/6/2021
 * Course Number: Data Structures
 * Course Name:Data Structures
 * Problem Number: 12
 * Email: [email protected]
 * Short Description of the Problem
 * Simple Binary name organizer.
 */

import java.io.File;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.net.URL;
import java.util.Scanner;

public class TestBST {
	private final static String TITLE = "The Binary Search Tree Program";
	private final static String CONTINUE_PROMPT = "Do this again? [y/N] ";

	// **********************************************
	// Put as many methods you need here

	// **********************************************
	// Start your logic coding in the process method
	private static void process(Scanner input, String args[]) throws Exception {
		System.out.println("Pick a year between 2011 and 2020 inclusively.");
		int year = input.nextInt();
		if (year >= 2011 && year <= 2021) {

			File file1 = new File("yob" + year + "byname.txt");
			FileWriter fw = new FileWriter(file1);
			PrintWriter pw = new PrintWriter(fw);
			File file2 = new File("yob" + year + "bynumber.txt");
			FileWriter fw2 = new FileWriter(file2);
			PrintWriter pw2 = new PrintWriter(fw2);

			Scanner sc = new Scanner(
					new URL("https://cs.stcc.edu/~silvestri/names/randyob" + year + ".txt").openStream());
			var tree1 = new BST<KeyValue<String, Integer>>();
			var tree2 = new BST<KeyValue<Integer, String>>();
			sc.useDelimiter("\\s*,\\s*|\\s+");
			while (sc.hasNextLine()) {
				String name = sc.next();
				@SuppressWarnings("unused")
				String sex = sc.next();
				int number = sc.nextInt();
				tree1.insert(new KeyValue<String, Integer>(name, number));
				tree2.insert(new KeyValue<Integer, String>(number, name));
			}
			sc.close();

			var it = tree1.iterator();
			while (it.hasNext()) {
				pw.write(it.next() + "\n");

			}

			pw.close();

			var it2 = tree2.iterator();
			while (it2.hasNext()) {
				pw2.write(it2.next() + "\n");

			}
			pw2.close();

			System.out.println("Files have been created.");
		} else
			System.out.println("Error: Invalid Year. Please enter a valid year.");

	}

//		
	// **********************************************
	// Do not change the doThisAgain method
	private static boolean doThisAgain(Scanner input, String prompt) {
		System.out.println(prompt);
		String doOver = input.nextLine();
		return doOver.trim().equalsIgnoreCase("Y");
	}

	// **********************************************
	// Do not change the main method
	public static void main(String args[]) throws Exception {
		System.out.println("Welcome to " + TITLE);
		Scanner input = new Scanner(System.in);
		do {
			process(input, args);
		} while (doThisAgain(input, CONTINUE_PROMPT));
		input.close();
		System.out.println("Thank you for using " + TITLE);
	}

}

Tree.java

/*
 * Name:Janan Patel	
 * Date: 12/6/2021
 * Course Number: Data Structures
 * Course Name:Data Structures
 * Problem Number: 12
 * Email: [email protected]
 * Short Description of the Problem
 * Tree interface.
 */
package chapter25;

import java.util.Collection;

public interface Tree<E> extends Collection<E> {
	/** Return true if the element is in the tree */
	public boolean search(E e);

	/**
	 * Insert element e into the binary tree Return true if the element is
	 * inserted successfully
	 */
	public boolean insert(E e);

	/**
	 * Delete the specified element from the tree Return true if the element is
	 * deleted successfully
	 */
	public boolean delete(E e);

	/** Get the number of elements in the tree */
	public int getSize();

	/** Inorder traversal from the root */
	public void inorder();

	/** Postorder traversal from the root */
	public void postorder();

	/** Preorder traversal from the root */
	public void preorder();

	@Override /** Return true if the tree is empty */
	public default boolean isEmpty() {
		return this.size() == 0;
	}

	@Override
	public default boolean contains(Object e) {
		return search((E) e);
	}

	@Override
	public default boolean add(E e) {
		return insert(e);
	}

	@Override
	public default boolean remove(Object e) {
		return delete((E) e);
	}

	@Override
	public default int size() {
		return getSize();
	}

	@Override
	public default boolean containsAll(Collection<?> c) {
		// Left as an exercise
		return false;
	}

	@Override
	public default boolean addAll(Collection<? extends E> c) {
		// Left as an exercise
		return false;
	}

	@Override
	public default boolean removeAll(Collection<?> c) {
		// Left as an exercise
		return false;
	}

	@Override
	public default boolean retainAll(Collection<?> c) {
		// Left as an exercise
		return false;
	}

	@Override
	public default Object[] toArray() {
		// Left as an exercise
		return null;
	}

	@Override
	public default <T> T[] toArray(T[] array) {
		// Left as an exercise
		return null;
	}
}