Implement an AVL tree class in Java, BUT with the following specifications: a. W
ID: 3853200 • Letter: I
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 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<E extends Comparable<E>> extends BinaryTree<E> {
private boolean foundNode; // helper variable
Comparator<E> comp;
/** Create a default binary tree */
public BST(Comparator<E> c) {
comp = c;
}
public BST(BST<E> sourceTree) {
super(sourceTree);
}
/** Create a binary tree from an array of objects */
public BST(E[] objects, Comparator<E> c) {
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<E> current = root; // Start from the root
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<E> foundNode = _findNode(root, e); // YOU WRITE FOR LAB EX.
// 7.3
if (foundNode != null)
return foundNode.getData();
return null;
}
private BinaryNode<E> _findNode(BinaryNode<E> node, E e) {
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<E> _insert(BinaryNode<E> node, E e) {
if (node == null) {
node = new BinaryNode<E>(e);
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<E> _delete(BinaryNode<E> node, E e) {
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<E> _deleteNode(BinaryNode<E> nodeToDelete) {
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<E> parentOfRightMost = nodeToDelete;
BinaryNode<E> rightMost = nodeToDelete.getLeftChild();
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<E> currNode = root;
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<E> currNode = root;
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<E> implements TreeInterface<E> {
protected BinaryNode<E> root = null; // reference to the root
protected int size = 0; // number of nodes in the tree
public BinaryTree() {
}
public BinaryTree(BinaryTree<E> sourceTree) {
// 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<E> root, int level, String indent) {
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<E> visitor) {
preorder(root, visitor);
}
@Override /** Inorder traversal from the root */
public void inorder(Visitor<E> visitor) {
inorder(root, visitor);
}
@Override /** Postorder traversal from the root */
public void postorder(Visitor<E> 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<E> root, Visitor<E> visitor){
LinkedQueue<BinaryNode<E>> Q = new LinkedQueue<>();
if(Q.isEmpty()){
return;
}
Q.enqueue(root);
visitor.visit(Q.peekFront().getData());
while(!Q.isEmpty()){
BinaryNode<E> v = Q.peekFront();
Q.dequeue();
BinaryNode<E> w = v.getLeftChild();
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<E> root, Visitor<E> visitor) {
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<E> root, Visitor<E> visitor) {
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<E> root, Visitor<E> visitor) {
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<T> {
private T data;
private BinaryNode<T> leftChild; // Reference to left child
private BinaryNode<T> rightChild; // Reference to right child
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<T> newLeftChild, BinaryNode<T> newRightChild) {
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 node’s left child.
*/
public BinaryNode<T> getLeftChild() {
return leftChild;
} // end getLeftChild
/**
* Sets this node’s left child to a given node.
*
* @param newLeftChild
* A node that will be the left child.
*/
public void setLeftChild(BinaryNode<T> newLeftChild) {
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 node’s right child.
*/
public BinaryNode<T> getRightChild() {
return rightChild;
} // end getRightChild
/**
* Sets this node’s right child to a given node.
*
* @param newRightChild
* A node that will be the right child.
*/
public void setRightChild(BinaryNode<T> newRightChild) {
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<T> node) {
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<T> copy() {
BinaryNode<T> newRoot = new BinaryNode<>(data);
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<Date> binaryMonthDates = new BST<>(monthComp);
BST<Date> binaryYearDates = new BST<>(yearComp);
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> dates) {
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> tree) {
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<Date> {
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<T> {
public void visit(T obj);
}
public interface TreeInterface<E> {
/** 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<E> visitor);
/** Postorder traversal from the root */
public void postorder(Visitor<E> visitor);
/** Preorder traversal from the root */
public void preorder(Visitor<E> 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<Date> {
/**
* 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<Date> {
/**
* 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<Date> {
/**
* 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<Date> {
/**
* 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());
}
}
Explanation / Answer
import java.util.Scanner;
class TreeNode
{
TreeNode lft, rht; // left and right
int info;
int length;
public TreeNode()
{
lft = null;
rht = null;
info = 0;
length = 0;
}
public TreeNode(int n)
{
lft = null;
rht = null;
info = n;
length = 0;
}
}
class AVL
{
private TreeNode root;
public AVL()
{
root = null;
}
public boolean emptyOrNot()
{
return root == null;
}
public void Empty()
{
root = null;
}
public void insertdata(int info)
{
root = insertdata(info, root);
}
private int length(TreeNode t )
{
return t == null ? -1 : t.length;
}
private int maximum(int lhs, int rhs)
{
return lhs > rhs ? lhs : rhs;
}
private TreeNode insertdata(int x, TreeNode t)
{
if (t == null)
t = new TreeNode(x);
else if (x < t.info)
{
t.lft = insertdata( x, t.lft );
if( length( t.lft ) - length( t.rht ) == 2 )
if( x < t.lft.info )
t = leftChildRotate( t );
else
t = leftChildDouble( t );
}
else if( x > t.info )
{
t.rht = insertdata( x, t.rht );
if( length( t.rht ) - length( t.lft ) == 2 )
if( x > t.rht.info)
t = rotateWithrhtChild( t );
else
t = doubleWithrhtChild( t );
}
else
; // do nothing
t.length = maximum( length( t.lft ), length( t.rht ) ) + 1;
return t;
}
private TreeNode leftChildRotate(TreeNode n2)
{
TreeNode n1 = n2.lft;
n2.lft = n1.rht;
n1.rht = n2;
n2.length = maximum( length( n2.lft ), length( n2.rht ) ) + 1;
n1.length = maximum( length( n1.lft ), n2.length ) + 1;
return n1;
}
private TreeNode rotateWithrhtChild(TreeNode n1)
{
TreeNode n2 = n1.rht;
n1.rht = n2.lft;
n2.lft = n1;
n1.length = maximum( length( n1.lft ), length( n1.rht ) ) + 1;
n2.length = maximum( length( n2.rht ), n1.length ) + 1;
return n2;
}
private TreeNode leftChildDouble(TreeNode k3)
{
k3.lft = rotateWithrhtChild( k3.lft );
return leftChildRotate( k3 );
}
private TreeNode doubleWithrhtChild(TreeNode n1)
{
n1.rht = leftChildRotate( n1.rht );
return rotateWithrhtChild( n1 );
}
public int noOfNodes()
{
return noOfNodes(root);
}
private int noOfNodes(TreeNode r)
{
if (r == null)
return 0;
else
{
int l = 1;
l += noOfNodes(r.lft);
l += noOfNodes(r.rht);
return l;
}
}
public boolean find(int number)
{
return find(root, number);
}
private boolean find(TreeNode r, int number)
{
boolean foundOrNot = false;
while ((r != null) && !foundOrNot)
{
int rightnumberue = r.info;
if (number < rightnumberue)
r = r.lft;
else if (number > rightnumberue)
r = r.rht;
else
{
foundOrNot = true;
break;
}
foundOrNot = find(r, number);
}
return foundOrNot;
}
public void inordTraversal()
{
inordTraversal(root);
}
private void inordTraversal(TreeNode r)
{
if (r != null)
{
inordTraversal(r.lft);
System.out.print(r.info +" ");
inordTraversal(r.rht);
}
}
public void preordTraversal()
{
preordTraversal(root);
}
private void preordTraversal(TreeNode r)
{
if (r != null)
{
System.out.print(r.info +" ");
preordTraversal(r.lft);
preordTraversal(r.rht);
}
}
public void postordTraversal()
{
postordTraversal(root);
}
private void postordTraversal(TreeNode r)
{
if (r != null)
{
postordTraversal(r.lft);
postordTraversal(r.rht);
System.out.print(r.info +" ");
}
}
}
public class AVLTreeDriver
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
AVL obj = new AVL();
System.out.println("AVL Tree Driver ");
char ch;
do
{
System.out.println(" Select operation to perform: ");
System.out.println("1. Insertion of data ");
System.out.println("2. Find data");
System.out.println("3. Number of nodes");
System.out.println("4. Is Tree empty");
System.out.println("5. Clear the tree");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter an integer: ");
obj.insertdata( scan.nextInt() );
break;
case 2 :
System.out.println("Enter an integer: ");
System.out.println("Result : "+ obj.find( scan.nextInt() ));
break;
case 3 :
System.out.println("Number of nodes = "+ obj.noOfNodes());
break;
case 4 :
System.out.println("Is it empty status = "+ obj.emptyOrNot());
break;
case 5 :
System.out.println(" Tree successfully cleared");
obj.Empty();
break;
default :
System.out.println("Entered choice is wrong ");
break;
}
System.out.print(" Displaying in postorder : ");
obj.postordTraversal();
System.out.print(" Displaying in preorder : ");
obj.preordTraversal();
System.out.print(" Displaying in inorder : ");
obj.inordTraversal();
System.out.println(" Continue or Exit (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
----------------------
OUTPUT:
AVL Tree Driver
Select operation to perform:
1. Insertion of data
2. Find data
3. Number of nodes
4. Is Tree empty
5. Clear the tree
1
Enter an integer:
56
Displaying in postorder : 56
Displaying in preorder : 56
Displaying in inorder : 56
Continue or Exit (Type y or n)
y
Select operation to perform:
1. Insertion of data
2. Find data
3. Number of nodes
4. Is Tree empty
5. Clear the tree
1
Enter an integer:
43
Displaying in postorder : 43 56
Displaying in preorder : 56 43
Displaying in inorder : 43 56
Continue or Exit (Type y or n)
n
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.