This problem is a programming problem.
Write a recursive method named makeBinaryTree within the IntBST class, which is posted on
The IntBST class implements a binary search tree that stores integers. The IntBST class inherits
from many other classes and interfaces. All these classes and interfaces, including the IntBST
class itself, are included in the package nodeTrees. You need all files in the package for this
problem.
The makeBinaryTree method must satisfy the following requirements:
· The signature must be
public static IntBST makeBinaryTree(int[] a)
You must not change the signature. But, you may write additional method(s) within
IntBST class if needed.
· This method receives an array of integers with size n = 2k – 1, k >= 1. So, n = 1, 3, 7, 15, and so on. The integers in the array are sorted in non-decreasing order.
· This method then builds a "complete" binary search tree that contains all integers in the array, and print it on the screen (see an example below).
You must also print the size and the height of the tree. Here, a complete binary tree is a binary tree where all leaf nodes have the same depth and all internal nodes have 2 children. (this definition is slightly different from the definition in the book).
· A tree must be built recursively.
After implementing the method within IntBST, use the provided Hw3_p7.java program to test your method.
If you run the program with the following array (a4 in the main method):
{10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150}
Note that the tree is printed horizontally.
Do not change any other methods in the IntBST class and any other files in the nodeTrees package. However, you may override a method in a superclass of IntBST and redefine the method within IntBST, if needed.
Hint: High-level description of one possible implementation:
· Split the given array into three parts: left subarray, a root node r, right subarray. Suppose for example, that the given array is [10, 20, 30, 40, 50, 60, 70]. Then, the left subarray is [10, 20, 30], r = 40, and the right subarray is [50, 60, 70].
· Build a binary tree lt from the left subarray and build a binary tree rt from the right subarray. When you build each subtree, you must do it recursively.
· Make lt as the left subtree of r and make rt as the right subtree of r. You need to figure out how to implement this. I suggest that you study other programs in the nodeTrees package.
Classes provided :
package nodeTrees;
import java.util.ArrayList;
import java.util.List;
public class IntBST extends NodeBinaryTree {
private int size = 0;
public IntBST() { }
public int size() {
return size;
}
public void setSize(int s) { size = s; }
public boolean isEmpty() {
return size() == 0;
}
public Node addRoot(Integer e) throws IllegalStateException {
if (size != 0)
throw new IllegalStateException("Tree is not empty");
root = createNode(e, null, null, null);
size = 1;
return root;
}
public void print(Node n){ print ("", n); }
public void print(String prefix, Node n){
if (n != null){
print(prefix + " ", right(n));
System.out.println (prefix + ("|-- ") + n.getElement());
print(prefix + " ", left(n));
}
}
public void inorderPrint(Node n) {
if (n == null)
return;
inorderPrint(n.getLeft());
System.out.print(n.getElement() + " ");
inorderPrint(n.getRight());
}
public Iterable> children(Node n) {
List> snapshot = new ArrayList<>(2); // max capacity of 2
if (left(n) != null)
snapshot.add(left(n));
if (right(n) != null)
snapshot.add(right(n)); return snapshot;
}
public int height(Node n) throws IllegalArgumentException {
if (isExternal(n)) { return 0; }
int h = 0; // base case if p is external
for (Node c : children(n)) h = Math.max(h, height(c)); return h + 1;
}
public static IntBST makeBinaryTree(int[] a){
// complete this method
}
}
public class Hw3_p7 {
public static void main(String[] args) {
IntBST t = new IntBST();
int[] a1 = {10};
int[] a2 = {10, 20, 30};
int[] a3 = {10, 20, 30, 40, 50, 60, 70};
int[] a4 = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150};
t = IntBST.makeBinaryTree(a4); // test with other arrays too
System.out.println("Tree size: " + t.size());
System.out.println("Tree height: " + t.height(t.root));
System.out.println("");
t.print(t.root);
}
}
