Okay so. Complete BinaryTree\'s visit() and Entry\'s apply() method so that we c
ID: 3818365 • Letter: O
Question
Okay so.
Complete BinaryTree's visit() and Entry's apply() method so that we could process the tree using the Visitor pattern.
They following code might be needed.
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<E> {
/** Tree's element which is stored within this Node. */
private E element;
/** Left child of the current Node. */
private Entry<E> left;
/** Right child of the current Node. */
private Entry<E> right;
/** Parent in the binary tree for the current Node. */
private Entry<E> 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<E> 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<E> getLeft() {
return left;
}
/** Specify a node to be the left child of the current node. */
public void setLeft(Entry<E> left) {
this.left = left;
}
/** Get the node's right child. */
public Entry<E> getRight() {
return right;
}
/** Specify a node to be the right child of the current node. */
public void setRight(Entry<E> right) {
this.right = right;
}
/** Get the node's parent in the tree. This is null if the node is a root. */
public Entry<E> getParent() {
return parent;
}
/** Specify a node to be the parent of the current node. */
public void setParent(Entry<E> 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<E> visitor, String data) {
}
}
Explanation / Answer
package chegg.bstree;
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.
*/
@SuppressWarnings("rawtypes")
public class BinaryTree<E extends Comparable> extends AbstractCollection {
/** Root node of this binary tree */
private Entry<E> 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<Entry<E>> visitor) {
return visitor.visitInterior(root, "preorder");
}
/**
* 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
/* Functions to insert data */
public void insert(E data) {
root = insert(root, data);
}
/* Function to insert data recursively */
private Entry<E> insert(Entry<E> node, E data) {
if (node == null)
node = new Entry<E>(data, node);
else {
if (data.compareTo(node.getElement()) == -1)
node.setLeft(insert(node.getLeft(), data));
else
node.setRight(insert(node.getRight(), data));
}
return node;
}
public static void main(String[] args) {
BinaryTree<Integer> bsTree = new BinaryTree<Integer>();
bsTree.insert(10);
bsTree.insert(20);
bsTree.insert(30);
System.out.println(bsTree.visit(new TreeVisitorImpl()));
}
}
class Entry<E> {
/** Tree's element which is stored within this Node. */
private E element;
/** Left child of the current Node. */
private Entry<E> left;
/** Right child of the current Node. */
private Entry<E> right;
/** Parent in the binary tree for the current Node. */
private Entry<E> 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<E> 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<E> getLeft() {
return left;
}
/** Specify a node to be the left child of the current node. */
public void setLeft(Entry<E> left) {
this.left = left;
}
/** Get the node's right child. */
public Entry<E> getRight() {
return right;
}
/** Specify a node to be the right child of the current node. */
public void setRight(Entry<E> right) {
this.right = right;
}
/** Get the node's parent in the tree. This is null if the node is a root. */
public Entry<E> getParent() {
return parent;
}
/** Specify a node to be the parent of the current node. */
public void setParent(Entry<E> 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<E> visitor, String data) {
return null;
}
}
interface TreeVisitor<E> {
public String visitLeaf(E leaf, String message);
public String visitInterior(E node, String message);
}
class TreeVisitorImpl implements TreeVisitor<Entry<Integer>> {
private static String treeString = "";
public String visitLeaf(Entry<Integer> leaf, String message) {
String leafNodes = null;
leafNodes = printLeafNodes(leaf, leafNodes);
return leafNodes;
}
public static String printLeafNodes(Entry<Integer> t, String leafNodes) {
if (t == null)
return null;
if (t.getLeft() == null && t.getRight() == null)
leafNodes = leafNodes + "" + t.getElement();
printLeafNodes(t.getLeft(), leafNodes);
printLeafNodes(t.getRight(), leafNodes);
return leafNodes;
}
public String visitInterior(Entry<Integer> node, String message) {
inorder(node);
return treeString;
}
private void inorder(Entry<Integer> r) {
if (r != null) {
inorder(r.getLeft());
treeString = treeString + " " + r.getElement();
inorder(r.getRight());
}
}
boolean isLeaf(Entry<Integer> node, int data) {
if (node == null) {
return false;
}
System.out.println("Node traversed :" + node.getElement());
if (node.getLeft() == null && node.getRight() == null
&& node.getElement() == data) {
System.out.println("Node : " + node.getElement() + " is leaf node");
return true;
}
return (isLeaf(node.getLeft(), data) || isLeaf(node.getRight(), data));
}
}
Description :
1. Provided Implementation of TreeVisitor interface. Please check TreeVisitorImpl.java
2. Provided implemnetation of both the method available in TreeVisitor interface.
A. public String visitLeaf(E leaf, String message);
B. public String visitInterior(E node, String message);
3.. Provided the implementation of visit() method avaiable in BinaryTree class.
4. There is one main method defained in BinaryTree class. you need to run or execute the same to check the program how it is working.
5. I couldn't understand the Entry's apply method working so i am leaving it. Please provide the some more working details of that method so that i can assist on you.
Please let me know if you face any dificulties to run the above code and make understanding on same.
Thanks
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.