I have attached the implementation of LinkedBinaryTree from Lab07 and alsot the picture of page 349. Please help. I need it in Java. Its not that big as it looks I guess.

Implementation of LinkedBinaryTree :

import java.util.Iterator; import java.util.LinkedList; import java.util.Queue;

/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */

/** * * @author lionel.clarke */ public class LinkedBinaryTree extends AbstractBinaryTree {

static class Node implements Position {

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

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

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

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

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

} }

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

public void inOrder(Node root) { if (root != null) { inOrder(root.left); System.out.printf("%s ", root.getElement()); inOrder(root.right); } }

public void preOrder(Node root) { if (root != null) { System.out.printf("%s ", root.getElement()); inOrder(root.left); inOrder(root.right); } }

public void postOrder(Node root) { if (root != null) { inOrder(root.left); inOrder(root.right); System.out.printf("%s ", root.getElement()); } }

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

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

Using your LinkedBinaryTree implementation from Lab07write a program that reads fully parenthesized, arithmetic expressions from a file and converts them into binary expression trees Add a method named euler TourBinary as described on page 349 of the textbook. Write this method so that it will print out a traditional parenthesized arithmetic expression. 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: Print out the expression that was read from the file. Determine if the expression is valid. o o Print an invalid expression message for invalid e For each valid 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 Using your LinkedBinaryTree implementation from Lab07write a program that reads fully parenthesized, arithmetic expressions from a file and converts them into binary expression trees Add a method named euler TourBinary as described on page 349 of the textbook. Write this method so that it will print out a traditional parenthesized arithmetic expression. 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: Print out the expression that was read from the file. Determine if the expression is valid. o o Print an invalid expression message for invalid e For each valid 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