1.题目描述
你好,我需要用recursion的方法把一个array生成一个binary tree with linked structure。比如说给定的array是 , 需生成的结果:。
已经给了10个文件,关系如下:
我的任务是需要在IntBST.java中创建一个叫makeBinaryTree的method来实现以上需求,其余所有文件中内容都是提前给定的,不需要修改。
- 题目来源及自己的思路
我的思路是把array中点作为root,用recursion分别把左、右边subarray的中点作为left tree(t1)和right tree(t2)的root,最后再把两边的t1和t2连接起来。intBST class最后makeBinaryTree中//complete this method这行后面是我写的code。我运行出来的有NullPointerException,可能是root那里有错,别的地方可能也有不少问题。作为Java新手小白,我思路有点混乱,请大神指点,该如何修改。不胜感激!
- 相关代码
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
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…