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 T

Answer 1

等待大神解答