Finish the implementation of this Binary Search Tree and BSTDictionary, then wri
ID: 3601584 • Letter: F
Question
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<T> {
private T data;
private BinaryNode<T> leftChild, rightChild;
public BinaryNode() {
this(null);
}
public BinaryNode(T data) {
this(data, null, null);
}
public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) {
this.data = data;
leftChild = left;
setRightChild(right);
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public BinaryNode<T> getLeftChild(){
return leftChild;
}
public void setLeftChild(BinaryNode<T> left) {
leftChild = left;
}
public BinaryNode<T> getRightChild() {
return rightChild;
}
public void setRightChild(BinaryNode<T> right) {
this.rightChild = right;
}
public boolean hasLeftChild() {
return leftChild != null;
}
public boolean hasRightChild() {
return rightChild != null;
}
public boolean isLeaf() {
return (!hasLeftChild() && !hasRightChild());
}
public BinaryNode<T> copy(){
BinaryNode<T> newRoot = new BinaryNode<T>(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<T> 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<T> 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<T extends Comparable<? super T>>
extends BinaryTree<T>
implements SearchTreeInterface<T>{
public BinarySearchTree(){
super();
}
public BinarySearchTree(T rootEntry){
super();
setRootNode(new BinaryNode<T> (rootEntry));
}
public void setTree(T rootData){
throw new UnsupportedOperationException();
}
public void setTree(T rootData, BinaryTreeInterface<T> leftTree, BinaryTreeInterface<T> 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<T> 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<T> 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<T> newRoot = removeEntry(getRootNode(), entry, oldEntry);
setRootNode(newRoot);
return oldEntry.get();
}
private BinaryNode<T> removeEntry(BinaryNode<T> 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<T> leftChild = rootNode.getLeftChild();
BinaryNode<T> subTreeRoot = removeEntry(leftChild, entry, oldEntry);
rootNode.setLeftChild(subTreeRoot);
}
else{
BinaryNode<T> rightChild = rootNode.getRightChild();
rootNode.setRightChild(removeEntry(rightChild, entry, oldEntry));
}
}
return rootNode;
}
private BinaryNode<T> removeFromRoot(BinaryNode<T> rootNode){
if(rootNode.hasLeftChild() && rootNode.hasRightChild()){
BinaryNode<T> leftSubtreeRoot = rootNode.getLeftChild();
BinaryNode<T> 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<T> findLargest(BinaryNode<T> rootNode){
if(rootNode.hasRightChild())
rootNode = findLargest(rootNode.getRightChild());
return rootNode;
}
private BinaryNode<T> removeLargest(BinaryNode<T> rootNode){
if(rootNode.hasRightChild()){
BinaryNode<T> 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<T> implements BinaryTreeInterface<T> {
private BinaryNode<T> root;
public BinaryTree() {
root = null;
}
public BinaryTree(T rootData) {
root = new BinaryNode<T>(rootData);
}
public BinaryTree(T rootData, BinaryTree<T> leftTree, BinaryTree<T> rightTree) {
privateSetTree(rootData, leftTree, rightTree);
}
public void setTree(T rootData) {
root = new BinaryNode<T>(rootData);
}
public void setTree(T rootData, BinaryTree<T> left, BinaryTree<T> right) {
privateSetTree(rootData, left, right);
}
private void privateSetTree(T rootData, BinaryTree<T> left, BinaryTree<T> 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<T> getRootNode() {
return root;
}
protected void setRootData(T rootData){
root.setData(rootData);
}
protected void setRootNode(BinaryNode<T> rootNode){
root = rootNode;
}
public Iterator<T> getPreorderIterator() {
throw new UnsupportedOperationException("Preorder not supported.");
}
public Iterator<T> getInorderIterator() {
throw new UnsupportedOperationException("Inorder not supported.");
}
public Iterator<T> getPostorderIterator() {
return new PostorderIterator();
}
public Iterator<T> getLevelorderIterator() {
throw new UnsupportedOperationException("Level Order not supported.");
}
private class PostorderIterator implements Iterator<T> {
private Stack<BinaryNode<T>> nodeStack;
private BinaryNode<T> current;
public PostorderIterator() {
nodeStack = new Stack<>();
current = root;
populateStack(current);
}
private void populateStack(BinaryNode<T> 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<T> extends TreeInterface<T>, TreeIteratorInterface<T>{
public void setTree(T rootData);
public void setTree(T rootData, BinaryTree<T> left, BinaryTree<T> right);
}
BSTDictionary.java
import java.util.Iterator;
public class BSTDictionary<K extends Comparable<? super K>,V>
implements DictionaryInterface<K,V>{
private SearchTreeInterface<Entry<K,V>> bst;
public BSTDictionary(){
bst = new BinarySearchTree<>();
}
private class Entry<S extends Comparable<? super S>,T>
implements Comparable<Entry<S,T>>
{
private S key;
private T value;
private Entry(S searchKey, T dataValue){
key = searchKey;
value = dataValue;
}
public int compareTo(Entry<S,T> 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<K, V> newEntry = new Entry<>(key, value);
Entry<K, V> 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<K> 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<K,V>{
public V add(K key, V value);
public V remove(K key);
public V getValue(K key);
public boolean contains(K key);
public Iterator<K> getKeyIterator();
public boolean isEmpty();
public int getSize();
public void clear();
}
SearchTreeInterface.java
import java.util.Iterator;
public interface SearchTreeInterface<T extends Comparable<? super T>>
extends TreeInterface<T>{
public boolean contains(T entry);
public T getEntry(T entry);
public T add(T newEntry);
public T remove(T entry);
public Iterator<T> getInorderIterator;
}
TreeInterface.java
public interface TreeInterface<T> {
public T getRootData();
public int getHeight();
public int getNumberOfNodes();
public boolean isEmpty();
public void clear();
}
TreeIteratorInterface.java
import java.util.Iterator;
public interface TreeIteratorInterface<T> {
public Iterator<T> getPreorderIterator();
public Iterator<T> getInorderIterator();
public Iterator<T> getPostorderIterator();
public Iterator<T> 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
Explanation / Answer
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<T> getRootNode() {
return root;
}
protected void setRootData(T rootData){
root.setData(rootData);
}
protected void setRootNode(BinaryNode<T> rootNode){
root = rootNode;
}
public Iterator<T> getPreorderIterator() {
throw new UnsupportedOperationException("Preorder not supported.");
}
public Iterator<T> getInorderIterator() {
throw new UnsupportedOperationException("Inorder not supported.");
}
public Iterator<T> getPostorderIterator() {
return new PostorderIterator();
}
public Iterator<T> getLevelorderIterator() {
throw new UnsupportedOperationException("Level Order not supported.");
}
private class PostorderIterator implements Iterator<T> {
private Stack<BinaryNode<T>> nodeStack;
private BinaryNode<T> current;
public PostorderIterator() {
nodeStack = new Stack<>();
current = root;
populateStack(current);
}
private void populateStack(BinaryNode<T> 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() {
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.