Implement the ADT dictionary by using a binary search tree . Use the ADT diction
ID: 3600828 • Letter: I
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 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
Explanation / Answer
/*To generate a random number */
in java editor
Random r= new Random();
int x=0;
int y=100;
int z=r.nextInt(y-x)+x;
/*binary search tree*/
import java.util;
class treeA
{
ArrayList<Integer>a;
HashMap<Integer,Integer>hash;
public treeA()
{
a=new ArrayList<Integer>();
hash=new HasMap<Integer,Integer>();
void Addition(int x)
{
if(hash.get(x)!=null)
return;
int s=a.size();
a.Addition(x);
has.put(x,s);
}
void delete(int x)
{
Integer i=hash.get(x);
if(i==null)
return;
hash.delete(x);
intsize=a.size();
Integer l=a.get(size-1);
Collections.swap(a,i,size-1);
a.delete(size-1);
hassh.put(l,i);
}
int getRand()
{
Random r = new Random();
int x=r.nextInt(a.size));
return a.get(i);
}
Integer search(int x)
{
return hash.get(x);
}
}
class Main
{
public static void main(String [] args)
{
TreeA ab=new TreeA();
ab.add(20);
ab.add(30);
ab.add(35);
ab.add(40);
ab.add(50);
system.out.println(ab.search(30));
ab.delete(20);
ab.Addition(50);
system.out.println(ab.serach(50));
system.out.println(ab.getRand());
}
}