Java Program Help: I have a LinkedBinaryTree class that will follow the question

Question

Java Program Help: I have a LinkedBinaryTree class that will follow the question. In that class, Add a method named eulerTourBinary as described on page 349 of the textbook. Write this method so that it will print out a traditional parenthesized arithmetic expression. I don't understand because it's not a code fragment.

Your program should: - Ask the user to enter the absolute path and filename (as a single String) of the file that contains a list of arithmetic expressions. Each expression will be on a single line in the input text file delimited by and end of line character. - Read arithmetic expressions from an input file until the EOF is reached. o See file format and example at end of assignment. - For each expression your program should: o Print out the expression that was read from the file. o Determine if the expression is valid. Print an invalid expression message for invalid expressions. For each valid expression • Represent the expression in a binary expression tree • Evaluate the expression and display the results of the evaluation • Display the contents of the binary expression tree using: o A preorder traversal o An inorder traversal o A postorder traversal o The eulerTourBinary method that you added for this Lab • Each traversal should be appropriately labelled and print out on a single line Summary, one LinkedBinaryTree class and one Client Class

Here's the LinkedBinaryTree Class:

import java.util.Iterator;

import java.util.LinkedList;

import java.util.Queue;

public class LinkedBinaryTree extends AbstractBinaryTree

{ static class Node implements Position

{ //declaring nodes and variables private E element;

private Node left;

private Node right;

private Node parent;

public Node(E e, Node above, Node leftChild, Node rightChild)

{ element = e; parent = above; left = leftChild; right = rightChild; }

//setters and getters for the elements of the tree

public E getElement()

{ return element; }

public Node getParent()

{ return parent; }

public Node getLeft()

{ return left; }

public Node getRight()

{ return right; }

public void setElement(E e)

{ element = e; }

public void setParent(Node parentNode)

{ parent = parentNode; }

public void setLeft(Node leftChild)

{ left = leftChild; }

public void setRight(Node rightChild)

{ right = rightChild; }

}

protected Node createNode(E e, Node parent,

Node left, Node right)

{

return new Node(e, parent, left, right); }

protected Node root = null;

private int size = 0;

public LinkedBinaryTree() { }

protected Node validate(Position p) throws IllegalArgumentException {

if (!(p instanceof Node))

{ throw new IllegalArgumentException("Not valid position type");

}

Node node = (Node) p;

if (node.getParent() == node) {

throw new IllegalArgumentException("p is no longer in the tree");

}

return node; }

public int size()

{ return size; }

@Override

public Iterator iterator()

{

return null; }

@Override

public Iterable> positions()

{ return null; }

public Position root()

{ return root; }

//methods declaring argument exceptions to maintain specific values in the trees

public Position parent(Position p) throws IllegalArgumentException

{ Node node = validate(p);

return node.getParent(); }

public Position left(Position p) throws IllegalArgumentException {

Node node = validate(p);

return node.getLeft(); }

public Position right(Position p) throws IllegalArgumentException {

Node node = validate(p);

return node.getRight();

} public Position addRoot(E e) throws IllegalStateException {

if (!isEmpty()) {

throw new IllegalStateException("Tree is not empty"); }

root = createNode(e, null, null, null);

size = 1; return root; }

//add method in order to add a left child to the tree

public Position addLeft(Position p, E e)

throws IllegalArgumentException {

Node parent = validate(p);

if (parent.getLeft() != null) {

throw new IllegalArgumentException("p already has a left child");

} Node child = createNode(e, parent, null, null);

parent.setLeft(child);

size++;

return child; }

//add method in order to add a right child to the tree

public Position addRight(Position p, E e) throws IllegalArgumentException {

Node parent = validate(p);

if (parent.getRight() != null) {

throw new IllegalArgumentException("p already has a right child");

}

Node child = createNode(e, parent, null, null);

parent.setRight(child);

size++;

return child; }

public E set(Position p, E e) throws IllegalArgumentException

{ Node node = validate(p);

E temp = node.getElement();

node.setElement(e);

return temp;

}

public void attach(Position p, LinkedBinaryTree t1,

LinkedBinaryTree t2) throws IllegalArgumentException {

Node node = validate(p);

if (isInternal(p)) {

throw new IllegalArgumentException("p must be a leaf");

//indicating p as a leaf

}

size += t1.size() + t2.size();

if (!t1.isEmpty())

{ t1.root.setParent(node);

node.setLeft(t1.root);

t1.root = null;

t1.size = 0;

}

if (!t2.isEmpty()) {

t2.root.setParent(node);

node.setRight(t2.root);

t2.root = null;

t2.size = 0; } }

//removal method of a node from the tree traversal

public E remove(Position p) throws IllegalArgumentException {

Node node = validate(p);

if (numChildren(p) == 2) {

throw new IllegalArgumentException("p has two children");

}

Node child = (node.getLeft() != null ? node.getLeft() : node.getRight());

if (child != null) {

child.setParent(node.getParent());

}

if (node == root) {

root = child;

} else

{ Node parent = node.getParent()

; if (node == parent.getLeft())

{ parent.setLeft(child); } else

{ parent.setRight(child); }

}

size--;

E temp = node.getElement();

node.setElement(null);

node.setLeft(null);

node.setRight(null);

node.setParent(node);

return temp; }

//Tree Traversal Methods

//Defining inOrder Method

public void inOrder(Node root)

{ if (root != null) {

inOrder(root.left);

System.out.printf("%s ", root.getElement());

inOrder(root.right); } }

//Defining preOrder method

public void preOrder(Node root)

{ if (root != null)

{ System.out.printf("%s ", root.getElement());

inOrder(root.left);

inOrder(root.right); } }

//Defining postOrder Method

public void postOrder(Node root)

{ if (root != null) {

inOrder(root.left);

inOrder(root.right);

System.out.printf("%s ", root.getElement()); } }

//Defining BreathFirst method

public void BreathFirst(Node root)

{ Queue> queue = new LinkedList>();

if (root == null)

{ return; }

queue.clear();

queue.add(root);

while (!queue.isEmpty()) {

Node node = queue.remove();

System.out.print(node.element + " ");

if (node.left != null) {

queue.add(node.left); }

if (node.right != null)

{ queue.add(node.right); } } }

//parethesize method for traversal in client class

public void parenthesize(Tree T, Position p) {

System.out.print(p.getElement());

if (T.isInternal(p)) {

boolean firstTime = true;

for (Position c : T.children(p))

{ System.out.print((firstTime ? " (" : ", "));

firstTime = false;

parenthesize(T, c); }

System.out.print(")"); } } }

Explanation / Answer

//******************************************************************* // LinkedBinaryTree.java Java Foundations // // Implements a binary tree using a linked representation. //******************************************************************* package javafoundations; import java.util.Iterator; import javafoundations.*; import javafoundations.exceptions.*; public class LinkedBinaryTree implements BinaryTree { protected BTNode root; //----------------------------------------------------------------- // Creates an empty binary tree. //----------------------------------------------------------------- public LinkedBinaryTree() { root = null; } //----------------------------------------------------------------- // Creates a binary tree with the specified element as its root. //----------------------------------------------------------------- public LinkedBinaryTree (T element) { root = new BTNode(element); } //----------------------------------------------------------------- // Creates a binary tree with the two specified subtrees. //----------------------------------------------------------------- public LinkedBinaryTree (T element, LinkedBinaryTree left, LinkedBinaryTree right) { root = new BTNode(element); root.setLeft(left.root); root.setRight(right.root); } //----------------------------------------------------------------- // Returns the element stored in the root of the tree. Throws an // EmptyCollectionException if the tree is empty. //----------------------------------------------------------------- public T getRootElement() { if (root == null) throw new EmptyCollectionException ("Get root operation " + "failed. The tree is empty."); return root.getElement(); } //----------------------------------------------------------------- // Returns the left subtree of the root of this tree. //----------------------------------------------------------------- public LinkedBinaryTree getLeft() { if (root == null) throw new EmptyCollectionException ("Get left operation " + "failed. The tree is empty."); LinkedBinaryTree result = new LinkedBinaryTree(); result.root = root.getLeft(); return result; } //----------------------------------------------------------------- // Returns the element in this binary tree that matches the // specified target. Throws a ElementNotFoundException if the // target is not found. //----------------------------------------------------------------- public T find (T target) { BTNode node = null; if (root != null) node = root.find(target); if (node == null) throw new ElementNotFoundException("Find operation failed. " + "No such element in tree."); return node.getElement(); } //----------------------------------------------------------------- // Returns the number of elements in this binary tree. //----------------------------------------------------------------- public int size() { int result = 0; if (root != null) result = root.count(); return result; } //----------------------------------------------------------------- // Populates and returns an iterator containing the elements in // this binary tree using an inorder traversal. //----------------------------------------------------------------- public Iterator inorder() { ArrayIterator iter = new ArrayIterator(); if (root != null) root.inorder (iter); return iter; } //----------------------------------------------------------------- // Populates and returns an iterator containing the elements in // this binary tree using a levelorder traversal. //----------------------------------------------------------------- public Iterator levelorder() { LinkedQueue queue = new LinkedQueue(); ArrayIterator iter = new ArrayIterator(); if (root != null) { queue.enqueue(root); while (!queue.isEmpty()) { BTNode current = queue.dequeue(); iter.add (current.getElement()); if (current.getLeft() != null) queue.enqueue(current.getLeft()); if (current.getRight() != null) queue.enqueue(current.getRight()); } } return iter; } //----------------------------------------------------------------- // Satisfies the Iterable interface using an inorder traversal. //----------------------------------------------------------------- public Iterator iterator() { return inorder(); } //----------------------------------------------------------------- // The following methods are left as programming projects. //----------------------------------------------------------------- public LinkedBinaryTree getRight() { if(root == null) { throw new EmptyCollectionException ("Get right operation " + "failed. The tree is empty."); } LinkedBinaryTree result = new LinkedBinaryTree(); result.root = root.getRight(); return result; } public Boolean Contains(T item) { BTNode result; result = root; if(root == null) { throw new EmptyCollectionException ("'Contains' operation " + "failed. The tree is empty."); } if(root == item) { return true; } while(result.getElement() != item) { result = result.getRight(); } while(result.getElement() != item) { result = result.getLeft(); } if(root == null && result.getElement() != item) { return false; } return true; } public boolean isEmpty() { if(root == null) { return true; } else { return false; } } public String toString() { return ("There are " + root.count() + " items in this tree."); } public Iterator preorder() { } // public Iterator postorder() { } }

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.