home / study / engineering / computer science / computer science questions and a

ID: 3599814 • Letter: H

Question

home / study / engineering / computer science / computer science questions and answers / implement the adt dictionary by using a binary search tree. use the adt dictionary in a word ...

Your question has been posted.

We'll notify you when a Chegg Expert has answered. Post another question.

Question: Implement the ADT dictionary by using a binary search tree. Use the ADT dictionary in a word coun...

Edit 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<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;
   }



}

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;
   }

   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);

}

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();

}

TreeInterface.java

public interface TreeInterface<T> {

   public T getRootData();
   public int getHeight();
   public int getNumberOfNodes();
   public boolean isEmpty();
   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);

publlic T add(T newEntry);

public T remove(T entry);

public Iterator<T> getInorderIterator;

}

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();

}

//implements contains, getEntry, add and remove here

}

Explanation / Answer