Finish the implementation of this Binary Search Tree and BSTDictionary, then write a class WordCount which can take a txt file and put each word in the text file

into the binary search tree. The end result should be a binary search tree with each word from the file in its own node in the tree. Below is the code for the Binary search tree, and below that is the txt file for putting into the tree.

BinaryNode.java

public class BinaryNode {

private T data;

private BinaryNode leftChild, rightChild;

public BinaryNode() {

this(null);

}

public BinaryNode(T data) {

this(data, null, null);

}

public BinaryNode(T data, BinaryNode left, BinaryNode right) {

this.data = data;

leftChild = left;

setRightChild(right);

}

public T getData() {

return data;

}

public void setData(T data) {

this.data = data;

}

public BinaryNode getLeftChild(){

return leftChild;

}

public void setLeftChild(BinaryNode left) {

leftChild = left;

}

public BinaryNode getRightChild() {

return rightChild;

}

public void setRightChild(BinaryNode right) {

this.rightChild = right;

}

public boolean hasLeftChild() {

return leftChild != null;

}

public boolean hasRightChild() {

return rightChild != null;

}

public boolean isLeaf() {

return (!hasLeftChild() && !hasRightChild());

}

public BinaryNode copy(){

BinaryNode newRoot = new BinaryNode(data);

if(leftChild != null) {

newRoot.setLeftChild(leftChild.copy());

}

if(rightChild != null) {

newRoot.setRightChild(rightChild.copy());

}

return newRoot;

}

public int getHeight() {

return getHeight(this);

}

private int getHeight(BinaryNode node) {

int height = 0;

if(node != null) {

height = 1 + Math.max(getHeight(node.getLeftChild()), getHeight(node.getRightChild()));

}

return height;

}

public int getNumberOfNodes() {

return getNumberOfNodes(this);

}

private int getNumberOfNodes(BinaryNode node) {

int rightNumber = 0;

int leftNumber = 0;

if(leftChild != null) {

leftNumber = getNumberOfNodes(node.getLeftChild());

}

if(rightChild != null) {

rightNumber = getNumberOfNodes(node.getRightChild());

}

return 1 + leftNumber + rightNumber;

}

}

BinarySearchTree.java

public class BinarySearchTree>

extends BinaryTree

implements SearchTreeInterface{

public BinarySearchTree(){

super();

}

public BinarySearchTree(T rootEntry){

super();

setRootNode(new BinaryNode (rootEntry));

}

public void setTree(T rootData){

throw new UnsupportedOperationException();

}

public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree)

{

throw new UnsupportedOperationException();

}

@Override

public boolean contains(T entry) {

return getEntry(entry) != null;

}

@Override

public T getEntry(T entry) {

return findEntry(getRootNode(), entry);

}

private T findEntry(BinaryNode rootNode, T entry){

T result = null;

if (rootNode != null){

T rootEntry = rootNode.getData();

if(entry.equals(rootEntry))

result = rootEntry;

else if (entry.compareTo(rootEntry) < 0)

result = findEntry(rootNode.getLeftChild(), entry);

else

result = findEntry(rootNode.getRightChild(), entry);

}

return result;

}

@Override

public T add(T newEntry) {

T result = null;

if(isEmpty())

setRootNode(new BinaryNode<>(newEntry));

else

result = addEntry(getRootNode(), newEntry);

return result;

}

private T addEntry(BinaryNode rootNode, T newEntry){

assert rootNode != null;

T result = null;

int comparison = newEntry.compareTo(rootNode.getData());

if(comparison == 0){

result = rootNode.getData();

rootNode.setData(newEntry);

}

else if(comparison < 0){

if(rootNode.hasLeftChild())

result = addEntry(rootNode.getLeftChild(), newEntry);

else

rootNode.setLeftChild(new BinaryNode<>(newEntry));

}

else{

assert comparison > 0;

if(rootNode.hasRightChild())

result = addEntry(rootNode.getRightChild(), newEntry);

else

rootNode.setRightChild(new BinaryNode<>(newEntry));

}

return result;

}

private class ReturnObject{

T data;

ReturnObject(T data){

}

public T get(){

return data;

}

public void set(T data){

this.data= data;

}

}

@Override

public T remove(T entry){

ReturnObject oldEntry = new ReturnObject(null);

BinaryNode newRoot = removeEntry(getRootNode(), entry, oldEntry);

setRootNode(newRoot);

return oldEntry.get();

}

private BinaryNode removeEntry(BinaryNode rootNode, T entry, ReturnObject oldEntry){

if(rootNode != null){

T rootData = rootNode.getData();

int comparison = entry.compareTo(rootData);

if(comparison == 0){

oldEntry.set(rootData);

rootNode = removeFromRoot(rootNode);

}

else if (comparison < 0){

BinaryNode leftChild = rootNode.getLeftChild();

BinaryNode subTreeRoot = removeEntry(leftChild, entry, oldEntry);

rootNode.setLeftChild(subTreeRoot);

}

else{

BinaryNode rightChild = rootNode.getRightChild();

rootNode.setRightChild(removeEntry(rightChild, entry, oldEntry));

}

}

return rootNode;

}

private BinaryNode removeFromRoot(BinaryNode rootNode){

if(rootNode.hasLeftChild() && rootNode.hasRightChild()){

BinaryNode leftSubtreeRoot = rootNode.getLeftChild();

BinaryNode largestNode = findLargest(leftSubtreeRoot);

rootNode.setData(largestNode.getData());

rootNode.setLeftChild(removeLargest(leftSubtreeRoot));

}

else if (rootNode.hasRightChild())

rootNode = rootNode.getRightChild();

else

rootNode = rootNode.getLeftChild();

return rootNode;

}

private BinaryNode findLargest(BinaryNode rootNode){

if(rootNode.hasRightChild())

rootNode = findLargest(rootNode.getRightChild());

return rootNode;

}

private BinaryNode removeLargest(BinaryNode rootNode){

if(rootNode.hasRightChild()){

BinaryNode rightChild = rootNode.getRightChild();

rightChild = removeLargest(rightChild);

rootNode.setRightChild(rightChild);

}

else

rootNode = rootNode.getLeftChild();

return rootNode;

}

//implements contains, getEntry, add and remove here

}

BinaryTree.java

import java.util.Iterator;

import java.util.Stack;

public class BinaryTree implements BinaryTreeInterface {

private BinaryNode root;

public BinaryTree() {

root = null;

}

public BinaryTree(T rootData) {

root = new BinaryNode(rootData);

}

public BinaryTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) {

privateSetTree(rootData, leftTree, rightTree);

}

public void setTree(T rootData) {

root = new BinaryNode(rootData);

}

public void setTree(T rootData, BinaryTree left, BinaryTree right) {

privateSetTree(rootData, left, right);

}

private void privateSetTree(T rootData, BinaryTree left, BinaryTree right) {

root = new BinaryNode<>(rootData);

if ((left != null) && (!left.isEmpty())) {

root.setLeftChild(left.root.copy());

}

if ((right != null) && (!right.isEmpty())) {

root.setRightChild(right.root.copy());

}

}

public T getRootData() {

return root.getData();

}

public int getHeight() {

return root.getHeight();

}

public int getNumberOfNodes() {

return root.getNumberOfNodes();

}

public boolean isEmpty() {

return root == null;

}

public void clear() {

root = null;

}

protected BinaryNode getRootNode() {

return root;

}

protected void setRootData(T rootData){

root.setData(rootData);

}

protected void setRootNode(BinaryNode rootNode){

root = rootNode;

}

public Iterator getPreorderIterator() {

throw new UnsupportedOperationException("Preorder not supported.");

}

public Iterator getInorderIterator() {

throw new UnsupportedOperationException("Inorder not supported.");

}

public Iterator getPostorderIterator() {

return new PostorderIterator();

}

public Iterator getLevelorderIterator() {

throw new UnsupportedOperationException("Level Order not supported.");

}

private class PostorderIterator implements Iterator {

private Stack> nodeStack;

private BinaryNode current;

public PostorderIterator() {

nodeStack = new Stack<>();

current = root;

populateStack(current);

}

private void populateStack(BinaryNode node){

nodeStack.add(node);

if(node.hasRightChild()){

populateStack(node.getRightChild());

}

if(node.hasLeftChild()){

populateStack(node.getLeftChild());

}

}

public boolean hasNext() {

return !nodeStack.isEmpty();

}

public T next() {

return nodeStack.pop().getData();

}

}

}

BinaryTreeInterface.java

public interface BinaryTreeInterface extends TreeInterface, TreeIteratorInterface{

public void setTree(T rootData);

public void setTree(T rootData, BinaryTree left, BinaryTree right);

}

BSTDictionary.java

import java.util.Iterator;

public class BSTDictionary,V>

implements DictionaryInterface{

private SearchTreeInterface> bst;

public BSTDictionary(){

bst = new BinarySearchTree<>();

}

private class Entry,T>

implements Comparable>

{

private S key;

private T value;

private Entry(S searchKey, T dataValue){

key = searchKey;

value = dataValue;

}

public int compareTo(Entry other){

return key.compareTo(other.key);

}

// Entry should also define the method equals, to String, getKey, getValue, and setValue. no setKey is provided

}

@Override

public V add(K key, V value) {

Entry newEntry = new Entry<>(key, value);

Entry returnedEntry = bst.add(newEntry);

V result = null;

if(returnedEntry != null)

result = returnedEntry.getValue();

return result;

}

@Override

public V remove(K key) {

// TODO Auto-generated method stub

return null;

}

@Override

public V getValue(K key) {

// TODO Auto-generated method stub

return null;

}

@Override

public boolean contains(K key) {

// TODO Auto-generated method stub

return false;

}

@Override

public Iterator getKeyIterator() {

// TODO Auto-generated method stub

return null;

}

@Override

public boolean isEmpty() {

// TODO Auto-generated method stub

return false;

}

@Override

public int getSize() {

// TODO Auto-generated method stub

return 0;

}

@Override

public void clear() {

// TODO Auto-generated method stub

}

}

DictionaryInterface.java

import java.util.Iterator;

public interface DictionaryInterface{

public V add(K key, V value);

public V remove(K key);

public V getValue(K key);

public boolean contains(K key);

public Iterator getKeyIterator();

public boolean isEmpty();

public int getSize();

public void clear();

}

SearchTreeInterface.java

import java.util.Iterator;

public interface SearchTreeInterface>

extends TreeInterface{

public boolean contains(T entry);

public T getEntry(T entry);

public T add(T newEntry);

public T remove(T entry);

public Iterator getInorderIterator;

}

TreeInterface.java

public interface TreeInterface {

public T getRootData();

public int getHeight();

public int getNumberOfNodes();

public boolean isEmpty();

public void clear();

}

TreeIteratorInterface.java

import java.util.Iterator;

public interface TreeIteratorInterface {

public Iterator getPreorderIterator();

public Iterator getInorderIterator();

public Iterator getPostorderIterator();

public Iterator getLevelorderIterator();

}

uscontitution.txt

We the People of the United States in Order to form a more perfect Union

establish Justice insure domestic Tranquility provide for the common

defence promote the general Welfare and secure the Blessings of Liberty to

ourselves and our Posterity do ordain and establish this Constitution for the

United States of America

Article 1

Section 1

All legislative Powers herein granted shall be vested in a Congress of the

United States which shall consist of a Senate and House of Representatives

Section 2

The House of Representatives shall be composed of Members chosen every second

Year by the People of the several States and the Electors in each State shall

have the Qualifications requisite for Electors of the most numerous Branch of

the State Legislature

No Person shall be a Representative who shall not have attained to the Age of

twenty five Years and been seven Years a Citizen of the United States and who

shall not when elected be an Inhabitant of that State in which he shall be

chosen

Representatives and direct Taxes shall be apportioned among the several States

which may be included within this Union according to their respective Numbers

which shall be determined by adding to the whole Number of free Persons

including those bound to Service for a Term of Years and excluding Indians not

taxed three fifths of all other Persons

The actual Enumeration shall be made within three Years after the first Meeting

of the Congress of the United States and within every subsequent Term of ten

Years in such Manner as they shall by Law direct The Number of

Representatives shall not exceed one for every thirty Thousand but each State

shall have at Least one Representative and until such enumeration shall be

made the State of New Hampshire shall be entitled to choose three

Massachusetts eight Rhode Island and Providence Plantations one Connecticut

five New York six New Jersey four Pennsylvania eight Delaware one Maryland

six Virginia ten North Carolina five South Carolina five and Georgia three

When vacancies happen in the Representation from any State the Executive

Authority thereof shall issue Writs of Election to fill such Vacancies

The House of Representatives shall choose their Speaker and other Officers and

shall have the sole Power of Impeachment

Section 3

The Senate of the United States shall be composed of two Senators from each

State chosen by the Legislature thereof for six Years and each Senator shall

have one Vote

Immediately after they shall be assembled in Consequence of the first Election

they shall be divided as equally as may be into three Classes The Seats of the

Senators of the first Class shall be vacated at the Expiration of the second

Year of the second Class at the Expiration of the fourth Year and of the

third Class at the Expiration of the sixth Year so that one third may be

chosen every second Year and if Vacancies happen by Resignation or otherwise

during the Recess of the Legislature of any State the Executive thereof may

make temporary Appointments until the next Meeting of the Legislature which

shall then fill such Vacancies

No person shall be a Senator who shall not have attained to the Age of thirty

Years and been nine Years a Citizen of the United States and who shall not

when elected be an Inhabitant of that State for which he shall be chosen

The Vice President of the United States shall be President of the Senate but

shall have no Vote unless they be equally divided

The Senate shall choose their other Officers and also a President pro tempore

in the absence of the Vice President or when he shall exercise the Office of

President of the United States

The Senate shall have the sole Power to try all Impeachments When sitting for

that Purpose they shall be on Oath or Affirmation When the President of the

United States is tried the Chief Justice shall preside And no Person shall be

convicted without the Concurrence of two thirds