BELOW IS A JAVA PROGRAM. BUT THE OUTPUT IS NOT RIGHT. SO HELP ME TO MAKE IT RIGH
ID: 3777708 • Letter: B
Question
BELOW IS A JAVA PROGRAM. BUT THE OUTPUT IS NOT RIGHT. SO HELP ME TO MAKE IT RIGHT PLZ.
OUT PUT SHOULD BE:
"Create an implementation of a binary tree using the recursive approach introduced in the chapter. In this approach, each node is a binary tree. Thus a binary tree contains a reference to the element stored at its root as well as references to its left and right subtrees. You may also want to include a reference to its parent." p.741
You need to use the locally implemented binary tree. This means you need to have a "jsjf" subfolder with at least these files: BinaryTreeADT.java, LinkedBinaryTree.java, BinaryTreeNode.java, and the exceptions sub-subfolder.
Test/demonstrate your binary tree by doing the following:
Request file name from user,
Read an infix expression from file,
Build binary expression tree,
Display binary expression tree,
Evaluate binary expression tree,
Display result.
##############################################
Note a typical input file can be found here
##############################################
# Version 0.2, fully parenthesized.
# This is a comment
((9 + 4) * 5) + (4 - (6 + 3))
# Note first expression should evaluate to 60
((42 + ( 10 - 2 )) + ( 5 * 3 )) / 6
# Note second expression should evaluate to 65 / 6 or 10 (integer division)
##############################################
My program is below but the out put is incorrect
##############################################
StringTree.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Stack;
import jsjf.BinaryTreeNode;
import jsjf.LinkedBinaryTree;
public class StringTree extends LinkedBinaryTree<String> {
public StringTree(String rootStr, StringTree leftSubtree, StringTree rightSubtree) {
root = new BinaryTreeNode<String>(rootStr, leftSubtree, rightSubtree);
} // StringTree
public StringTree(File f) {
Stack<StringTree> leftStack = new Stack<StringTree>(), rightStack = new Stack<StringTree>();
// stacks of left and right subtrees of nodes
Scanner scan;
// scanner for reading from the file
String nodeType,
nodeStr;
// string contained in the current node
boolean hasLeftChild, hasRightChild;
// true if the current node has a left or right child
StringTree leftSubtree, rightSubtree,
// left and right subtrees of the current node
subtree;
// subtree having the current node as its root
// Create a scanner for reading from the file.
try {
scan = new Scanner(f);
} catch (FileNotFoundException e) {
System.out.println(e.getMessage());
root = null;
System.out.println(" "+"The program has terminated......");
System.exit(0);
return;
}
// Read the file and build a tree from the bottom up.
while (scan.hasNext()) {
// Input information about a tree node.
nodeType = scan.next();
hasLeftChild = (scan.next().equalsIgnoreCase("y"));
hasRightChild = (scan.next().equalsIgnoreCase("y"));
nodeStr = scan.next();
// Determine the left and right subtrees of the subtree
// having the node as its root.
if (hasLeftChild)
leftSubtree = leftStack.pop();
else
leftSubtree = null;
if (hasRightChild)
rightSubtree = rightStack.pop();
else
rightSubtree = null;
// Create the subtree having the node as its root.
subtree = new StringTree(nodeStr, leftSubtree, rightSubtree);
// Push the subtree onto the appropriate stack or finish
// construction of the whole tree.
if (nodeType.equalsIgnoreCase("L"))
leftStack.push(subtree);
else if (nodeType.equalsIgnoreCase("R"))
rightStack.push(subtree);
else {
root = subtree.root;
break;
}
} // while
} // StringTree
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
// scanner to read keyboard input
String name;
// name of a tree description file
File f;
// the corresponding file object
StringTree tree;
// tree constructed from the file
// Input a tree description file name and create a
// corresponding file object.
System.out.print("Enter a tree description file name: ");
name = scan.nextLine();
scan.close();
f = new File(name);
// Create a tree as described by the file.
tree = new StringTree(f);
// Display the tree.
System.out.print(tree.toString());
// Find and display the tree's height.
System.out.println("The tree's height is: " + tree.getHeight());
// List the nodes in the order visited in a post-order
// traversal.
Iterator<String> post = tree.iteratorPostOrder();
System.out.print("Traversed in PostOrder: ");
while (post.hasNext()) {
System.out.print(post.next() + " ");
}
//Printing terminating message
System.out.println(" "+" "+"The program has terminated......");
} // main
} // class StringTree
// ***************************************************************
LinkedBinaryTree.java
package jsjf;
import java.util.*;
import jsjf.exceptions.*;
public class LinkedBinaryTree<T> implements BinaryTreeADT<T>, Iterable<T> {
protected BinaryTreeNode<T> root;
protected int modCount = 0;
public LinkedBinaryTree() {
root = null;
} // LinkedBinaryTree
public LinkedBinaryTree(T element) {
root = new BinaryTreeNode<T>(element);
} // LinkedBinaryTree
public LinkedBinaryTree(T element, LinkedBinaryTree<T> left, LinkedBinaryTree<T> right) {
root = new BinaryTreeNode<T>(element);
root.setLeft(left.root);
root.setRight(right.root);
} // LinkedBinaryTree
public T getRootElement() throws EmptyCollectionException {
if (root == null) {
throw new EmptyCollectionException("There is no element at root! There must be a root element to"
+ "create a tree.");
} else {
return root.getElement();
}
} // getRootElement
protected BinaryTreeNode<T> getRootNode() throws EmptyCollectionException {
if(root == null){
throw new EmptyCollectionException("There is no node at root! There must be a root node to"
+ "create a tree.");
} else{
return root;
}
} // getRootNode
public LinkedBinaryTree<T> getLeft() {
BinaryTreeNode<T> leftChild;
LinkedBinaryTree<T> leftSubtree;
if (root == null)
return null;
leftChild = root.getLeft();
if (leftChild == null)
return null;
leftSubtree = new LinkedBinaryTree<T>();
leftSubtree.root = leftChild;
return leftSubtree;
} // getLeft
public LinkedBinaryTree<T> getRight() {
BinaryTreeNode<T> rightChild;
LinkedBinaryTree<T> rightSubtree;
if (root == null)
return null;
rightChild = root.getRight();
if (rightChild == null)
return null;
rightSubtree = new LinkedBinaryTree<T>();
rightSubtree.root = rightChild;
return rightSubtree;
} // getRight
public boolean isEmpty() {
return (root == null);
} // isEmpty
public int size() {
return 0;
} // size
public int getHeight() {
if (this.isEmpty()) {
System.out.println(" "+"Check file for formatting errors.....");
System.out.println(" "+"The program has terminated......");
System.exit(0);
return 0;
} else {
BinaryTreeNode<T> node = root;
return height(node);
}
} // getHeight
private int height(BinaryTreeNode<T> node) {
if (node == null){
return -1;
}
int leftSub = height(node.left);
int rightSub = height(node.right);
if (leftSub > rightSub){
return leftSub + 1;
}
else{
return rightSub + 1;
}
} // height
public boolean contains(T targetElement) {
return false;
} // contains
public T find(T targetElement) throws ElementNotFoundException {
BinaryTreeNode<T> current = findNode(targetElement, root);
if (current == null)
throw new ElementNotFoundException("LinkedBinaryTree");
return (current.getElement());
} // find
private BinaryTreeNode<T> findNode(T targetElement, BinaryTreeNode<T> next) {
if (next == null)
return null;
if (next.getElement().equals(targetElement))
return next;
BinaryTreeNode<T> temp = findNode(targetElement, next.getLeft());
if (temp == null)
temp = findNode(targetElement, next.getRight());
return temp;
} // findNode
public String toString() {
return toString(root, 0);
} // toString
// Recursive helper method for the toString method.
private String toString(BinaryTreeNode<T> node, int indent) {
String result = "";
BinaryTreeNode<T> leftChild, rightChild;
if (node == null)
return "";
rightChild = node.getRight();
if (rightChild != null)
result += toString(rightChild, indent + 1);
for (int k = 1; k <= indent; k++)
result += " ";
result += node.getElement() + " ";
leftChild = node.getLeft();
if (leftChild != null)
result += toString(leftChild, indent + 1);
return result;
} // toString
public Iterator<T> iterator() {
return iteratorInOrder();
} // iterator
public Iterator<T> iteratorInOrder() {
ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
inOrder(root, tempList);
return new TreeIterator(tempList.iterator());
} // iteratorInOrder
protected void inOrder(BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) {
if (node != null) {
inOrder(node.getLeft(), tempList);
tempList.addToRear(node.getElement());
inOrder(node.getRight(), tempList);
}
} // inOrder
public Iterator<T> iteratorPreOrder() {
return null;
} // iteratorPreOrder
protected void preOrder(BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) {
// To be completed as a Programming Project
} // preOrder
public Iterator<T> iteratorPostOrder() {
ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
postOrder(root, tempList);
return new TreeIterator(tempList.iterator());
} // iteratorPostOrder
protected void postOrder(BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) {
if (node != null) {
postOrder(node.getLeft(), tempList);
postOrder(node.getRight(), tempList);
tempList.addToRear(node.getElement());
}
} // postOrder
public Iterator<T> iteratorLevelOrder() {
ArrayUnorderedList<BinaryTreeNode<T>> nodes = new ArrayUnorderedList<BinaryTreeNode<T>>();
ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
BinaryTreeNode<T> current;
nodes.addToRear(root);
while (!nodes.isEmpty()) {
current = nodes.removeFirst();
if (current != null) {
tempList.addToRear(current.getElement());
if (current.getLeft() != null)
nodes.addToRear(current.getLeft());
if (current.getRight() != null)
nodes.addToRear(current.getRight());
} else
tempList.addToRear(null);
}
return new TreeIterator(tempList.iterator());
} // iteratorLevelOrder
private class TreeIterator implements Iterator<T> {
private int expectedModCount;
private Iterator<T> iter;
public TreeIterator(Iterator<T> iter) {
this.iter = iter;
expectedModCount = modCount;
} // TreeIterator
public boolean hasNext() throws ConcurrentModificationException {
if (!(modCount == expectedModCount))
throw new ConcurrentModificationException();
return (iter.hasNext());
} // hasNext
public T next() throws NoSuchElementException {
if (hasNext())
return (iter.next());
else
throw new NoSuchElementException();
} // next
public void remove() {
throw new UnsupportedOperationException();
} // remove
} // class TreeIterator
} // class LinkedBinaryTree<T>
// ***************************************************************
BinaryTreeADT.java
package jsjf;
import java.util.Iterator;
public interface BinaryTreeADT<T>
{
public T getRootElement();
public boolean isEmpty();
public int size();
public boolean contains(T targetElement);
public T find(T targetElement);
public String toString();
public Iterator<T> iterator();
public Iterator<T> iteratorInOrder();
public Iterator<T> iteratorPreOrder();
public Iterator<T> iteratorPostOrder();
public Iterator<T> iteratorLevelOrder();
}
BinaryTreeNode.java
package jsjf;
public class BinaryTreeNode<T>
{
protected T element;
protected BinaryTreeNode<T> left, right;
public BinaryTreeNode(T obj)
{
element = obj;
left = null;
right = null;
}
public BinaryTreeNode(T obj, LinkedBinaryTree<T> left, LinkedBinaryTree<T> right)
{
element = obj;
if (left == null)
this.left = null;
else
this.left = left.getRootNode();
if (right == null)
this.right = null;
else
this.right = right.getRootNode();
}
public int numChildren()
{
int children = 0;
if (left != null)
children = 1 + left.numChildren();
if (right != null)
children = children + 1 + right.numChildren();
return children;
}
public T getElement()
{
return element;
}
public BinaryTreeNode<T> getRight()
{
return right;
}
public void setRight(BinaryTreeNode<T> node)
{
right = node;
}
public BinaryTreeNode<T> getLeft()
{
return left;
}
public void setLeft(BinaryTreeNode<T> node)
{
left = node;
}
}
EmptyCollectionException.java
package jsjf.exceptions;
public class EmptyCollectionException extends RuntimeException
{
private static final long serialVersionUID = 1L;
public EmptyCollectionException (String collection)
{
super ("The " + collection + " is empty.");
}
}
ElementNotFoundException.java
package jsjf.exceptions;
public class ElementNotFoundException extends RuntimeException
{
private static final long serialVersionUID = 1L;
public ElementNotFoundException (String collection)
{
super ("The target element is not in this " + collection);
}
}
ArrayUnorderedList.java
package jsjf;
import jsjf.exceptions.*;
public class ArrayUnorderedList<T> extends ArrayList<T>
implements UnorderedListADT<T>
{
public ArrayUnorderedList()
{
super();
}
public ArrayUnorderedList(int initialCapacity)
{
super(initialCapacity);
}
public void addToFront(T element)
{
if (size() == list.length)
expandCapacity();
// shift elements up one
for (int scan=rear; scan > 0; scan--)
list[scan] = list[scan-1];
list[0] = element;
rear++;
modCount++;
}
public void addToRear(T element)
{
if (size() == list.length)
expandCapacity();
list[rear] = element;
rear++;
modCount++;
}
public void addAfter(T element, T target)
{
if (size() == list.length)
expandCapacity();
int scan = 0;
// find the insertion point
while (scan < rear && !target.equals(list[scan]))
scan++;
if (scan == rear)
throw new ElementNotFoundException("UnorderedList");
scan++;
// shift elements up one
for (int shift=rear; shift > scan; shift--)
list[shift] = list[shift-1];
// insert element
list[scan] = element;
rear++;
modCount++;
}
}
UnorderedListADT.java
package jsjf;
public interface UnorderedListADT<T> extends ListADT<T>
{
public void addToFront(T element);
public void addToRear(T element);
public void addAfter(T element, T target);
}
ListADT.java
package jsjf;
import java.util.Iterator;
public interface ListADT<T> extends Iterable<T>
{
public T removeFirst();
public T removeLast();
public T remove(T element);
public T first();
public T last();
public boolean contains(T target);
public boolean isEmpty();
public int size();
public Iterator<T> iterator();
public String toString();
}
ArrayList.java
package jsjf;
import jsjf.exceptions.*;
import java.util.*;
public abstract class ArrayList<T> implements ListADT<T>, Iterable<T>
{
private final static int DEFAULT_CAPACITY = 100;
private final static int NOT_FOUND = -1;
protected int rear;
protected T[] list;
protected int modCount;
public ArrayList()
{
this(DEFAULT_CAPACITY);
}
// Added.
@SuppressWarnings("unchecked")
public ArrayList(int initialCapacity)
{
rear = 0;
list = (T[])(new Object[initialCapacity]);
modCount = 0;
}
protected void expandCapacity()
{
list = Arrays.copyOf(list, list.length*2);
}
public T removeLast() throws EmptyCollectionException
{
if (isEmpty())
throw new EmptyCollectionException("ArrayList");
T result;
rear--;
result = list[rear];
list[rear] = null;
modCount++;
return result;
}
public T removeFirst() throws EmptyCollectionException
{
if (isEmpty())
throw new EmptyCollectionException("ArrayList");
T result = list[0];
rear--;
/** shift the elements */
for (int scan=0; scan < rear; scan++)
list[scan] = list[scan+1];
list[rear] = null;
modCount++;
return result;
}
public T remove(T element)
{
T result;
int index = find(element);
if (index == NOT_FOUND)
throw new ElementNotFoundException("ArrayList");
result = list[index];
rear--;
// shift the appropriate elements
for (int scan=index; scan < rear; scan++)
list[scan] = list[scan+1];
list[rear] = null;
modCount++;
return result;
}
public T first() throws EmptyCollectionException
{
if (isEmpty())
throw new EmptyCollectionException("ArrayList");
return list[0];
}
public T last() throws EmptyCollectionException
{
if (isEmpty())
throw new EmptyCollectionException("ArrayList");
return list[rear-1];
}
public boolean contains(T target)
{
return (find(target) != NOT_FOUND);
}
private int find(T target)
{
int scan = 0;
int result = NOT_FOUND;
if (!isEmpty())
while (result == NOT_FOUND && scan < rear)
if (target.equals(list[scan]))
result = scan;
else
scan++;
return result;
}
public boolean isEmpty()
{
return (rear == 0);
}
public int size()
{
return rear;
}
public String toString()
{
String result = "";
for (int scan=0; scan < rear; scan++)
result = result + list[scan] + " ";
return result;
}
public Iterator<T> iterator()
{
return new ArrayListIterator();
}
private class ArrayListIterator implements Iterator<T>
{
int iteratorModCount;
int current;
public ArrayListIterator()
{
iteratorModCount = modCount;
current = 0;
}
public boolean hasNext() throws ConcurrentModificationException
{
if (iteratorModCount != modCount)
throw new ConcurrentModificationException();
return (current < rear);
}
public T next() throws ConcurrentModificationException
{
if (!hasNext())
throw new NoSuchElementException();
current++;
return list[current - 1];
}
public void remove() throws UnsupportedOperationException
{
throw new UnsupportedOperationException();
}
}
}
Explanation / Answer
import java.util.Scanner;
/* Class BTNode */
class BTNode
{
BTNode left, right;
int data;
/* Constructor */
public BTNode()
{
left = null;
right = null;
data = 0;
}
/* Constructor */
public BTNode(int n)
{
left = null;
right = null;
data = n;
}
/* Function to set left node */
public void setLeft(BTNode n)
{
left = n;
}
/* Function to set right node */
public void setRight(BTNode n)
{
right = n;
}
/* Function to get left node */
public BTNode getLeft()
{
return left;
}
/* Function to get right node */
public BTNode getRight()
{
return right;
}
/* Function to set data to node */
public void setData(int d)
{
data = d;
}
/* Function to get data from node */
public int getData()
{
return data;
}
}
/* Class BT */
class BT
{
private BTNode root;
/* Constructor */
public BT()
{
root = null;
}
/* Function to check if tree is empty */
public boolean isEmpty()
{
return root == null;
}
/* Functions to insert data */
public void insert(int data)
{
root = insert(root, data);
}
/* Function to insert data recursively */
private BTNode insert(BTNode node, int data)
{
if (node == null)
node = new BTNode(data);
else
{
if (node.getRight() == null)
node.right = insert(node.right, data);
else
node.left = insert(node.left, data);
}
return node;
}
/* Function to count number of nodes */
public int countNodes()
{
return countNodes(root);
}
/* Function to count number of nodes recursively */
private int countNodes(BTNode r)
{
if (r == null)
return 0;
else
{
int l = 1;
l += countNodes(r.getLeft());
l += countNodes(r.getRight());
return l;
}
}
/* Function to search for an element */
public boolean search(int val)
{
return search(root, val);
}
/* Function to search for an element recursively */
private boolean search(BTNode r, int val)
{
if (r.getData() == val)
return true;
if (r.getLeft() != null)
if (search(r.getLeft(), val))
return true;
if (r.getRight() != null)
if (search(r.getRight(), val))
return true;
return false;
}
/* Function for inorder traversal */
public void inorder()
{
inorder(root);
}
private void inorder(BTNode r)
{
if (r != null)
{
inorder(r.getLeft());
System.out.print(r.getData() +" ");
inorder(r.getRight());
}
}
/* Function for preorder traversal */
public void preorder()
{
preorder(root);
}
private void preorder(BTNode r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
/* Function for postorder traversal */
public void postorder()
{
postorder(root);
}
private void postorder(BTNode r)
{
if (r != null)
{
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() +" ");
}
}
}
/* Class BinaryTree */
public class BinaryTree
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of BT */
BT bt = new BT();
/* Perform tree operations */
System.out.println("Binary Tree Test ");
char ch;
do
{
System.out.println(" Binary Tree Operations ");
System.out.println("1. insert ");
System.out.println("2. search");
System.out.println("3. count nodes");
System.out.println("4. check empty");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
bt.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to search");
System.out.println("Search result : "+ bt.search( scan.nextInt() ));
break;
case 3 :
System.out.println("Nodes = "+ bt.countNodes());
break;
case 4 :
System.out.println("Empty status = "+ bt.isEmpty());
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display tree */
System.out.print(" Post order : ");
bt.postorder();
System.out.print(" Pre order : ");
bt.preorder();
System.out.print(" In order : ");
bt.inorder();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.