Please make sure that the code compiles Implement an algorithm in Java that will
ID: 3837910 • Letter: P
Question
Please make sure that the code compiles
Implement an algorithm in Java that will perform a preorder traversal of a Binary Tree by using the Tree class provided below and provide a Utility class with a main method that can use the code:
Interface Tree
public interface Tree<E> extends Iterable<E>
{
Position<E> root( );
Position<E> parent(Position<E> p) throws IllegalArgumentException;
Iterable<Position<E>> children(Position<E> p)
throws IllegalArgumentException;
int numChildren(Position<E> p) throws IllegalArgumentException;
boolean isInternal(Position<E> p) throws IllegalArgumentException;
boolean isExternal(Position<E> p) throws IllegalArgumentException;
boolean isRoot(Position<E> p) throws IllegalArgumentException;
int size( );
boolean isEmpty( );
Iterator<E> iterator( );
Iterable<Position<E>> positions( );
}
Interface Position
public interface Position<E>
{
/**
3 * Returns the element stored at this position.
4 *
5 * @return the stored element
6 * @throws IllegalStateException if position no longer valid
7 */
E getElement( ) throws IllegalStateException;
}
AbstractTree Class
public abstract class AbstractTree<E> implements Tree<E>
{
public boolean isInternal(Position<E> p)
{
return numChildren(p) > 0;
}
public boolean isExternal(Position<E> p)
{
return numChildren(p) == 0;
}
public boolean isRoot(Position<E> p)
{
return p == root( );
}
public boolean isEmpty( )
{
return size( ) == 0;
}
/** Returns the number of levels separating Position p from the root. */
public int depth(Position<E> p)
{
if (isRoot(p))
return 0;
else
return 1 + depth(parent(p));
}
/** Returns the height of the tree. */
private int heightBad( )
{
// works, but quadratic worst-case time
int h = 0;
for (Position<E> p : positions( ))
if (isExternal(p)) // only consider leaf positions
h = Math.max(h, depth(p));
return h;
}
/** Returns the height of the subtree rooted at Position p. */
public int height(Position<E> p)
{
int h = 0; // base case if p is external
for (Position<E> c : children(p))
h = Math.max(h, 1 + height(c));
return h;
}
}
AbstractBinaryTree
public abstract class AbstractBinaryTree<E> extends AbstractTree<E> implements BinaryTree<E>
{
/** Returns the Position of p's sibling (or null if no sibling exists). */
public Position<E> sibling(Position<E> p)
{
Position<E> parent = parent(p);
if (parent == null)
return null; // p must be the root
if (p == left(parent)) // p is a left child
return right(parent); // (right child might be null)
else // p is a right child
return left(parent); // (left child might be null)
}
/** Returns the number of children of Position p. */
public int numChildren(Position<E> p)
{
int count=0;
if (left(p) != null)
count++;
if (right(p) != null)
count++;
return count;
}
/** Returns an iterable collection of the Positions representing p's children. */
public Iterable<Position<E>> children(Position<E> p)
{
List<Position<E>> snapshot = (List<Position<E>>) new ArrayList<E>(2); // max capacity of 2
if (left(p) != null)
snapshot.add(left(p));
if (right(p) != null)
snapshot.add(right(p));
return snapshot;
}
}
Interface BinaryTree
public interface BinaryTree<E> extends Tree<E>
{
/** Returns the Position of p's left child (or null if no child exists). */
Position<E> left(Position<E> p) throws IllegalArgumentException;
/** Returns the Position of p's right child (or null if no child exists). */
Position<E> right(Position<E> p) throws IllegalArgumentException;
/** Returns the Position of p's sibling (or null if no sibling exists). */
Position<E> sibling(Position<E> p) throws IllegalArgumentException;
}
LinkedBinaryTree class
public class LinkedBinaryTree<E> extends AbstractBinaryTree<E>
{
//---------------- nested Node class ----------------
protected static class Node<E> implements Position<E>
{
private E element; // an element stored at this node
private Node<E> parent; // a reference to the parent node (if any)
private Node<E> left; // a reference to the left child (if any)
private Node<E> right; // a reference to the right child (if any)
/** Constructs a node with the given element and neighbors. */
public Node(E e, Node<E> above, Node<E> leftChild, Node<E> rightChild)
{
element = e;
parent = above;
left = leftChild;
right = rightChild;
}
// accessor methods
public E getElement( )
{
return element;
}
public Node<E> getParent( )
{
return parent;
}
public Node<E> getLeft( )
{
return left;
}
public Node<E> getRight( )
{
return right;
}
// update methods
public void setElement(E e)
{
element = e;
}
public void setParent(Node<E> parentNode)
{
parent = parentNode;
}
public void setLeft(Node<E> leftChild)
{
left = leftChild;
}
public void setRight(Node<E> rightChild)
{
right = rightChild;
}
}
//----------- end of nested Node class -----------
/** Factory function to create a new node storing element e. */
protected Node<E> createNode(E e, Node<E> parent, Node<E> left, Node<E> right)
{
return new Node<E>(e, parent, left, right);
}
// LinkedBinaryTree instance variables
protected Node<E> root = null; // root of the tree
private int size = 0; // number of nodes in the tree
// constructor
public LinkedBinaryTree( )
{
} // constructs an empty binary tree
// nonpublic utility
/** Validates the position and returns it as a node. */
protected Node<E> validate(Position<E> p) throws IllegalArgumentException
{
if (!(p instanceof Node))
throw new IllegalArgumentException("Not valid position type");
Node<E> node = (Node<E>) p; // safe cast
if (node.getParent( ) == node) // our convention for defunct node
throw new IllegalArgumentException("p is no longer in the tree");
return node;
}
// accessor methods (not already implemented in AbstractBinaryTree)
/** Returns the number of nodes in the tree. */
public int size()
{
return size;
}
/** Returns the root Position of the tree (or null if tree is empty). */
public Position<E> root()
{
return root;
}
/** Returns the Position of p's parent (or null if p is root). */
public Position<E> parent(Position<E> p) throws IllegalArgumentException
{
Node<E> node = validate(p);
return node.getParent( );
}
/** Returns the Position of p's left child (or null if no child exists). */
public Position<E> left(Position<E> p) throws IllegalArgumentException
{
Node<E> node = validate(p);
return node.getLeft( );
}
/** Returns the Position of p's right child (or null if no child exists). */
public Position<E> right(Position<E> p) throws IllegalArgumentException
{
Node<E> node = validate(p);
return node.getRight( );
}
// update methods supported by this class
/** Places element e at the root of an empty tree and returns its new Position. */
public Position<E> addRoot(E e) throws IllegalStateException
{
if (!isEmpty( )) throw new IllegalStateException("Tree is not empty");
root = createNode(e, null, null, null);
size = 1;
return root;
}
/** Creates a new left child of Position p storing element e; returns its Position. */
public Position<E> addLeft(Position<E> p, E e) throws IllegalArgumentException
{
Node<E> parent = validate(p);
if (parent.getLeft( ) != null)
throw new IllegalArgumentException("p already has a left child");
Node<E> child = createNode(e, parent, null, null);
parent.setLeft(child);
size++;
return child;
}
/** Creates a new right child of Position p storing element e; returns its Position. */
public Position<E> addRight(Position<E> p, E e) throws IllegalArgumentException
{
Node<E> parent = validate(p);
if (parent.getRight( ) != null)
throw new IllegalArgumentException("p already has a right child");
Node<E> child = createNode(e, parent, null, null);
parent.setRight(child);
size++;
return child;
}
/** Replaces the element at Position p with e and returns the replaced element. */
public E set(Position<E> p, E e) throws IllegalArgumentException
{
Node<E> node = validate(p);
E temp = node.getElement( );
node.setElement(e);
return temp;
}
/** Attaches trees t1 and t2 as left and right subtrees of external p. */
public void attach(Position<E> p, LinkedBinaryTree<E> t1, LinkedBinaryTree<E> t2) throws IllegalArgumentException
{
Node<E> node = validate(p);
if (isInternal(p))
throw new IllegalArgumentException("p must be a leaf");
size += t1.size( ) + t2.size( );
if (!t1.isEmpty( ))
{
// attach t1 as left subtree of node
t1.root.setParent(node);
node.setLeft(t1.root);
t1.root = null;
t1.size = 0;
}
if (!t2.isEmpty( ))
{
// attach t2 as right subtree of node
t2.root.setParent(node);
node.setRight(t2.root);
t2.root = null;
t2.size = 0;
}
}
/** Removes the node at Position p and replaces it with its child, if any. */
public E remove(Position<E> p) throws IllegalArgumentException
{
Node<E> node = validate(p);
if (numChildren(p) == 2)
throw new IllegalArgumentException("p has two children");
Node<E> child = (node.getLeft( ) != null ? node.getLeft( ) : node.getRight( ) );
if (child != null)
child.setParent(node.getParent( )); // child’s grandparent becomes its parent
if (node == root)
root = child; // child becomes root
else
{
Node<E> parent = node.getParent( );
if (node == parent.getLeft( ))
parent.setLeft(child);
else
parent.setRight(child);
}
size--;
E temp = node.getElement( );
node.setElement(null); // help garbage collection
node.setLeft(null);
node.setRight(null);
node.setParent(node); // our convention for defunct node
return temp;
}
public Iterator<E> iterator() {
// TODO Auto-generated method stub
return null;
}
public Iterable<Position<E>> positions() {
// TODO Auto-generated method stub
return null;
}
} //----------- end of LinkedBinaryTree class -----------
Explanation / Answer
For your reference you can use the below code to implement an algorithm in java that will perform a preorder traversal of a Binary Tree.
import java.util.stack;
//program to traverse a binary tree using preorder traversal.
Public class PreOrderTraversal {
Public Static void main(String[] args) throws Exception {
BinaryTree bt=new BinaryTree();
BinaryTree.TreeNode root = new BinaryTree.TreeNode("1");
bt.root=root;
bt.root.left = new BinaryTree.TreeNode("2");
bt.root.left.left = new BinaryTree.TreeNode("3");
bt.root.left.right = new BinaryTree.TreeNode("4");
bt.root.right = new BinaryTree.TreeNode("5");
bt.root.right.right = new BinaryTree.TreeNode("6");
}
}
//create binary class
class BinaryTree {
static class TreeNode {
String data;
TreeNode left, right;
TreeNode(String value) {
this.data = value;
left = right = null;
}
boolean isLeaf() {
return left == null ? right == null: false;
}
}
// root of binary tree
TreeNode root;
//Print method for preOder
public void perOrder() {
preOrder(root);
}
Private void preOrder(TreeNode node) {
if(node==null) {
return;
}
System.out,printf("%s", node.data);
preOrder(node.left);
preOrder(node.right);
}
}