Question
Implement the ADT dictionary by using a binary search tree . Use the ADT dictionary in a word count program. Your class WordCount will take
Implement the ADT dictionary by using a binary search tree. Use the ADT dictionary in a word count program. Your class WordCount will take an input from command line for the name of a text file. This text file will contain words or numbers that are tokenized (separated by whitespace). The code I have included is simply the class heirarchy that needs to be utilized in this program.
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; } }
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; }
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); }
TreeIteratorInterface.java
import java.util.Iterator;
public interface TreeIteratorInterface { public Iterator getPreorderIterator(); public Iterator getInorderIterator(); public Iterator getPostorderIterator(); public Iterator getLevelorderIterator(); }
TreeInterface.java
public interface TreeInterface { public T getRootData(); public int getHeight(); public int getNumberOfNodes(); public boolean isEmpty(); public void clear(); }
SearchTreeInterface.java
import java.util.Iterator;
public interface SearchTreeInterface>
extends TreeInterface{
public boolean contains(T entry);
public T getEntry(T entry);
publlic T add(T newEntry);
public T remove(T entry);
public Iterator getInorderIterator;
}
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();
}
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;
}
public boolean contains(T entry)
{
return getEntry(entry) != null;
}
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;
}
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));
} // end if
}// end if
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;
}
public Iterator getInorderIterator()
{
return getInorderIterator();
} // end getInorderIterator
private class ReturnObject
{
T entry;
public ReturnObject()
{
// do nothing
}
public ReturnObject(T newEntry)
{
entry = newEntry;
}
public void set(T newEntry)
{
entry = newEntry;
}
public T get()
{
return entry;
}
}
}
BstDictonary.java
public class BstDictionary , V> implements DictionaryInterface
{
private SearchTreeInterface> bst;
private int count;
public BstDictionary()
{
bst = new BinarySearchTree();
}
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();
count++;
return result;
}
public V getValue(K key)
{
return bst.get(key);
}
public V remove(K key)
{
Entry findEntry = new Entry<>(key, null);
Entry returnedEntry = bst.remove(findEntry);
V result = null;
if(returnedEntry != null)
result = returnedEntry.getValue();
count--;
return result;
}
public Iterator getKeyIterator()
{
return new KeyIterator();
}
private class KeyIterator implements Iterator
{
Iterator> localIterator;
public KeyIterator()
{
localIterator = bst.getInorderIterator();
}
public boolean hasNext()
{
return localIterator.hasNext();
}
public K next()
{
Entry nextEntry = localIterator.next();
return nextEntry.getKey();
}
public void remove()
{
throw new UnsupportedOperationException();
}
}
private class Entry, T> implements Comparable>
{
private S key;
private T value;
private Entry(S searchKey, T dataValue)
{
key = searchKey;
value = dataValue;
}
public V getValue() {
// TODO Auto-generated method stub
return null;
}
public K getKey() {
return null;
}
public int compareTo(Entry other)
{
return key.compareTo(other.key);
}
} // end Entry
} // end BstDictionary
The output should be like this:
input.text
This 1
is 2
dogs 3
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
