Java如何通过recursion把一个数组array生成一个二叉树binary tree?

Question

1.题目描述
你好，我需要用recursion的方法把一个array生成一个binary tree with linked structure。比如说给定的array是 , 需生成的结果：。
已经给了10个文件，关系如下：
我的任务是需要在IntBST.java中创建一个叫makeBinaryTree的method来实现以上需求，其余所有文件中内容都是提前给定的，不需要修改。

1. 题目来源及自己的思路

我的思路是把array中点作为root，用recursion分别把左、右边subarray的中点作为left tree(t1)和right tree(t2)的root，最后再把两边的t1和t2连接起来。intBST class最后makeBinaryTree中//complete this method这行后面是我写的code。我运行出来的有NullPointerException,可能是root那里有错，别的地方可能也有不少问题。作为Java新手小白，我思路有点混乱，请大神指点，该如何修改。不胜感激！

1. 相关代码

Queue.java

public interface Queue<E> {
    int size();
    boolean isEmpty(); 
    void enqueue(E e);
    E first();
    E dequeue();
}

LinkedQueue.java

public class LinkedQueue<E> implements Queue<E> {
    public LinkedQueue() { }
    @Override
    public int size() { return list.size(); }
    @Override
    public boolean isEmpty() { return list.isEmpty(); }
    @Override
    public void enqueue(E element) { list.addLast(element); }
    @Override
    public E first() { return list.first(); }
    @Override
    public E dequeue() { return list.removeFirst(); }
    public String toString() {return list.toString();}
}

Tree.java

import java.util.Iterator;
/**
 * An interface for a tree where nodes can have an arbitrary number of children. * * @author Michael T. Goodrich
 * @author Roberto Tamassia
 * @author Michael H. Goldwasser
 */public interface Tree<E> extends Iterable<E> {
  /**
 * Returns the root Position of the tree (or null if tree is empty). * @return root Position of the tree (or null if tree is empty)
 */ Node<E> root();
 /**
 * Returns the Position of p's parent (or null if p is root). * * @param p A valid Position within the tree
 * @return Position of p's parent (or null if p is root)
 * @throws IllegalArgumentException if p is not a valid Position for this tree.
 */ Node<E> parent(Node<E> p) throws IllegalArgumentException;
 /**
 * Returns an iterable collection of the Positions representing p's children. * * @param p A valid Position within the tree
 * @return iterable collection of the Positions of p's children
 * @throws IllegalArgumentException if p is not a valid Position for this tree.
 */ Iterable<Node<E>> children(Node<E> p)
                                   throws IllegalArgumentException;
 /**
 * Returns the number of children of Position p. * * @param p A valid Position within the tree
 * @return number of children of Position p
 * @throws IllegalArgumentException if p is not a valid Position for this tree.
 */ int numChildren(Node<E> p) throws IllegalArgumentException;
 /**
 * Returns true if Position p has one or more children. * * @param p A valid Position within the tree
 * @return true if p has at least one child, false otherwise
 * @throws IllegalArgumentException if p is not a valid Position for this tree.
 */ boolean isInternal(Node<E> p) throws IllegalArgumentException;
 /**
 * Returns true if Position p does not have any children. * * @param p A valid Position within the tree
 * @return true if p has zero children, false otherwise
 * @throws IllegalArgumentException if p is not a valid Position for this tree.
 */ boolean isExternal(Node<E> p) throws IllegalArgumentException;
 /**
 * Returns true if Position p represents the root of the tree. * * @param p A valid Position within the tree
 * @return true if p is the root of the tree, false otherwise
 * @throws IllegalArgumentException if p is not a valid Position for this tree.
 */ boolean isRoot(Node<E> p) throws IllegalArgumentException;
 /**
 * Returns the number of nodes in the tree. * @return number of nodes in the tree
 */ int size();
 /**
 * Tests whether the tree is empty. * @return true if the tree is empty, false otherwise
 */ boolean isEmpty();
 /**
 * Returns an iterator of the elements stored in the tree. * @return iterator of the tree's elements
 */ Iterator<E> iterator();
 /**
 * Returns an iterable collection of the positions of the tree. * @return iterable collection of the tree's positions
 */ Iterable<Node<E>> positions();
}

AbstractTree.java

import net.datastructures.Queue;
import net.datastructures.LinkedQueue;
import java.util.Iterator;
import java.util.List; // for use as snapshot iterator
import java.util.ArrayList; // for use as snapshot iterator
/**
 * An abstract base class providing some functionality of the Tree interface. * * The following three methods remain abstract, and must be * implemented by a concrete subclass: root, parent, children. Other * methods implemented in this class may be overridden to provide a * more direct and efficient implementation. * * @author Michael T. Goodrich
 * @author Roberto Tamassia
 * @author Michael H. Goldwasser
 */public abstract class AbstractTree<E> implements Tree<E> {
  /**
 * Returns true if Node p has one or more children. * * @param p A valid Node within the tree
 * @return true if p has at least one child, false otherwise
 * @throws IllegalArgumentException if p is not a valid Node for this tree.
 */ @Override
 public boolean isInternal(Node<E> p) { return numChildren(p) > 0; }
  /**
 * Returns true if Node p does not have any children. * * @param p A valid Node within the tree
 * @return true if p has zero children, false otherwise
 * @throws IllegalArgumentException if p is not a valid Node for this tree.
 */ @Override
 public boolean isExternal(Node<E> p) { return numChildren(p) == 0; }
  /**
 * Returns true if Node p represents the root of the tree. * * @param p A valid Node within the tree
 * @return true if p is the root of the tree, false otherwise
 */ @Override
 public boolean isRoot(Node<E> p) { return p == root(); }
  /**
 * Returns the number of children of Node p. * * @param p A valid Node within the tree
 * @return number of children of Node p
 * @throws IllegalArgumentException if p is not a valid Node for this tree.
 */ @Override
 public int numChildren(Node<E> p) {
    int count=0;
 for (Node child : children(p)) count++;
 return count;
 }
  /**
 * Returns the number of nodes in the tree. * @return number of nodes in the tree
 */ @Override
 public int size() {
    int count=0;
 for (Node p : positions()) count++;
 return count;
 }
  /**
 * Tests whether the tree is empty. * @return true if the tree is empty, false otherwise
 */ @Override
 public boolean isEmpty() { return size() == 0; }
  //---------- support for computing depth of nodes and height of (sub)trees ----------
 /** Returns the number of levels separating Node p from the root.
 * * @param p A valid Node within the tree
 * @throws IllegalArgumentException if p is not a valid Node for this tree.
 */ public int depth(Node<E> p) throws IllegalArgumentException {
    if (isRoot(p))
      return 0;
 else return 1 + depth(parent(p));
 }
  /** Returns the height of the tree.
 * * Note: This implementation works, but runs in O(n^2) worst-case time. */ private int heightBad() {             // works, but quadratic worst-case time
 int h = 0;
 for (Node<E> p : positions())
      if (isExternal(p))                // only consider leaf positions
 h = Math.max(h, depth(p));
 return h;
 }
  /**
 * Returns the height of the subtree rooted at Node p. * * @param p A valid Node within the tree
 * @throws IllegalArgumentException if p is not a valid Node for this tree.
 */ public int height(Node<E> n) throws IllegalArgumentException {
    int h = 0; // base case if p is external
 for (Node<E> c : children(n))
      h = Math.max(h, 1 + height(c));
 return h;
 }
  //---------- support for various iterations of a tree ----------
 //---------------- nested ElementIterator class ---------------- /* This class adapts the iteration produced by positions() to return elements. */ private class ElementIterator implements Iterator<E> {
    Iterator<Node<E>> posIterator = positions().iterator();
 public boolean hasNext() { return posIterator.hasNext(); }
    public E next() { return posIterator.next().getElement(); } // return element!
 public void remove() { posIterator.remove(); }
  }
  /**
 * Returns an iterator of the elements stored in the tree. * @return iterator of the tree's elements
 */ @Override
 public Iterator<E> iterator() { return new ElementIterator(); }
  /**
 * Returns an iterable collection of the positions of the tree. * @return iterable collection of the tree's positions
 */ @Override
 public Iterable<Node<E>> positions() { return preorder(); }
  /**
 * Adds positions of the subtree rooted at Node p to the given * snapshot using a preorder traversal * @param p Node serving as the root of a subtree
 * @param snapshot a list to which results are appended
 */ private void preorderSubtree(Node<E> p, List<Node<E>> snapshot) {
    snapshot.add(p); // for preorder, we add position p before exploring subtrees
 for (Node<E> c : children(p))
      preorderSubtree(c, snapshot);
 }
  /**
 * Returns an iterable collection of positions of the tree, reported in preorder. * @return iterable collection of the tree's positions in preorder
 */ public Iterable<Node<E>> preorder() {
    List<Node<E>> snapshot = new ArrayList<>();
 if (!isEmpty())
      preorderSubtree(root(), snapshot); // fill the snapshot recursively
 return snapshot;
 }
  /**
 * Adds positions of the subtree rooted at Node p to the given * snapshot using a postorder traversal * @param p Node serving as the root of a subtree
 * @param snapshot a list to which results are appended
 */ private void postorderSubtree(Node<E> p, List<Node<E>> snapshot) {
    for (Node<E> c : children(p))
      postorderSubtree(c, snapshot);
 snapshot.add(p); // for postorder, we add position p after exploring subtrees
 }
  /**
 * Returns an iterable collection of positions of the tree, reported in postorder. * @return iterable collection of the tree's positions in postorder
 */ public Iterable<Node<E>> postorder() {
    List<Node<E>> snapshot = new ArrayList<>();
 if (!isEmpty())
      postorderSubtree(root(), snapshot); // fill the snapshot recursively
 return snapshot;
 }
  /**
 * Returns an iterable collection of positions of the tree in breadth-first order. * @return iterable collection of the tree's positions in breadth-first order
 */ public Iterable<Node<E>> breadthfirst() {
    List<Node<E>> snapshot = new ArrayList<>();
 if (!isEmpty()) {
      Queue<Node<E>> fringe = new LinkedQueue<>();
 fringe.enqueue(root()); // start with the root
 while (!fringe.isEmpty()) {
        Node<E> p = fringe.dequeue(); // remove from front of the queue
 snapshot.add(p); // report this position
 for (Node<E> c : children(p))
          fringe.enqueue(c); // add children to back of queue
 }
    }
    return snapshot;
 }
}

BinaryTree.java

public interface BinaryTree<E> extends Tree<E> {
  /**
 * Returns the Node of p's left child (or null if no child exists). * * @param p A valid Node within the tree
 * @return the Node of the left child (or null if no child exists)
 * @throws IllegalArgumentException if p is not a valid Node for this tree
 */ Node<E> left(Node<E> p) throws IllegalArgumentException;
 /**
 * Returns the Node of p's right child (or null if no child exists). * * @param p A valid Node within the tree
 * @return the Node of the right child (or null if no child exists)
 * @throws IllegalArgumentException if p is not a valid Node for this tree
 */ Node<E> right(Node<E> p) throws IllegalArgumentException;
 /**
 * Returns the Node of p's sibling (or null if no sibling exists). * * @param p A valid Node within the tree
 * @return the Node of the sibling (or null if no sibling exists)
 * @throws IllegalArgumentException if p is not a valid Node for this tree
 */ Node<E> sibling(Node<E> p) throws IllegalArgumentException;
}

AbstractBinaryTree.java

import java.util.List;
import java.util.ArrayList;
/**
 * An abstract base class providing some functionality of the BinaryTree interface. * * The following five methods remain abstract, and must be implemented * by a concrete subclass: size, root, parent, left, right. * * @author Michael T. Goodrich
 * @author Roberto Tamassia
 * @author Michael H. Goldwasser
 */public abstract class AbstractBinaryTree<E> extends AbstractTree<E>
                                             implements BinaryTree<E> {
  /**
 * Returns the Node of p's sibling (or null if no sibling exists). * * @param p A valid Node within the tree
 * @return the Node of the sibling (or null if no sibling exists)
 * @throws IllegalArgumentException if p is not a valid Node for this tree
 */ @Override
 public Node<E> sibling(Node<E> p) {
    Node<E> parent = parent(p);
 if (parent == null) return null; // p must be the root
 if (p == left(parent))                            // p is a left child
 return right(parent); // (right child might be null)
 else // p is a right child
 return left(parent); // (left child might be null)
 }
  /**
 * Returns the number of children of Node p. * * @param p A valid Node within the tree
 * @return number of children of Node p
 * @throws IllegalArgumentException if p is not a valid Node for this tree.
 */ @Override
 public int numChildren(Node<E> p) {
    int count=0;
 if (left(p) != null)
      count++;
 if (right(p) != null)
      count++;
 return count;
 }
  /**
 * Returns an iterable collection of the Nodes representing p's children. * * @param p A valid Node within the tree
 * @return iterable collection of the Nodes of p's children
 * @throws IllegalArgumentException if p is not a valid Node for this tree.
 */ @Override
 public Iterable<Node<E>> children(Node<E> p) {
    List<Node<E>> snapshot = new ArrayList<>(2); // max capacity of 2
 if (left(p) != null)
      snapshot.add(left(p));
 if (right(p) != null)
      snapshot.add(right(p));
 return snapshot;
 }
  /**
 * Adds positions of the subtree rooted at Node p to the given * snapshot using an inorder traversal * @param p Node serving as the root of a subtree
 * @param snapshot a list to which results are appended
 */ private void inorderSubtree(Node<E> p, List<Node<E>> snapshot) {
    if (left(p) != null)
      inorderSubtree(left(p), snapshot);
 snapshot.add(p);
 if (right(p) != null)
      inorderSubtree(right(p), snapshot);
 }
  /**
 * Returns an iterable collection of positions of the tree, reported in inorder. * @return iterable collection of the tree's positions reported in inorder
 */ public Iterable<Node<E>> inorder() {
    List<Node<E>> snapshot = new ArrayList<>();
 if (!isEmpty())
      inorderSubtree(root(), snapshot); // fill the snapshot recursively
 return snapshot;
 }
  /**
 * Returns an iterable collection of the positions of the tree using inorder traversal * @return iterable collection of the tree's positions using inorder traversal
 */ @Override
 public Iterable<Node<E>> positions() {
    return inorder();
 }
}

Node.java

public class Node<E> {
   private E element; // an element stored at this node
 private Node<E> parent; // a reference to the parent node (if any)
 private Node<E> left; // a reference to the left child (if any)
 private Node<E> right; // a reference to the right child (if any)
 /**
 * Constructs a node with the given element and neighbors. * * @param e the element to be stored
 * @param above reference to a parent node
 * @param leftChild reference to a left child node
 * @param rightChild reference to a right child node
 */ public Node(E e, Node<E> above, Node<E> leftChild, 
Node<E> rightChild) {
      element = e;
 parent = above;
 left = leftChild;
 right = rightChild;
 }
    // accessor methods
 public E getElement() { return element; }
    public Node<E> getParent() { return parent; }
    public Node<E> getLeft() { return left; }
    public Node<E> getRight() { return right; }
    // update methods
 public void setElement(E e) { element = e; }
    public void setParent(Node<E> parentNode) { parent = parentNode; }
    public void setLeft(Node<E> leftChild) { left = leftChild; }
    public void setRight(Node<E> rightChild) { right = rightChild; }
}

NodeBinaryTree.java

import java.util.Stack;
/**
 * Concrete implementation of a binary tree using a node-based, linked * structure. * * @author Michael T. Goodrich
 * @author Roberto Tamassia
 * @author Michael H. Goldwasser
 */public class NodeBinaryTree<E> extends AbstractBinaryTree<E> {
   
   /** Factory function to create a new node storing element e. */
 protected Node<E> createNode(E e, Node<E> parent, Node<E> left, Node<E> right) {
      return new Node<E>(e, parent, left, right);
 }
   // NodeBinaryTree instance variables
 /** The root of the binary tree */
 public Node<E> root = null; // root of the tree
 /** The number of nodes in the binary tree */
// private int size = 0; // number of nodes in the tree
 private int size = 0;
 // constructor
 /** Construts an empty binary tree. */
 public NodeBinaryTree() { } // constructs an empty binary tree
 // nonpublic utility /**
 * Verifies that a Node belongs to the appropriate class, and is not one * that has been previously removed. Note that our current implementation does * not actually verify that the position belongs to this particular list * instance. * * @param p a Node (that should belong to this tree)
 * @return the underlying Node instance for the position
 * @throws IllegalArgumentException if an invalid position is detected
 */ /*
 * protected Node<E> validate(Node<E> p) throws IllegalArgumentException { if * (!(p instanceof Node)) throw new * IllegalArgumentException("Not valid position type"); Node<E> node = (Node<E>) * p; // safe cast if (node.getParent() == node) // our convention for defunct * node throw new IllegalArgumentException("p is no longer in the tree"); return * node; } */
 // accessor methods (not already implemented in AbstractBinaryTree) /**
 * Returns the number of nodes in the tree. ** @return number of nodes in the tree
 */ @Override
 public int size() {
      return size;
 }
   /**
 * Returns the root Node of the tree (or null if tree is empty). ** @return root Node of the tree (or null if tree is empty)
 */ @Override
 public Node<E> root() {
      return root;
 }
   /**
 * Returns the Node of p's parent (or null if p is root). * * @param n A valid Node within the tree
 * @return Node of p's parent (or null if p is root)
 * @throws IllegalArgumentException if p is not a valid Node for this tree.
 */ @Override
 public Node<E> parent(Node<E> n) throws IllegalArgumentException {
      return n.getParent();
 }
   /**
 * Returns the Node of p's left child (or null if no child exists). * * @param n A valid Node within the tree
 * @return the Node of the left child (or null if no child exists)
 * @throws IllegalArgumentException if p is not a valid Node for this tree
 */ @Override
 public Node<E> left(Node<E> n) throws IllegalArgumentException {
      return n.getLeft();
 }
   /**
 * Returns the Node of p's right child (or null if no child exists). * * @param n A valid Node within the tree
 * @return the Node of the right child (or null if no child exists)
 * @throws IllegalArgumentException if p is not a valid Node for this tree
 */ @Override
 public Node<E> right(Node<E> n) throws IllegalArgumentException {
      return n.getRight();
 }
   // update methods supported by this class
 /**
 * Places element e at the root of an empty tree and returns its new Node. * * @param e the new element
 * @return the Node of the new element
 * @throws IllegalStateException if the tree is not empty
 */ public Node<E> addRoot(E e) throws IllegalStateException {
      if (!isEmpty())
         throw new IllegalStateException("Tree is not empty");
 root = createNode(e, null, null, null);
 size = 1;
 return root;
 }
   /**
 * Creates a new left child of Node p storing element e and returns its * Node. * * @param n the Node to the left of which the new element is inserted
 * @param e the new element
 * @return the Node of the new element
 * @throws IllegalArgumentException if p is not a valid Node for this tree
 * @throws IllegalArgumentException if p already has a left child
 */ public Node<E> addLeft(Node<E> n, E e) throws IllegalArgumentException {
      Node<E> parent = n;
 if (parent.getLeft() != null)
         throw new IllegalArgumentException("n already has a left child");
 Node<E> child = createNode(e, parent, null, null); // node child's parent is n,left is null, right is null
 parent.setLeft(child); // node child becomes the left child of parent node
 size++;
 return child;
 }
   /**
 * Creates a new right child of Node p storing element e and returns its * Node. * * @param n the Node to the right of which the new element is inserted
 * @param e the new element
 * @return the Node of the new element
 * @throws IllegalArgumentException if p is not a valid Node for this tree.
 * @throws IllegalArgumentException if p already has a right child
 */ public Node<E> addRight(Node<E> n, E e) throws IllegalArgumentException {
      Node<E> parent = n;
 if (parent.getRight() != null)
         throw new IllegalArgumentException("n already has a right child");
 Node<E> child = createNode(e, parent, null, null);
 parent.setRight(child);
 size++;
 return child;
 }
   /**
 * Replaces the element at Node p with element e and returns the replaced * element. * * @param n the relevant Node
 * @param e the new element
 * @return the replaced element
 * @throws IllegalArgumentException if p is not a valid Node for this tree.
 */ public E set(Node<E> n, E e) throws IllegalArgumentException {
      E temp = n.getElement();
 n.setElement(e);
 return temp;
 }
   /**
 * Attaches trees t1 and t2, respectively, as the left and right subtree of the * leaf Node n. As a side effect, t1 and t2 are set to empty trees. * * @param n a leaf of the tree
 * @param t1 an independent tree whose structure becomes the left child of n
 * @param t2 an independent tree whose structure becomes the right child of n
 * @throws IllegalArgumentException if p is not a valid Node for this tree
 * @throws IllegalArgumentException if p is not a leaf
 */ public void attach(Node<E> n, NodeBinaryTree<E> t1, NodeBinaryTree<E> t2) throws IllegalArgumentException {
      if (isInternal(n))
         throw new IllegalArgumentException("p must be a leaf");
 size += t1.size() + t2.size();
 if (!t1.isEmpty()) { // attach t1 as left subtree of node
 t1.root.setParent(n); // node n becomes to t1's root parent
 n.setLeft(t1.root); // t1's root becomes to the left child of n
 t1.root = null; // remove original t1 for garbage collection
 t1.size = 0; // remove original t1 for garbage collection
 }
      if (!t2.isEmpty()) { // attach t2 as right subtree of node
 t2.root.setParent(n);
 n.setRight(t2.root);
 t2.root = null;
 t2.size = 0;
 }
   }
   /**
 * Removes the node at Node p and replaces it with its child, if any. * * @param n the relevant Node
 * @return element that was removed
 * @throws IllegalArgumentException if n is not a valid Node for this tree.
 * @throws IllegalArgumentException if n has two children.
 */ public E remove(Node<E> n) throws IllegalArgumentException {
      if (numChildren(n) == 2)
         throw new IllegalArgumentException("p has two children");
 Node<E> child = (n.getLeft() != null ? n.getLeft() : n.getRight());
 if (child != null)
         child.setParent(n.getParent()); // child's grandparent becomes its parent
 if (n == root)
         root = child; // child becomes root
 else {
         Node<E> parent = n.getParent();
 if (n == parent.getLeft())
            parent.setLeft(child);
 else parent.setRight(child);
 }
      size--;
 E temp = n.getElement();
 n.setElement(null); // help garbage collection
 n.setLeft(null);
 n.setRight(null);
 n.setParent(n); // our convention for defunct node
 return temp;
 }
   
   /**
 * Print a binary tree horizontally * Modified version of https://stackoverflow.com/questions/4965335/how-to-print-binary-tree-diagram * Modified by Keith Gutfreund * @param n Node in tree to start printing from
 */ void print(Node<E> n){ 
      print ("", n); 
}
   
   public void print(String prefix, Node<E> n){
     if (n != null){
       print(prefix + "       ", right(n));
 System.out.println (prefix + ("|-- ") + n.getElement());
 print(prefix + "       ", left(n));
 }
   }
}

IntBST.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// binary search tree storing integers
public class IntBST extends NodeBinaryTree<Integer> {
   private int size = 0;
 public IntBST() {
   }
   public int size() {
      return size;
 }
   public void setSize(int s) {
      size = s;
 }
   public boolean isEmpty() {
      return size() == 0;
 }
   /**
 * Places element e at the root of an empty tree and returns its new Node. * * @param e the new element
 * @return the Node of the new element
 * @throws IllegalStateException if the tree is not empty
 */
 public Node<Integer> 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;
 }
   /**
 * Print a binary tree horizontally Modified version of * https://stackoverflow.com/questions/4965335/how-to-print-binary-tree-diagram * Modified by Keith Gutfreund * * @param n Node in tree to start printing from
 */
 public void print(Node<Integer> n) {
      print("", n);
 }
   public void print(String prefix, Node<Integer> n) {
      if (n != null) {
         print(prefix + "       ", right(n));
 System.out.println(prefix + ("|-- ") + n.getElement());
 print(prefix + "       ", left(n));
 }
   }
   public void inorderPrint(Node<Integer> n) {
      if (n == null)
         return;
//    Node<Integer> n = validate(p);
 inorderPrint(n.getLeft());
 System.out.print(n.getElement() + "  ");
 inorderPrint(n.getRight());
 }
   public Iterable<Node<Integer>> children(Node<Integer> n) {
      List<Node<Integer>> 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<Integer> n) throws IllegalArgumentException {
      if (isExternal(n)) {
         return 0;
 }
      int h = 0; // base case if p is external
 for (Node<Integer> c : children(n)) h = Math.max(h, height(c));
 return h + 1;
 }
   // Receives an array of integers and creates a binary tree
 // Input: an array of integers, a; size of a is 2^k - 1, k = 1, 2, . . . //        integers in the array are sorted in non-decreasing order // Output: an IntBST, which is a "complete" binary tree with all integers in the array a 
 
 public static IntBST makeBinaryTree(int[] a) {
 // complete this method
 
 // base case 
     IntBST tree = new IntBST();
     int middle = (a.length - 1) / 2;
     Node rootNode = new Node(a[middle],null,null,null);
     if (a.length == 1) {
         tree.root.setParent(rootNode);
         return tree;
     }
     while (a.length > 1){
         int[] leftSubArray = Arrays.copyOfRange(a,0, middle);
         int[] rightSubArray = Arrays.copyOfRange(a, middle + 1, a.length);
         IntBST t1 = makeBinaryTree(leftSubArray);
         IntBST t2 = makeBinaryTree(rightSubArray);
         // attach t1 and t2 with root
         if (!t1.isEmpty()) {
            t1.root.setParent(rootNode);
            rootNode.setLeft(t1.root);
         }
         if (!t2.isEmpty()) {
            t2.root.setParent(rootNode);
            rootNode.setRight(t2.root);
         }
      }
        return tree;
    }
  }

Hw5_P7.java

public class Hw5_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);
      System.out.println("Tree size: " + t.size());
      System.out.println("Tree height: " + t.height(t.root));
      System.out.println("");
      t.print(t.root);
    }
  }