Create an implementation of a binary tree using the recursive approach. In this
ID: 664877 • Letter: C
Question
Create an implementation of a binary tree using the recursive approach. 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. Use java.
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.
Use the following file: expressions.txt
-----------------------------------------------------------------------------
expressions.txt:
Explanation / Answer
package javafoundations;
import java.util.Iterator;
public interface BinaryTree<T> extends Iterable<T>
{
// Returns the element stored in the root of the tree.
public T getRootElement();
// Returns the left subtree of the root.
public BinaryTree<T> getLeft();
// Returns the right subtree of the root.
public BinaryTree<T> getRight();
// Returns true if the binary tree contains an element that
// matches the specified element and false otherwise.
public boolean contains (T target);
// Returns a reference to the element in the tree matching
// the specified target.
public T find (T target);
// Returns true if the binary tree contains no elements, and
// false otherwise.
public boolean isEmpty();
// Returns the number of elements in this binary tree.
public int size();
// Returns the string representation of the binary tree.
public String toString();
// Returns a preorder traversal on the binary tree.
public Iterator<T> preorder();
// Returns an inorder traversal on the binary tree.
public Iterator<T> inorder();
// Returns a postorder traversal on the binary tree.
public Iterator<T> postorder();
// Performs a level-order traversal on the binary tree.
public Iterator<T> levelorder();
}
public Iterator<T> levelorder()
{
LinkedQueue<BTNode<T>> queue = new LinkedQueue<BTNode<T>>();
ArrayIterator<T> iter = new ArrayIterator<T>();
if (root != null)
{
queue.enqueue(root);
while (!queue.isEmpty())
{
BTNode<T> 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;
}
public Iterator<T> iterator()
{
return inorder();
}
}
BTNode class:
`
//*******************************************************************
// BTNode.java Java Foundations
//
// Represents a node in a binary tree with a left and right child.
// Therefore this class also represents the root of a subtree.
//*******************************************************************
package javafoundations;
public class BTNode<T>
{
protected T element;
protected BTNode<T> left, right;
public BTNode (T element)
{
this.element = element;
left = right = null;
}
public T getElement()
{
return element;
}
public void setElement (T element)
{
this.element = element;
}
public BTNode<T> getLeft()
{
return left;
}
public void setLeft (BTNode<T> left)
{
this.left = left;
}
public BTNode<T> getRight()
{
return right;
}
public void setRight (BTNode<T> right)
{
this.right = right;
}
public BTNode<T> find (T target)
{
BTNode<T> result = null;
if (element.equals(target))
result = this;
else
{
if (left != null)
result = left.find(target);
if (result == null && right != null)
result = right.find(target);
}
return result;
}
public int count()
{
int result = 1;
if (left != null)
result += left.count();
if (right != null)
result += right.count();
return result;
}
public void inorder (ArrayIterator<T> iter)
{
if (left != null)
left.inorder (iter);
iter.add (element);
if (right != null)
right.inorder (iter);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.