Question: Please help me with this assignment. I have the solutions for int data and now I just have to upgrade to generic BST provided down
Please help me with this assignment. I have the solutions for int data and now I just have to upgrade to generic BST provided down below but I am a bit confused!! Thank you!! New solutions need to go in the SearchTree.java file!
//Here are some important coding files to solve the problems. All you have to do is copy & paste these to your IDE to solve the problems.
//SeachTree.java
// Class SearchTree stores and prints a binary search tree of
// objects of type E. E must implement the Comparable
// interface. from Reges and Stepp, BJP 3ed.
// modified by W.P. Iverson, to not allow duplicates added
// Bellevue College, November 2015
public class SearchTree
private SearchTreeNode
// post: constructs an empty search tree
public SearchTree() {
overallRoot = null;
}
// WRITE ADDITIONAL METHODS HERE:
// Removes the given value from this BST, if it exists.
public void remove(int value) {
overallRoot = remove(overallRoot, value);
}
private IntTreeNode remove(IntTreeNode root, int value) {
if (root == null) {
return null;
} else if (root.data > value) {
root.left = remove(root.left, value);
} else if (root.data
root.right = remove(root.right, value);
} else { // root.data == value; remove this node
if (root.right == null) {
return root.left; // no R child; replace w/ L
} else if (root.left == null) {
return root.right; // no L child; replace w/ R
} else {
// both children; replace w/ min from R
root.data = getMin(root.right);
root.right = remove(root.right, root.data);
}
}
return root;
}
// post: value added to tree so as to preserve binary search tree
public void add(E value) {
overallRoot = add(overallRoot, value);
}
// post: value added to tree so as to preserve binary search tree
private SearchTreeNode
if (root == null) {
root = new SearchTreeNode
} else if (root.data.compareTo(value) > 0) {
root.left = add(root.left, value);
} else if (root.data.compareTo(value)
root.right = add(root.right, value);
}
return root;
}
// post: returns true if tree contains value, returns false otherwise
public boolean contains(E value) {
return contains(overallRoot, value);
}
// post: returns true if given tree contains value, returns false otherwise
private boolean contains(SearchTreeNode
if (root == null) {
return false;
} else {
int compare = value.compareTo(root.data);
if (compare == 0) {
return true;
} else if (compare
return contains(root.left, value);
} else { // compare > 0
return contains(root.right, value);
}
}
}
// post: prints the data of the tree, one per line
public void print() {
printInorder(overallRoot);
}
// post: prints the data of the tree using an inorder traversal
private void printInorder(SearchTreeNode
if (root != null) {
printInorder(root.left);
System.out.println(root.data);
printInorder(root.right);
}
}
private static class SearchTreeNode
public E data; // data stored in this node
public SearchTreeNode
public SearchTreeNode
// post: constructs a leaf node with given data
public SearchTreeNode(E data) {
this(data, null, null);
}
// post: constructs a node with the given data and links
public SearchTreeNode(E data, SearchTreeNode
SearchTreeNode
this.data = data;
this.left = left;
this.right = right;
}
}
}
//Post.java
// Basic tests for Chapter 17 Exercises
// upgraded into generic Search Tree use
// CS211, March 2017, W.P. Iverson, instructor
public class Post {
public static void main(String[] args) {
SearchTree
SearchTree
test.add(new CalendarDate(1,1,2017)); test.add(new CalendarDate(12,12,2016));
// A. Exercise #7 isFull();
System.out.println(test.isFull()); // false
System.out.println(empty.isFull()); // true
// B. Exercise #9 equals(t2);
System.out.println(test.equals(test)); // true
System.out.println(test.equals(empty)); // false
// D. Exercise #12 removeLeaves();
empty.removeLeaves(); empty.print(); // nothing to print
test.removeLeaves(); test.print();// [1/1/2017]
// C. remove process explained in detail via PowerPoint at BJP site
empty.remove(42.); empty.print(); // nothing to print
test.remove(new CalendarDate(1,1,2017)); test.print(); // all gone
}
}
//CalendarDate.java I think we need it?
import java.util.Comparator;
// The CalendarDate class stores information about a single calendar date
// (upgraded from BJP text Chapter 10)
//
public class CalendarDate implements Comparable
// FIELDS
private int month;
private int day;
private int year;
// Constructors
public CalendarDate() {
// default 0,0 makes no sense, so using 1,1
this(1,1,1970); // zero epoch UNIX
}
public CalendarDate(int month, int day, int year) {
if (month12 || day31 || year9999 || year
throw new IllegalArgumentException("Invalid month/day/year");
this.month = month;
this.day = day;
this.year = year;
}
// ACCESSORS (getters)
public int getMonth() {
return month;
}
public int getDay() {
return day;
}
public int getYear() {
return year;
}
// simple quick output
public String toString() {
return month + "/" + day + "/" + year;
}
// I thought a long date was dinner with a preson you don't like?
// But we'll also use the January 1, 1970 format instead
public String longDate() {
String[] names = {"January","February","March","April","May","June","July","August","September","October","November","December"};
return names[month-1] + " " + day + ", " + year;
}
// Compares this calendar date to another date.
// Dates are compared by month and then by day.
public int compareTo(CalendarDate other) {
if (this.year != other.year) {
return this.year - other.year;
} else if (this.month != other.month) {
return this.month - other.month;
} else {
return this.day - other.day;
}
}
// for Comparator interface
public int compare(CalendarDate first, CalendarDate second) {
// Should be the same as compareTo() result
return first.compareTo(second);
}
@Override
public boolean equals(Object other) {
// Note: must override equals(Object)
if (other instanceof CalendarDate) {
CalendarDate test = (CalendarDate)other;
return (this.compareTo(test)==0);
} else
return false;
}
@Override
public int hashCode() {
// days since 0/0/0 assuming 31 in each month
// number is strange, but works to achieve unique hash code
return (day+31*month+366*year);
}
}
//Solutions first with easier int data (Practice-IT)
//A. Exercise #7 isFull();
public boolean isFull() {
return isFull(overallRoot);
private boolean isFull(IntTreeNode node) {
if(node == null)
return true;
if(node.left == null && node.right != null)
return false;
if(node.left != null && node.right == null)
return false;
return isFull(node.left) && isFull(node.right);
}
//B. Exercise #9 equals(t2);
public boolean equals2(IntTree t2) {
return equals2(overallRoot, t2.overallRoot);
}
private boolean equals2(IntTreeNode n1, IntTreeNode n2) {
if(n1 == null && n2 == null)
return true;
if(n1 == null && n2 != null)
return false;
if(n1 != null && n2 == null)
return false;
return n1.data == n2.data && equals2(n1.left, n2.left) &&
equals2(n1.right, n2.right);
}
//C. Exercise #12 removeLeaves();
public void removeLeaves() {
overallRoot = removeLeaves(overallRoot);
}
private IntTreeNode removeLeaves(IntTreeNode node) {
if(node == null)
return null;
if(node.left == null && node.right == null)
return null;
node.left = removeLeaves(node.left);
node.right = removeLeaves(node.right);
return node;
}
//D. remove(data);
public int IntTreeNode remove(IntTreeNode root, int value) {
if (root == null) {
return null;
} else if (root.data > value) {
root.left = remove(root.left, value);
} else if (root.data
root.right = remove(root.right, value);
} else { // root.data == value; remove this node
if (root.right == null) {
return root.left; // no R child; replace w/ L
} else if (root.left == null) {
return root.right; // no L child; replace w/ R
} else {
// both children; replace w/ min from R
root.data = getMin(root.right);
root.right = remove(root.right, root.data);
}
}
return root;
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help