Question
Implement an AVL tree class in Java, BUT with the following specifications: a. Write a subclass of BinaryNode called AVL_Node, which includes an instance variable
Implement an AVL tree class in Java, BUT with the following specifications:
a. Write a subclass of BinaryNode called AVL_Node, which includes an instance variable for the height (int)
b. Write a subclass of BST called AVL_Tree which overrides the insert and remove methods (be sure to instantiate an AVL_Node in the insert method), and adds new methods for leftRotation, rightRotation, leftRightRotation, rightLeftRotation (may use the ones given in one of the Class Notes)
c. Be sure to use the completed BinaryTree class that includes the writeIndentedTree methods.
I uploaded all the classes from the program just in case it is needed.
_________________________________________________________________________________
import java.util.Comparator;
//Adapted from Code By Y. Daniel Liang
//Modified by C. Lee-Klawender
public class BST
private boolean foundNode; // helper variable
Comparator
/** Create a default binary tree */
public BST(Comparator
comp = c;
}
public BST(BST
super(sourceTree);
}
/** Create a binary tree from an array of objects */
public BST(E[] objects, Comparator
this(c);
for (int i = 0; i < objects.length; i++)
insert(objects[i]);
}
@Override /** Returns true if the element is in the tree */
public boolean contains(E e) {
BinaryNode
while (current != null) {
if (comp.compare(current.getData(), e) > 0)// change for hw4
{
current = current.getLeftChild();
} else if (comp.compare(current.getData(), e) < 0)// change for hw4
{
current = current.getRightChild();
} else // element matches current.getData()
return true; // Element is found
} // end while
return false;
}
@Override
/**
* Returns the data of the Node that equals the parameter, null if not
* found.
*/
public E getEntry(E e) // YOU WRITE FOR HW#4
{
BinaryNode
// 7.3
if (foundNode != null)
return foundNode.getData();
return null;
}
private BinaryNode
if (node == null)
return null;
else if (comp.compare(node.getData(), e) > 0)// change this
return _findNode(node.getLeftChild(), e);
else if (comp.compare(node.getData(), e) < 0)// change this
return _findNode(node.getRightChild(), e);
else // found it!
return node;
}
@Override
/**
* Insert element o into the binary tree Return true if the element is
* inserted successfully
*/
public boolean insert(E e) {
root = _insert(root, e); // calls private insert that YOU write for HW#4
size++;
return true; // Element inserted successfully
}
private BinaryNode
if (node == null) {
node = new BinaryNode
return node;
} else if (comp.compare(node.getData(), e) > 0)// change this for hw4
node.setLeftChild(_insert(node.getLeftChild(), e));// recursive call
else { // change for hw4
node.setRightChild(_insert(node.getRightChild(), e));// recursive
// call
}
return node;
}
@Override
/**
* Delete an element from the binary tree. Return true if the element is
* deleted successfully Return false if the element is not in the tree
*/
public boolean delete(E e) {
foundNode = false; // initialize boolean instance variable
root = _delete(root, e); // call private method to do actual deletion
if (foundNode) {
size--;// Element deleted successfully
}
return foundNode;
}
// Private recursive method that returns an updated "root" node from where
// current node is
private BinaryNode
if (node == null) {
return null;
}
if (comp.compare(node.getData(), e) > 0)// change this for hw4
node.setLeftChild(_delete(node.getLeftChild(), e));// recursive call
else if (comp.compare(node.getData(), e) < 0)// change for hw4
node.setRightChild(_delete(node.getRightChild(), e));// recursive
// call
else {
foundNode = true;
node = _deleteNode(node);
}
return node;
} // end _delete
// Private method that either "moves up" the left or right child, OR
// replaces the data in the nodeToDelete with the data in the rightmost
// child of
// the nodeToDelete's left child, then "removes" that node
private BinaryNode
if (nodeToDelete.isLeaf()) // node to delete has no children
{
return null;
}
if (!nodeToDelete.hasLeftChild()) // node to delete has no LEFT child
{
return nodeToDelete.getRightChild();
}
if (!nodeToDelete.hasRightChild()) // node to delete has no RIGHT child
{
return nodeToDelete.getLeftChild();
}
// must have left and right children
// Locate the rightmost node in the left subtree of
// the node to delete and also its parent
BinaryNode
BinaryNode
while (rightMost.getRightChild() != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.getRightChild(); // Keep going to the right
}
// Replace the element in nodeToDelete by the element in rightMost
nodeToDelete.setData(rightMost.getData()); // don't really delete the
// node, just change the
// data
// Eliminate rightmost node
if (parentOfRightMost.getRightChild() == rightMost)
parentOfRightMost.setRightChild(rightMost.getLeftChild());
else
// Special case: nodeToDelete's leftChild has no rightChild
parentOfRightMost.setLeftChild(rightMost.getLeftChild());
return nodeToDelete;
} // end private _deleteNode
public E getFirst()// you finish (part of HW#4)
{
if (root == null)
return null;
else {
BinaryNode
while (currNode.hasLeftChild()) {
currNode = currNode.getLeftChild();
}
return currNode.getData();
}
}
public E getLast()// you finish (part of HW#4)
{
if (root == null)
return null;
else {
BinaryNode
while (currNode.hasRightChild()) {
currNode = currNode.getRightChild();
}
return currNode.getData();
}
}
} // end class BST
________________________________________________________________________
import java.io.PrintStream;
// Adapted from code by Y. Daniel Liang
// Modified by C. Lee-Klawender
public abstract class BinaryTree
protected BinaryNode
protected int size = 0; // number of nodes in the tree
public BinaryTree() {
}
public BinaryTree(BinaryTree
// YOU WRITE (should do a DEEP COPY)
}
/** Clears the whole tree */
public void clear() {
root = null;
size = 0;
}
public void writeIndentedTree(PrintStream writer) {
writeTree(writer, this.root, 1, "");
// Call the writeTree, passing this parameter, this' root, 1 and ""
}
/**
* prints out the BST indented so that it actually looks like a binary tree and it is easily visible to
* the reader.
*/
protected void writeTree(PrintStream writer, BinaryNode
if (root == null) {
return;
} else {
for (int i = 1; i < level; i++) {
indent += " ";
}
level++;
writeTree(writer, root.getRightChild(), level, indent);
writer.println(indent + (level - 1) + ". " + root.getData().toString());
writeTree(writer, root.getLeftChild(), level, indent);
}
}
@Override /** Preorder traversal from the root */
public void preorder(Visitor
preorder(root, visitor);
}
@Override /** Inorder traversal from the root */
public void inorder(Visitor
inorder(root, visitor);
}
@Override /** Postorder traversal from the root */
public void postorder(Visitor
postorder(root, visitor);
}
@Override /** Get the number of nodes in the tree */
public int getSize() {
return size;
}
@Override /** Return true if the tree is empty */
public boolean isEmpty() {
return getSize() == 0;
}
protected void exercise(BinaryNode
LinkedQueue
if(Q.isEmpty()){
return;
}
Q.enqueue(root);
visitor.visit(Q.peekFront().getData());
while(!Q.isEmpty()){
BinaryNode
Q.dequeue();
BinaryNode
if(w.getData() != null){
Q.enqueue(w);
visitor.visit(w.getData());
w = v.getRightChild();
}
if(w.getData() != null){
Q.enqueue(w);
visitor.visit(w.getData());
}
}
}
/** Preorder traversal from a subtree */
protected void preorder(BinaryNode
if (root == null)
return;
visitor.visit(root.getData());
preorder(root.getLeftChild(), visitor);
preorder(root.getRightChild(), visitor);
}
/** Inorder traversal from a subtree */
protected void inorder(BinaryNode
if (root == null)
return;
inorder(root.getLeftChild(), visitor);
visitor.visit(root.getData());
inorder(root.getRightChild(), visitor);
}
/** Posorder traversal from a subtree */
protected void postorder(BinaryNode
if (root == null)
return;
postorder(root.getLeftChild(), visitor);
postorder(root.getRightChild(), visitor);
visitor.visit(root.getData());
}
} // end abstract BinaryTree class
________________________________________________________________
/**
* A class that represents nodes in a binary tree.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0 MODIFIED BY C. Lee-Klawender
*/
class BinaryNode
private T data;
private BinaryNode
private BinaryNode
public BinaryNode() {
this(null); // Call next constructor
} // end default constructor
public BinaryNode(T dataPortion) {
this(dataPortion, null, null); // Call next constructor
} // end constructor
public BinaryNode(T dataPortion, BinaryNode
data = dataPortion;
leftChild = newLeftChild;
rightChild = newRightChild;
} // end constructor
/**
* Retrieves the data portion of this node.
*
* @return The object in the data portion of the node.
*/
public T getData() {
return data;
} // end getData
/**
* Sets the data portion of this node.
*
* @param newData
* The data object.
*/
public void setData(T newData) {
data = newData;
} // end setData
/**
* Retrieves the left child of this node.
*
* @return The nodes left child.
*/
public BinaryNode
return leftChild;
} // end getLeftChild
/**
* Sets this nodes left child to a given node.
*
* @param newLeftChild
* A node that will be the left child.
*/
public void setLeftChild(BinaryNode
leftChild = newLeftChild;
} // end setLeftChild
/**
* Detects whether this node has a left child.
*
* @return True if the node has a left child.
*/
public boolean hasLeftChild() {
return leftChild != null;
} // end hasLeftChild
/**
* Retrieves the right child of this node.
*
* @return The nodes right child.
*/
public BinaryNode
return rightChild;
} // end getRightChild
/**
* Sets this nodes right child to a given node.
*
* @param newRightChild
* A node that will be the right child.
*/
public void setRightChild(BinaryNode
rightChild = newRightChild;
} // end setRightChild
/**
* Detects whether this node has a right child.
*
* @return True if the node has a right child.
*/
public boolean hasRightChild() {
return rightChild != null;
} // end hasRightChild
/**
* Detects whether this node is a leaf.
*
* @return True if the node is a leaf.
*/
public boolean isLeaf() {
return (leftChild == null) && (rightChild == null);
} // end isLeaf
/**
* Counts the nodes in the subtree rooted at this node.
*
* @return The number of nodes in the subtree rooted at this node.
*/
public int getNumberOfNodes() {
int leftNumber = 0;
int rightNumber = 0;
if (leftChild != null)
leftNumber = leftChild.getNumberOfNodes();
if (rightChild != null)
rightNumber = rightChild.getNumberOfNodes();
return 1 + leftNumber + rightNumber;
} // end getNumberOfNodes
/**
* Computes the height of the subtree rooted at this node.
*
* @return The height of the subtree rooted at this node.
*/
public int getHeight() {
return getHeight(this); // Call private getHeight
} // end getHeight
private int getHeight(BinaryNode
int height = 0;
if (node != null)
height = 1 + Math.max(getHeight(node.getLeftChild()), getHeight(node.getRightChild()));
return height;
} // end getHeight
/**
* Copies the subtree rooted at this node.
*
* @return The root of a copy of the subtree rooted at this node.
*/
public BinaryNode
BinaryNode
if (leftChild != null)
newRoot.setLeftChild(leftChild.copy());
if (rightChild != null)
newRoot.setRightChild(rightChild.copy());
return newRoot;
} // end copy
} // end BinaryNode
_________________________________________________________________________
/**
* Homework Assignment #4
* Jae Kim
* 6/10/17
* Windows/Ecplise
*
* The Main class reads the file that user inputs from the console and reads the lines and instantiates
* a new Date class with the 3 integers in the line. It then tests that all the methods in BST are working
* correctly
*/
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
public class Main {
public static void main(String[] args) {
MonthComparator monthComp = new MonthComparator();
YearComparator yearComp = new YearComparator();
BST
BST
Scanner scannedFile = openInputFile();
if (scannedFile != null) {
while (scannedFile.hasNextLine()) {
String line = scannedFile.nextLine();
line = line.trim();
String[] tpp = line.split("\\s+");
Date date = new Date();
if (date.setDate(Integer.parseInt(tpp[0]), Integer.parseInt(tpp[1]), Integer.parseInt(tpp[2]))) {
binaryMonthDates.insert(date);
binaryYearDates.insert(date);
} else
System.out.println("Invalid Date, not added: " + Integer.parseInt(tpp[0]) + "-"
+ Integer.parseInt(tpp[1]) + "-" + Integer.parseInt(tpp[2]));
}
scannedFile = null;
System.out.println(" Year-ordered tree has: ");
binaryYearDates.inorder(new YearVisitor());
System.out.println(" Month-ordered tree has: ");
binaryMonthDates.inorder(new MonthVisitor());
System.out.println(" Year-ordered indented tree: ");
binaryYearDates.writeTree(System.out, binaryYearDates.root, 1, "");
System.out.println(" Month-ordered indented tree: ");
binaryMonthDates.writeTree(System.out, binaryMonthDates.root, 1, "");
System.out.println(" Student Testing Year-ordered tree:");
myTest(binaryYearDates);
System.out.println("Student Testing Month-ordered tree:");
myTest(binaryMonthDates);
System.out.println(" Postorder traversal of updated Year-ordered Tree: ");
binaryYearDates.postorder(new YearVisitor());
System.out.println(" Now the updated Month-ordered indented tree has ");
binaryMonthDates.writeTree(System.out, binaryMonthDates.root, 1, "");
testMore(binaryYearDates);
testMore(binaryMonthDates);
} else
System.out.println("Ending program");
}
/**
* Tests if getEntry, getFirst, and getLast is working correctly.
* @param dates
*/
public static void myTest(BST
Date firstDate = dates.getFirst();
Date lastDate = dates.getLast();
System.out.println(" getFirst() returns: " + firstDate + " " + "getLast() returns: " + lastDate);
Date firstDateCopy = firstDate;
System.out.println("getEntry() passing a copy of the first returns: " + dates.getEntry(firstDateCopy));
Date almostLastDateCopy = new Date(lastDate.getMonth(), lastDate.getDay(), lastDate.getYear() + 1);
System.out.println("Created a copy of the last Date, with year+1: " + almostLastDateCopy.toString());
System.out.println(
"getEntry(); passing a copy of the last with year+1 returns: " + dates.getEntry(almostLastDateCopy));
System.out.println("insert() passing the copy of the last with year+1 returns: "
+ dates.insert(almostLastDateCopy) + " ");
}
public static Scanner userScanner = new Scanner(System.in);
// opens a text file for input, returns a Scanner:
public static Scanner openInputFile() {
String filename;
Scanner scanner = null;
System.out.print("Enter the input filename: ");
filename = userScanner.nextLine();
File file = new File(filename);
try {
scanner = new Scanner(file);
} // end try
catch (FileNotFoundException fe) {
System.out.println("Can't open input file ");
return null; // array of 0 elements
} // end catch
return scanner;
}
// CALL THIS METHOD AS INSTRUCTED ON THE ASSIGNMENT
public static void testMore(BST
Date firstDate, lastDate = null;
Date testDate1 = new Date(12, 31, 1900);
Date testDate2 = new Date(1, 2, 2000);
System.out.println(" Clearing tree:");
firstDate = tree.getFirst();
while (firstDate != null) {
lastDate = tree.getLast();
if (tree.delete(firstDate))
System.out.println("Removed " + firstDate);
if (firstDate != lastDate && tree.delete(lastDate))
System.out.println("Removed " + lastDate);
firstDate = tree.getFirst();
} //
System.out.println(" Tree is cleared, now writeIndentedTree displays: ");
tree.writeIndentedTree(System.out);
System.out.println("End writing tree Now adding back last 2 retrieved:");
tree.insert(testDate1);
tree.insert(testDate2);
System.out.println("Now the tree has: ");
tree.writeIndentedTree(System.out);
} // end testMore()
}
/*__________________OUTPUT #1____________________
Enter the input filename: HW4 Test Input1.txt
Invalid Date, not added: 4-31-2009
Year-ordered tree has:
1923-12-10
1933-11-10
1947-4-9
1949-11-15
1951-6-5
1960-2-1
1963-8-4
1972-2-25
1979-6-5
Month-ordered tree has:
2/1/1960
2/25/1972
4/9/1947
6/5/1951
6/5/1979
8/4/1963
11/10/1933
11/15/1949
12/10/1923
Year-ordered indented tree:
3. 6/5/1979
2. 2/25/1972
3. 8/4/1963
4. 2/1/1960
1. 6/5/1951
4. 11/15/1949
3. 4/9/1947
2. 11/10/1933
3. 12/10/1923
Month-ordered indented tree:
3. 12/10/1923
4. 11/15/1949
2. 11/10/1933
4. 8/4/1963
3. 6/5/1979
1. 6/5/1951
3. 4/9/1947
2. 2/25/1972
3. 2/1/1960
Student Testing Year-ordered tree:
getFirst() returns: 12/10/1923
getLast() returns: 6/5/1979
getEntry() passing a copy of the first returns: 12/10/1923
Created a copy of the last Date, with year+1: 6/5/1980
getEntry(); passing a copy of the last with year+1 returns: null
insert() passing the copy of the last with year+1 returns: true
Student Testing Month-ordered tree:
getFirst() returns: 2/1/1960
getLast() returns: 12/10/1923
getEntry() passing a copy of the first returns: 2/1/1960
Created a copy of the last Date, with year+1: 12/10/1924
getEntry(); passing a copy of the last with year+1 returns: null
insert() passing the copy of the last with year+1 returns: true
Postorder traversal of updated Year-ordered Tree:
1923-12-10
1949-11-15
1947-4-9
1933-11-10
1960-2-1
1963-8-4
1980-6-5
1979-6-5
1972-2-25
1951-6-5
Now the updated Month-ordered indented tree has
4. 12/10/1924
3. 12/10/1923
4. 11/15/1949
2. 11/10/1933
4. 8/4/1963
3. 6/5/1979
1. 6/5/1951
3. 4/9/1947
2. 2/25/1972
3. 2/1/1960
Clearing tree:
Removed 12/10/1923
Removed 6/5/1980
Removed 11/10/1933
Removed 6/5/1979
Removed 4/9/1947
Removed 2/25/1972
Removed 11/15/1949
Removed 8/4/1963
Removed 6/5/1951
Removed 2/1/1960
Tree is cleared, now writeIndentedTree displays:
End writing tree
Now adding back last 2 retrieved:
Now the tree has:
2. 1/2/2000
1. 12/31/1900
Clearing tree:
Removed 2/1/1960
Removed 12/10/1924
Removed 2/25/1972
Removed 12/10/1923
Removed 4/9/1947
Removed 11/15/1949
Removed 6/5/1951
Removed 11/10/1933
Removed 6/5/1979
Removed 8/4/1963
Tree is cleared, now writeIndentedTree displays:
End writing tree
Now adding back last 2 retrieved:
Now the tree has:
1. 12/31/1900
2. 1/2/2000
*/
/* __________________OUTPUT #2____________________
Enter the input filename: HW4 Test Input2.txt
Invalid Date, not added: 2-29-1941
Year-ordered tree has:
1932-2-17
1934-5-11
1935-9-2
1936-1-9
1937-12-24
1940-4-16
1942-4-1
1953-5-28
1953-9-13
1955-8-25
1955-9-7
1962-1-17
1972-9-23
1973-3-18
1977-8-10
1977-8-11
1978-10-14
1984-7-30
1984-9-30
1987-4-28
1990-5-11
1994-1-21
1994-5-27
1994-11-8
1995-2-9
2000-8-13
2002-3-31
2004-12-17
2008-8-6
2010-7-4
2014-9-11
2017-8-22
Month-ordered tree has:
1/9/1936
1/17/1962
1/21/1994
2/9/1995
2/17/1932
3/18/1973
3/31/2002
4/1/1942
4/16/1940
4/28/1987
5/11/1934
5/11/1990
5/27/1994
5/28/1953
7/4/2010
7/30/1984
8/6/2008
8/10/1977
8/11/1977
8/13/2000
8/22/2017
8/25/1955
9/2/1935
9/7/1955
9/11/2014
9/13/1953
9/23/1972
9/30/1984
10/14/1978
11/8/1994
12/17/2004
12/24/1937
Year-ordered indented tree:
5. 8/22/2017
4. 9/11/2014
3. 7/4/2010
4. 8/6/2008
6. 12/17/2004
5. 3/31/2002
2. 8/13/2000
5. 2/9/1995
4. 11/8/1994
3. 5/27/1994
6. 1/21/1994
5. 5/11/1990
4. 4/28/1987
5. 9/30/1984
1. 7/30/1984
5. 10/14/1978
4. 8/11/1977
6. 8/10/1977
5. 3/18/1973
3. 9/23/1972
6. 1/17/1962
7. 9/7/1955
5. 8/25/1955
6. 9/13/1953
4. 5/28/1953
5. 4/1/1942
6. 4/16/1940
2. 12/24/1937
5. 1/9/1936
4. 9/2/1935
3. 5/11/1934
4. 2/17/1932
Month-ordered indented tree:
3. 12/24/1937
6. 12/17/2004
5. 11/8/1994
7. 10/14/1978
6. 9/30/1984
4. 9/23/1972
6. 9/13/1953
8. 9/11/2014
7. 9/7/1955
8. 9/2/1935
5. 8/25/1955
6. 8/22/2017
2. 8/13/2000
3. 8/11/1977
5. 8/10/1977
4. 8/6/2008
1. 7/30/1984
4. 7/4/2010
3. 5/28/1953
2. 5/27/1994
5. 5/11/1990
4. 5/11/1934
3. 4/28/1987
7. 4/16/1940
6. 4/1/1942
5. 3/31/2002
6. 3/18/1973
7. 2/17/1932
8. 2/9/1995
9. 1/21/1994
4. 1/17/1962
5. 1/9/1936
Student Testing Year-ordered tree:
getFirst() returns: 2/17/1932
getLast() returns: 8/22/2017
getEntry() passing a copy of the first returns: 2/17/1932
Created a copy of the last Date, with year+1: 8/22/2018
getEntry(); passing a copy of the last with year+1 returns: null
insert() passing the copy of the last with year+1 returns: true
Student Testing Month-ordered tree:
getFirst() returns: 1/9/1936
getLast() returns: 12/24/1937
getEntry() passing a copy of the first returns: 1/9/1936
Created a copy of the last Date, with year+1: 12/24/1938
getEntry(); passing a copy of the last with year+1 returns: null
insert() passing the copy of the last with year+1 returns: true
Postorder traversal of updated Year-ordered Tree:
1932-2-17
1936-1-9
1935-9-2
1934-5-11
1940-4-16
1942-4-1
1953-9-13
1955-9-7
1962-1-17
1955-8-25
1953-5-28
1977-8-10
1973-3-18
1978-10-14
1977-8-11
1972-9-23
1937-12-24
1984-9-30
1994-1-21
1990-5-11
1987-4-28
1995-2-9
1994-11-8
1994-5-27
2004-12-17
2002-3-31
2008-8-6
2018-8-22
2017-8-22
2014-9-11
2010-7-4
2000-8-13
1984-7-30
Now the updated Month-ordered indented tree has
4. 12/24/1938
3. 12/24/1937
6. 12/17/2004
5. 11/8/1994
7. 10/14/1978
6. 9/30/1984
4. 9/23/1972
6. 9/13/1953
8. 9/11/2014
7. 9/7/1955
8. 9/2/1935
5. 8/25/1955
6. 8/22/2017
2. 8/13/2000
3. 8/11/1977
5. 8/10/1977
4. 8/6/2008
1. 7/30/1984
4. 7/4/2010
3. 5/28/1953
2. 5/27/1994
5. 5/11/1990
4. 5/11/1934
3. 4/28/1987
7. 4/16/1940
6. 4/1/1942
5. 3/31/2002
6. 3/18/1973
7. 2/17/1932
8. 2/9/1995
9. 1/21/1994
4. 1/17/1962
5. 1/9/1936
Clearing tree:
Removed 2/17/1932
Removed 8/22/2018
Removed 5/11/1934
Removed 8/22/2017
Removed 9/2/1935
Removed 9/11/2014
Removed 1/9/1936
Removed 7/4/2010
Removed 12/24/1937
Removed 8/6/2008
Removed 4/16/1940
Removed 12/17/2004
Removed 4/1/1942
Removed 3/31/2002
Removed 5/28/1953
Removed 8/13/2000
Removed 9/13/1953
Removed 2/9/1995
Removed 8/25/1955
Removed 11/8/1994
Removed 9/7/1955
Removed 5/27/1994
Removed 1/17/1962
Removed 1/21/1994
Removed 9/23/1972
Removed 5/11/1990
Removed 3/18/1973
Removed 4/28/1987
Removed 8/10/1977
Removed 9/30/1984
Removed 8/11/1977
Removed 7/30/1984
Removed 10/14/1978
Tree is cleared, now writeIndentedTree displays:
End writing tree
Now adding back last 2 retrieved:
Now the tree has:
2. 1/2/2000
1. 12/31/1900
Clearing tree:
Removed 1/9/1936
Removed 12/24/1938
Removed 1/17/1962
Removed 12/24/1937
Removed 1/21/1994
Removed 12/17/2004
Removed 2/9/1995
Removed 11/8/1994
Removed 2/17/1932
Removed 10/14/1978
Removed 3/18/1973
Removed 9/30/1984
Removed 3/31/2002
Removed 9/23/1972
Removed 4/1/1942
Removed 9/13/1953
Removed 4/16/1940
Removed 9/11/2014
Removed 4/28/1987
Removed 9/7/1955
Removed 5/11/1934
Removed 9/2/1935
Removed 5/11/1990
Removed 8/25/1955
Removed 5/27/1994
Removed 8/22/2017
Removed 5/28/1953
Removed 8/13/2000
Removed 7/4/2010
Removed 8/11/1977
Removed 7/30/1984
Removed 8/10/1977
Removed 8/6/2008
Tree is cleared, now writeIndentedTree displays:
End writing tree
Now adding back last 2 retrieved:
Now the tree has:
1. 12/31/1900
2. 1/2/2000
*/
______________________________________________________________
import java.util.Comparator;
/**
* Homework Assignment #3 Jae Kim 5/30/17 Windows/Ecplise
*
* Date class holds integer variables month, day, year. It works around the
* actual calendar.
*/
public class Date implements Comparable
static final int MIN_MONTH = 1;
static final int MAX_MONTH = 12;
static final int MIN_YEAR = 1000;
static final int MAX_YEAR = 9999;
static final int[] DAYS_IN_MONTH = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
private int month = 1;
private int day = 1;
private int year = 1000;
public Date() {
}
public Date(int m, int d, int y) {
setDate(m, d, y); // else leave default values
}
public static boolean isLeapYear(int y) {
return (y % 4 == 0 && y % 100 != 0 || y % 400 == 0);
}
public boolean setDate(int m, int d, int y) {
int isLeap = 0;
if (y >= MIN_YEAR && y <= MAX_YEAR && m >= MIN_MONTH && m <= MAX_MONTH) {
if (m == 2 && isLeapYear(y))
isLeap = 1;
if (d >= 1 && d <= (DAYS_IN_MONTH[m] + isLeap)) {
month = m;
day = d;
year = y;
return true;
}
}
return false; // leaves instance vars. as they were before
} // end setDate
public int getMonth() {
return month;
}
public int getDay() {
return day;
}
public int getYear() {
return year;
}
public String toString() {
return month + "/" + day + "/" + year;
}
/**
* Compares the Date passed through the parameter to the instance Date first
* by year, then month, and finally day.
*/
@Override
public int compareTo(Date param) {
int result = this.year - param.year;
if (result == 0) {
result = this.month - param.month;
if (result == 0)
result = this.day - param.day;
}
return result;
}
}
___________________________________________________________
// Adapted from Code By Y. Daniel Liang
// Modified by C. Lee-Klawender
// Note: this interface is NOT the same as the General Tree version shown in Catalyst
interface Visitor
public void visit(T obj);
}
public interface TreeInterface
/** Clear the whole Tree */
public void clear();
/** Return true if the element is in the tree */
public boolean contains(E e);
/** Return an element in the tree which matches the parameter */
public E getEntry(E e);
/**
* Insert element o into the binary tree Return true if the element is
* inserted successfully
*/
public boolean insert(E e);
/**
* Delete the specified element from the tree Return true if the element is
* deleted successfully
*/
public boolean delete(E e);
/** Inorder traversal from the root */
public void inorder(Visitor
/** Postorder traversal from the root */
public void postorder(Visitor
/** Preorder traversal from the root */
public void preorder(Visitor
/** Get the number of nodes in the tree */
public int getSize();
/** Return true if the tree is empty */
public boolean isEmpty();
}
__________________________________________________________
/**
* Homework Assignment #4
* Jae Kim
* 6/10/17
* Windows/Ecplise
*
* MonthComparator compares two dates with comparator
*/
import java.util.Comparator;
public class MonthComparator implements Comparator
/**
* compares two date parameters, first through month, then day, then year.
*/
public int compare(Date left, Date right) {
int difference = left.getMonth() - right.getMonth();
if (difference == 0) {
difference = left.getDay() - right.getDay();
}
if (difference == 0) {
difference = left.getYear() - right.getYear();
}
return difference;
}
}
_______________________________________________________________
/**
* Homework Assignment #4
* Jae Kim
* 6/10/17
* Windows/Ecplise
*
* MonthVisitor class visits each date in the BST.
*/
public class MonthVisitor implements Visitor
/**
* visit method prints out the date parameter by calling the original toString method
*/
@Override
public void visit(Date mDate) {
System.out.println(mDate.toString());
}
}
__________________________________________________________________
/**
* Homework Assignment #4
* Jae Kim
* 6/10/17
* Windows/Ecplise
*
* YearComparator compares the dates
*
*/
import java.util.Comparator;
public class YearComparator implements Comparator
/**
* compare two date classes by calling date class's compareTo
*/
public int compare(Date left, Date right) {
return left.compareTo(right);
}
}
________________________________________________
/**
* Homework Assignment #4
* Jae Kim
* 6/10/17
* Windows/Ecplise
*
* YearVisitor visits the date class.
*/
public class YearVisitor implements Visitor
/**
* Visit method prints out the date parameter in this format: yyyy-mm-dd
*/
@Override
public void visit(Date yDate) {
System.out.println(yDate.getYear() + "-" + yDate.getMonth() + "-" + yDate.getDay());
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
Progress Monitoring Data Tracking Organizer
Authors: Teacher'S Aid Publications
1st Edition
B0B7QCNRJ1
