Question

STAGE 1: Implement the following methods in “BST.java” class:

/** Return the height of this binary tree 20 points*/

public int height() {

   // Left as exercise

   return 0;

}

/** BreadthFirst traversal from the root 20 points */

public void breadthFirstTraversal() {

   // Left as an exercise

}

STAGE 2: Implement the following methods in “Tree.java” class:

@SuppressWarnings("unchecked")

@Override

public default boolean containsAll(Collection<?> c) {

   // Left as an exercise 10 points

     

   return true;

}

@SuppressWarnings("unchecked")

@Override

public default boolean addAll(Collection<? extends E> c) {

   // Left as an exercise 10 points

              

   return true;

}

@SuppressWarnings("unchecked")

@Override

public default boolean removeAll(Collection<?> c) {

   // Left as an exercise 10 points

  

   return true;

}

@SuppressWarnings("unchecked")

@Override

public default boolean retainAll(Collection<?> c) {

   // Left as an exercise 10 points

  

   return true;

  

}

@Override

public default Object[] toArray() {

   // Left as an exercise 10 points

  

   return temp;

}

@SuppressWarnings("unchecked")

@Override

public default <T> T[] toArray(T[] array) {

   // Left as an exercise 10 points

  

   return array;

}

STAGE 3: Test your classes with “DriverBST.java” class. Output should be:

The height of tree is 0

The height of tree is 1

The height of tree is 2

The height of tree is 2

The height of tree is 3

The breadth-first traversal is Green Blue Red White

The pre-order traversal is Green Blue Red White

The breadth-first traversal is Tom George Jean Jane Kevin Jen Peter Kim Susan Michael Michelle

The height of tree1 is 8

The breadth-first traversal for tree2 is 50 45 59 35 48 51 58

The height of tree2 is 4

The breadth-first traversal for tree3 is 50 48 52 58

The height of tree3 is 3

tree2 contains all of tree3 ? false

The breadth-first traversal for tree2 is 50 45 59 35 48 51 22 58 52

The height of tree2 is 5

The breadth-first traversal for tree2 is 22 52

The height of tree2 is 2

The breadth-first traversal for tree3 is 50 48 58

The height of tree3 is 2

[35, 45, 48, 50, 51, 58, 59]

[35, 45, 48, 50, 51, 58, 59]

tree.java

https://drive.google.com/file/d/17snMGZSyT7g67Q6kPH7toalCabEKaPPF/view?usp=sharing

BST.java

https://drive.google.com/file/d/1eFxiOO2_AVYzuEac0EPZ8hOuj6ZotOv-/view?usp=sharing

DriverBST.java

https://drive.google.com/file/d/1FU1yaHmZCPAWY3bQ-bxu_IVm3v4sqMVO/view?usp=sharing

Answer 1

BST.java

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package testprj2;

public class BST<E> implements Tree<E> {

protected TreeNode<E> root;
protected int size = 0;
protected java.util.Comparator<E> c;

/**
* Create a default BST with a natural order comparator
*/
public BST() {
this.c = (e1, e2) -> ((Comparable<E>) e1).compareTo(e2);
}

/**
* Create a BST with a specified comparator
*/
public BST(java.util.Comparator<E> c) {
this.c = c;
}

/**
* Create a binary tree from an array of objects
*/
public BST(E[] objects) {
this.c = (e1, e2) -> ((Comparable<E>) e1).compareTo(e2);
for (int i = 0; i < objects.length; i++) {
add(objects[i]);
}
}

@Override
/**
* Returns true if the element is in the tree
*/
public boolean search(E e) {
TreeNode<E> current = root; // Start from the root

while (current != null) {
if (c.compare(e, current.element) < 0) {
current = current.left;
} else if (c.compare(e, current.element) > 0) {
current = current.right;
} else // element matches current.element
{
return true; // Element is found
}
}

return false;
}

@Override
/**
* Insert element e into the binary tree Return true if the element is
* inserted successfully
*/
public boolean insert(E e) {
if (root == null) {
root = createNewNode(e); // Create a new root
} else {
// Locate the parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (c.compare(e, current.element) < 0) {
parent = current;
current = current.left;
} else if (c.compare(e, current.element) > 0) {
parent = current;
current = current.right;
} else {
return false; // Duplicate node not inserted
}
}
// Create the new node and attach it to the parent node
if (c.compare(e, parent.element) < 0) {
parent.left = createNewNode(e);
} else {
parent.right = createNewNode(e);
}
}

size++;
return true; // Element inserted successfully
}

protected TreeNode<E> createNewNode(E e) {
return new TreeNode<>(e);
}

protected int height(TreeNode<E> root) {
if (null == root) {
return 0;
}
int hLeftSub = height(root.left);
int hRightSub = height(root.right);
return Math.max(hLeftSub, hRightSub) + 1;
}

/**
* Return the height of this binary tree
*/
public int height() {
return height(root);
}

/**
* BreadthFirst traversal from the root
*/
  
public void breadthFirstTraversal() {
// Left as an exercise
int i;
for (i = 1; i <= height(root); i++) {
breadthFirstTraversal(root, i);
}

}

protected void breadthFirstTraversal(TreeNode<E> root, int level) {
if (root == null) {
return;
}
if (level == 1) {
System.out.print(root.element + " ");
} else if (level > 1) {
breadthFirstTraversal(root.left, level - 1);
breadthFirstTraversal(root.right, level - 1);
}
}

@Override
/**
* Inorder traversal from the root
*/
public void inorder() {
inorder(root);
}

/**
* Inorder traversal from a subtree
*/
protected void inorder(TreeNode<E> root) {
if (root == null) {
return;
}
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}

@Override
/**
* Postorder traversal from the root
*/
public void postorder() {
postorder(root);
}

/**
* Postorder traversal from a subtree
*/
protected void postorder(TreeNode<E> root) {
if (root == null) {
return;
}
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}

@Override
/**
* Preorder traversal from the root
*/
public void preorder() {
preorder(root);
}

/**
* Preorder traversal from a subtree
*/
protected void preorder(TreeNode<E> root) {
if (root == null) {
return;
}
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}

/**
* This inner class is static, because it does not access any instance
* members defined in its outer class
*/
public static class TreeNode<E> {

protected E element;
protected TreeNode<E> left;
protected TreeNode<E> right;

public TreeNode(E e) {
element = e;
}
}

@Override
/**
* Get the number of nodes in the tree
*/
public int getSize() {
return size;
}

/**
* Returns the root of the tree
*/
public TreeNode<E> getRoot() {
return root;
}

/**
* Returns a path from the root leading to the specified element
*/
public java.util.ArrayList<TreeNode<E>> path(E e) {
java.util.ArrayList<TreeNode<E>> list
= new java.util.ArrayList<>();
TreeNode<E> current = root; // Start from the root

while (current != null) {
list.add(current); // Add the node to the list
if (c.compare(e, current.element) < 0) {
current = current.left;
} else if (c.compare(e, current.element) > 0) {
current = current.right;
} else {
break;
}
}

return list; // Return an array list of nodes
}

@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) {
// Locate the node to be deleted and also locate its parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (c.compare(e, current.element) < 0) {
parent = current;
current = current.left;
} else if (c.compare(e, current.element) > 0) {
parent = current;
current = current.right;
} else {
break; // Element is in the tree pointed at by current
}
}

if (current == null) {
return false; // Element is not in the tree
}
// Case 1: current has no left child
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
} else {
if (c.compare(e, parent.element) < 0) {
parent.left = current.right;
} else {
parent.right = current.right;
}
}
} else {
// Case 2: The current node has a left child
// Locate the rightmost node in the left subtree of
// the current node and also its parent
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;

while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}

// Replace the element in current by the element in rightMost
current.element = rightMost.element;

// Eliminate rightmost node
if (parentOfRightMost.right == rightMost) {
parentOfRightMost.right = rightMost.left;
} else // Special case: parentOfRightMost == current
{
parentOfRightMost.left = rightMost.left;
}
}

size--;
return true; // Element deleted successfully
}

@Override
/**
* Obtain an iterator. Use inorder.
*/
public java.util.Iterator<E> iterator() {
return new InorderIterator();
}

// Inner class InorderIterator
private class InorderIterator implements java.util.Iterator<E> {
// Store the elements in a list

private java.util.ArrayList<E> list
= new java.util.ArrayList<>();
private int current = 0; // Point to the current element in list

public InorderIterator() {
inorder(); // Traverse binary tree and store elements in list
}

/**
* Inorder traversal from the root
*/
private void inorder() {
inorder(root);
}

/**
* Inorder traversal from a subtree
*/
private void inorder(TreeNode<E> root) {
if (root == null) {
return;
}
inorder(root.left);
list.add(root.element);
inorder(root.right);
}

@Override
/**
* More elements for traversing?
*/
public boolean hasNext() {
if (current < list.size()) {
return true;
}

return false;
}

@Override
/**
* Get the current element and move to the next
*/
public E next() {
return list.get(current++);
}

@Override // Remove the element returned by the last next()
public void remove() {
if (current == 0) // next() has not been called yet
{
throw new IllegalStateException();
}

delete(list.get(--current));
list.clear(); // Clear the list
inorder(); // Rebuild the list
}
}

@Override
/**
* Remove all elements from the tree
*/
public void clear() {
root = null;
size = 0;
}
}

Tree.java

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package testprj2;

import java.util.Collection;

public interface Tree<E> extends Collection<E> {

/**
* Return true if the element is in the tree
*/
public boolean search(E e);

/**
* Insert element e 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);

/**
* Get the number of elements in the tree
*/
public int getSize();

/**
* Inorder traversal from the root
*/
public default void inorder() {
}

/**
* Postorder traversal from the root
*/
public default void postorder() {
}

/**
* Preorder traversal from the root
*/
public default void preorder() {
}

/**
* Return the height of this binary tree
*/
public int height(); // Left as exercise: implement in BST

/**
* BreadthFirst traversal from the root
*/

public default void breadthFirstTraversal() {
// Left as an exercise: implement in BST
}

@Override
/**
* Return true if the tree is empty
*/
public default boolean isEmpty() {
return this.size() == 0;
}

@Override
public default boolean contains(Object e) {
return search((E) e);
}

@Override
public default boolean add(E e) {
return insert(e);
}

@Override
public default boolean remove(Object e) {
return delete((E) e);
}

@Override
public default int size() {
return getSize();
}

@SuppressWarnings("unchecked")
@Override
public default boolean containsAll(Collection<?> c) {
// Left as an exercise
boolean result = true;
for (Object e : c) {
result &= contains(e);
}
return result;
}

@SuppressWarnings("unchecked")
@Override
public default boolean addAll(Collection<? extends E> c) {
// Left as an exercise
for (E e : c) {
add(e);
}
return true;
}

@SuppressWarnings("unchecked")
@Override
public default boolean removeAll(Collection<?> c) {
// Left as an exercise
for (Object e : c) {
remove(e);
}
return true;
}

@SuppressWarnings("unchecked")
@Override
public default boolean retainAll(Collection<?> c) {
// Left as an exercise
for (E e : this) {
if (!c.contains(e)) {
remove(e);
}
}
return true;

}

@Override
public default Object[] toArray() {
// Left as an exercise
Object[] arr= new Object[this.getSize()];
int index = 0;
for (E e : this) {
arr[index] = e;
index++;
}
return arr;
}

@SuppressWarnings("unchecked")
@Override
public default <T> T[] toArray(T[] array) {
// Left as an exercise
//array = new T[this.getSize()];
int index = 0;
for (E e : this) {
array[index] =(T) e;
index++;
}
return array;
}

}

DriverBST.java

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package testprj2;

import java.util.ArrayList;
import java.util.Arrays;

public class DriverBST {

// TODO Auto-generated method stub
public static void main(String[] args) {
new DriverBST();
}

public DriverBST() {

Tree<String> tree = new BST<String>();
System.out.print("The height of tree is " + tree.height());

tree.insert("Green");
System.out.print("\nThe height of tree is " + tree.height());

tree.insert("Red");
System.out.print("\nThe height of tree is " + tree.height());
tree.insert("Blue");
System.out.print("\nThe height of tree is " + tree.height());
tree.insert("White");
System.out.print("\nThe height of tree is " + tree.height());
System.out.print("\nThe breadth-first traversal is ");
tree.breadthFirstTraversal();
System.out.print("\nThe pre-order traversal is ");
tree.preorder();

BST<String> tree1 = new BST<String>(new String[]{"Tom", "George", "Jean", "Jane", "Kevin", "Peter", "Susan",
"Jen", "Kim", "Michael", "Michelle"});
System.out.print("\nThe breadth-first traversal is ");
tree1.breadthFirstTraversal();
System.out.print("\nThe height of tree1 is " + tree1.height());

BST<Integer> tree2
= new BST<Integer>(new Integer[]{50, 45, 35, 48, 59, 51, 58});
System.out.print("\nThe breadth-first traversal for tree2 is ");
tree2.breadthFirstTraversal();
System.out.print("\nThe height of tree2 is " + tree2.height());
BST<Integer> tree3
= new BST<Integer>(new Integer[]{50, 48, 52, 58});
System.out.print("\nThe breadth-first traversal for tree3 is ");
tree3.breadthFirstTraversal();
System.out.print("\nThe height of tree3 is " + tree3.height());
System.out.println("\ntree2 contains all of tree3 ? " + tree2.containsAll(tree3));
BST<Integer> tree4
= new BST<Integer>(new Integer[]{22, 52});
tree2.addAll(tree4);
System.out.print("\nThe breadth-first traversal for tree2 is ");
tree2.breadthFirstTraversal();
System.out.print("\nThe height of tree2 is " + tree2.height());
tree2.retainAll(tree4);
System.out.print("\nThe breadth-first traversal for tree2 is ");
tree2.breadthFirstTraversal();
System.out.print("\nThe height of tree2 is " + tree2.height());
tree3.removeAll(tree4);
System.out.print("\nThe breadth-first traversal for tree3 is ");
tree3.breadthFirstTraversal();
System.out.print("\nThe height of tree3 is " + tree3.height());
tree2 = new BST<Integer>(new Integer[]{50, 45, 35, 48, 59, 51, 58});
Object[] list1 = tree2.toArray();

System.out.println("\n" + new ArrayList(Arrays.asList(list1)));

Integer[] list2 = new Integer[tree2.size()];
list2 = tree2.toArray(list2);

System.out.println(new ArrayList<Integer>(Arrays.asList(list2)) + "\n");

}

}

output:

run:
The height of tree is 0
The height of tree is 1
The height of tree is 2
The height of tree is 2
The height of tree is 3
The breadth-first traversal is Green Blue Red White
The pre-order traversal is Green Blue Red White
The breadth-first traversal is Tom George Jean Jane Kevin Jen Peter Kim Susan Michael Michelle
The height of tree1 is 8
The breadth-first traversal for tree2 is 50 45 59 35 48 51 58
The height of tree2 is 4
The breadth-first traversal for tree3 is 50 48 52 58
The height of tree3 is 3
tree2 contains all of tree3 ? false

The breadth-first traversal for tree2 is 50 45 59 35 48 51 22 58 52
The height of tree2 is 5
The breadth-first traversal for tree2 is 22 52
The height of tree2 is 2
The breadth-first traversal for tree3 is 50 48 58
The height of tree3 is 2
[35, 45, 48, 50, 51, 58, 59]
[35, 45, 48, 50, 51, 58, 59]

BUILD SUCCESSFUL (total time: 0 seconds)