Implement the ADT dictionary by using a binary search tree. Use the ADT dictiona
ID: 3600720 • 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. For this homework, the text file contains words or numbers that are tokenized (separated by whitespace).
I already have the following interfaces/classes made:
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();
}
//implements contains, getEntry, add and remove here
}
etc.
Explanation / Answer
import java.util.Scanner;
class BSTNode
{
BSTNode left, right;
int data;
public BSTNode()
{
left = null;
right = null;
data = 0;
}
public BSTNode(int n)
{
left = null;
right = null;
data = n;
}
public void setLeft(BSTNode n)
{
left = n;
}
public void setRight(BSTNode n)
{
right = n;
}
public BSTNode getLeft()
{
return left;
}
public BSTNode getRight()
{
return right;
}
public void setData(int d)
{
data = d;
}
public int getData()
{
return data;
}
}
// Class BST
class BST
{
private BSTNode root;
// Constructor
public BST()
{
root = null;
}
public boolean isEmpty()
{
return root == null;
}
public void insert(int data)
{
root = insert(root, data);
}
private BSTNode insert(BSTNode node, int data)
{
if (node == null)
node = new BSTNode(data);
else
{
if (data <= node.getData())
node.left = insert(node.left, data);
else
node.right = insert(node.right, data);
}
return node;
}
public void delete(int k)
{
if (isEmpty())
System.out.println("Tree Empty");
else if (search(k) == false)
System.out.println("Sorry "+ k +" is not present");
else
{
root = delete(root, k);
System.out.println(k+ " deleted from the tree");
}
}
private BSTNode delete(BSTNode root, int k)
{
BSTNode p, p2, n;
if (root.getData() == k)
{
BSTNode lt, rt;
lt = root.getLeft();
rt = root.getRight();
if (lt == null && rt == null)
return null;
else if (lt == null)
{
p = rt;
return p;
}
else if (rt == null)
{
p = lt;
return p;
}
else
{
p2 = rt;
p = rt;
while (p.getLeft() != null)
p = p.getLeft();
p.setLeft(lt);
return p2;
}
}
if (k < root.getData())
{
n = delete(root.getLeft(), k);
root.setLeft(n);
}
else
{
n = delete(root.getRight(), k);
root.setRight(n);
}
return root;
}
public int countNodes()
{
return countNodes(root);
}
private int countNodes(BSTNode r)
{
if (r == null)
return 0;
else
{
int l = 1;
l += countNodes(r.getLeft());
l += countNodes(r.getRight());
return l;
}
}
public boolean search(int val)
{
return search(root, val);
}
private boolean search(BSTNode r, int val)
{
boolean found = false;
while ((r != null) && !found)
{
int rval = r.getData();
if (val < rval)
r = r.getLeft();
else if (val > rval)
r = r.getRight();
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}
public void inorder()
{
inorder(root);
}
private void inorder(BSTNode r)
{
if (r != null)
{
inorder(r.getLeft());
System.out.print(r.getData() +" ");
inorder(r.getRight());
}
}
public void preorder()
{
preorder(root);
}
private void preorder(BSTNode r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
public void postorder()
{
postorder(root);
}
private void postorder(BSTNode r)
{
if (r != null)
{
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() +" ");
}
}
}
// Class BinarySearchTree
public class BinarySearchTree
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
// Creating object of BST
BST bst = new BST();
System.out.println("Binary Search Tree Test ");
char ch;
// Perform tree operations
do
{
System.out.println(" Binary Search Tree Operations ");
System.out.println("1. insert ");
System.out.println("2. delete");
System.out.println("3. search");
System.out.println("4. count nodes");
System.out.println("5. check empty");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
bst.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to delete");
bst.delete( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to search");
System.out.println("Search result : "+ bst.search( scan.nextInt() ));
break;
case 4 :
System.out.println("Nodes = "+ bst.countNodes());
break;
case 5 :
System.out.println("Empty status = "+ bst.isEmpty());
break;
default :
System.out.println("Wrong Entry ");
break;
}
// Display tree
System.out.print(" Post order : ");
bst.postorder();
System.out.print(" Pre order : ");
bst.preorder();
System.out.print(" In order : ");
bst.inorder();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}