Complete BinaryTree\'s visit() and Entry\'s apply() method so that we could proc
ID: 3818316 • Letter: C
Question
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<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 com.cheggtest;/*
* Java Program to Implement Binary Tree
*/
import java.util.Scanner;
class BTNode {
BTNode left, right;
int data;
/* Constructor */
public BTNode() {
left = null;
right = null;
data = 0;
}
public BTNode(int n) {
left = null;
right = null;
data = n;
}
public void setLeft(BTNode n) {
left = n;
}
public void setRight(BTNode n) {
right = n;
}
public BTNode getLeft() {
return left;
}
/* Function to get right node */
public BTNode getRight() {
return right;
}
}
/* Class BT */
class BT {
private BTNode root;
public BT() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public void insert(int data) {
root = insert(root, data);
}
/* Function to insert data recursively */
private BTNode insert(BTNode node, int data) {
if (node == null)
node = new BTNode(data);
else {
if (node.getRight() == null)
node.right = insert(node.right, data);
else
node.left = insert(node.left, data);
}
return node;
}
/* Function to count number of nodes */
public int countNodes() {
return countNodes(root);
}
/* Function to count number of nodes recursively */
private int countNodes(BTNode r) {
if (r == null)
return 0;
else {
int l = 1;
l += countNodes(r.getLeft());
l += countNodes(r.getRight());
return l;
}
}
/* Function to search for an element */
public boolean search(int val) {
return search(root, val);
}
/* Function to search for an element recursively */
private boolean search(BTNode r, int val) {
if (r.getData() == val)
return true;
if (r.getLeft() != null)
if (search(r.getLeft(), val))
return true;
if (r.getRight() != null)
if (search(r.getRight(), val))
return true;
return false;
}
/* Function for inorder traversal */
public void inorder() {
inorder(root);
}
private void inorder(BTNode r) {
if (r != null) {
inorder(r.getLeft());
System.out.print(r.getData() + " ");
inorder(r.getRight());
}
}
/* Function for preorder traversal */
public void preorder() {
preorder(root);
}
private void preorder(BTNode r) {
if (r != null) {
System.out.print(r.getData() + " ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
/* Function for postorder traversal */
public void postorder() {
postorder(root);
}
private void postorder(BTNode r) {
if (r != null) {
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() + " ");
}
}
}
/* Class BinaryTree */
public class BinaryTree {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
/* Creating object of BT */
BT bt = new BT();
/* Perform tree operations */
System.out.println("Binary Tree Test ");
char ch;
do {
System.out.println(" Binary Tree Operations ");
System.out.println("1. insert ");
System.out.println("2. search");
System.out.println("3. count nodes");
System.out.println("4. check empty");
int choice = scan.nextInt();
switch (choice) {
case 1:
System.out.println("Enter integer element to insert");
bt.insert(scan.nextInt());
break;
case 2:
System.out.println("Enter integer element to search");
System.out.println("Search result : "
+ bt.search(scan.nextInt()));
break;
case 3:
System.out.println("Nodes = " + bt.countNodes());
break;
case 4:
System.out.println("Empty status = " + bt.isEmpty());
break;
default:
System.out.println("Wrong Entry ");
break;
}
/* Display tree */
System.out.print(" Post order : ");
bt.postorder();
System.out.print(" Pre order : ");
bt.preorder();
System.out.print(" In order : ");
bt.inorder();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y' || ch == 'y');
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.