Complete BinaryTree's visit() and Entry's apply() method so that we could process the tree using the Visitor pattern.

------------------------------------------

Do consider following:

testNodeIsInteriorBothChildren

testNodeIsInteriorOneChild

testNodeIsLeaf

testBinaryTree

------------------------------

BinaryTree

package edu.buffalo.cse116;

import java.util.AbstractCollection; import java.util.Iterator;

/** * Instances of this class represent a vanilla binary tree (e.g., and not a binary search tree). * * @author Matthew Hertz * @param Type of data stored in each node of this tree. Since this is not a BST, E can be anything. */ public class BinaryTree extends AbstractCollection {

/** Root node of this binary tree */ private Entry root;

/** Number of nodes/elements within this binary tree. */ private int size;

/** * Initializes this BinarySearchTree object to be empty, to contain only * elements of type E, to be ordered by the Comparable interface, and to * contain no duplicate elements. */ public BinaryTree() { root = null; size = 0; }

public String visit(TreeVisitor visitor) { }

/** * Returns the size of this BinarySearchTree object. * * @return the size of this BinarySearchTree object. */ @Override public int size() { return size; }

/** * Iterator method that has, at last, been implemented. * * @return an iterator positioned at the smallest element in this * BinarySearchTree object. */ @Override public Iterator iterator() { // Skipped until next week throw new UnsupportedOperationException(); }

/** * Determines if there is at least one element in this binary tree object that equals a specified element. * * @param obj - the element sought in this binary tree * @return true if the object is an element in the binary tree; false othrwise. */ @Override public boolean contains(Object obj) { return getEntry(obj) != null; }

/** * Finds the BTNode object that houses a specified element, if there is such an * BTNode. * * @param obj - the element whose BTNode is sought. * @return the BTNode object that houses obj - if there is such an BTNode; * otherwise, return null. */ protected Entry getEntry(Object obj) { return getEntry(root, obj); }

/** * Finds the BTNode object that houses a specified element in the subtree rooted at subtreeRoot, if there is such an * BTNode. * * @param obj - the element whose BTNode is sought. * @return the BTNode object that houses obj - if there is such an BTNode in the subtree at subtreeRoot; * otherwise, return null. */ protected Entry getEntry(Entry subtreeRoot, Object obj) { if (subtreeRoot == null) { return null; } else if ((subtreeRoot.getElement() == obj) || ((subtreeRoot.getElement() != null) && subtreeRoot.getElement().equals(obj))) { return subtreeRoot; } if (subtreeRoot.getLeft() != null) { Entry retVal = getEntry(subtreeRoot.getLeft(), obj); if (retVal != null) { return retVal; } } if (subtreeRoot.getRight() != null) { Entry retVal = getEntry(subtreeRoot.getRight(), obj); if (retVal != null) { return retVal; } } return null; }

/** * Finds the successor of a specified Entry object in this BinarySearchTree. * The worstTime(n) is O(n) and averageTime(n) is constant. * * @param e - the Entry object whose successor is to be found. * @return the successor of e, if e has a successor; otherwise, return null. */ protected Entry successor(Entry e) { if (e == null) { return null; } else if (e.getRight() != null) { // successor is leftmost Entry in right subtree of e Entry p = e.getRight(); while (p.getLeft() != null) { p = p.getLeft(); } return p;

} // e has a right child else {

// go up the tree to the left as far as possible, then go up // to the right. Entry p = e.getParent(); Entry ch = e; while ((p != null) && (ch == p.getRight())) { ch = p; p = p.getParent(); } // while return p; } // e has no right child } // method successor }

---------------------

Tree visitor

package edu.buffalo.cse116;

/** * Interface implemented by Visitor classes. Each class defines the visitor for a generic binary tree. Classes will need * to implement this to define the specific functionality they will define. * * @author Matthew Hertz * @param Type of data held in each node in the binary tree. */ public interface TreeVisitor { public String visitLeaf(Entry leaf, String message);

public String visitInterior(Entry node, String message); }

-------------------

Entry

package edu.buffalo.cse116;

public class Entry { /** Tree's element which is stored within this Node. */ private E element;

/** Left child of the current Node. */ private Entry left; /** Right child of the current Node. */ private Entry right; /** Parent in the binary tree for the current Node. */ private Entry parent;

/** * Initializes this Entry object. This default constructor is defined for future expansion purposes. */ public Entry() {}

/** * Initializes this Entry object from element and parent. */ public Entry(E element, Entry parent) { this.element = element; this.parent = parent; }

/** Return the element stored in this node. */ public E getElement() { return element; }

/** Specify a new element to be stored at this node. */ public void setElement(E element) { this.element = element; }

/** Get the node's left child. */ public Entry getLeft() { return left; }

/** Specify a node to be the left child of the current node. */ public void setLeft(Entry left) { this.left = left; }

/** Get the node's right child. */ public Entry getRight() { return right; }

/** Specify a node to be the right child of the current node. */ public void setRight(Entry right) { this.right = right; }

/** Get the node's parent in the tree. This is null if the node is a root. */ public Entry getParent() { return parent; }

/** Specify a node to be the parent of the current node. */

public void setParent(Entry parent) { this.parent = parent; }

/** * Implement the node's portion of the Visitor pattern. This allows the TreeVisitor to work and return the result of * the traversal. * * @param visitor TreeVisitor instance doing the work. * @param data Data being passed along as part of this visiting traveral. * @return The result returned by the TreeVisitor. */ public String apply(TreeVisitor visitor, String data) { }

}