Timondm

Timondm 查看完整档案

填写现居城市  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 该用户太懒什么也没留下

个人动态

Timondm 关注了用户 · 11月2日

justjavac @justjavac

会写点 js 代码

关注 14455

Timondm 提出了问题 · 11月1日

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

1.题目描述
你好,我需要用recursion的方法把一个array生成一个binary tree with linked structure。比如说给定的array是屏幕快照 2020-11-01 00.12.55.png , 需生成的结果:屏幕快照 2020-11-01 00.13.10.png
已经给了10个文件,关系如下:image
我的任务是需要在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);
    }
  }

关注 1 回答 0

Timondm 赞了回答 · 10月3日

解决Java中怎样逐行读取文件信息为object并生成linked list?

梳理一下诉求:
1、输入一个文本文件,一行一条记录,有三个属性:id,name,salary,由逗号隔开;
2、逐行读取记录,将记录存放在SalariedEmployee对象中,所有记录存放于SalariedEmployeeList容器中,并提供根据name搜索记录的方法。


核心代码如下:

// 1.读取文本文件
SalariedEmployeeList employeeList = new SalariedEmployeeList();
try(BufferedReader br = new BufferedReader(new InputStreamReader(
new FileInputStream("your text file path")))) {
    String line = null;
    while ((line = br.readLine()) != null) {
        // line为空或者记录不够就略过
        if(line.isEmpty()) {
            continue;
        }
        String[] fields = line.split(",");
        if(fields.length() != 3) {
            continue;
        }
        SalariedEmployee employee = new SalariedEmployee(Integer.parseInt(fields[0],
        fields[1], Double.parseDouble(fields[2]);
        employeeList.add(employee);
    }
}

// SalariedEmployeeList类
// 从题主问题描述中没有看到这个类的声明,大体理解题主想要的意思是这个类本身就是一个容器,
// 可以容纳SalariedEmployee对象,最后提供一个根据name来查询Employee的方法,因此我就直接
// 将SalariedEmployeeList继承LinkedList,这样实现起来最快。
public class SalariedEmployeeList extends LinkedList<SalariedEmployee> {
    // 其他代码省略...
    // 根据name进行SalariedEmployee查询
    public SalariedEmployee findByName(String name) {
        for(SalariedEmployee employee : this) {
            if(employee.getName().equals(name)) {
                return employee;
            }
        }
        // 没有找到返回null
        return null;
    }
}

以上是代码的主要实现逻辑,应该是题主所想吧,如有问题,可以追问,望采纳,谢谢。

关注 2 回答 2

Timondm 提出了问题 · 10月3日

解决Java中怎样逐行读取文件信息为object并生成linked list?

### 大家好,我是刚学Java的小白,现在遇到问题需请教大神。我需要从一个.txt文件中逐行读取员工信息(id,name,salary),把每行信息存储成一个object,再把这些object(这些object 是SalariedEmployee class的 instance) 放在一个linked list(SalariedEmployeeList class)中。在 SalariedEmployeeList class中 建立一个 findByName method, 查找员工姓名,如果有该姓名,则返回该姓名所在的object。在main method中调用findByName,打印出该员工所有信息。

### 题目来源及自己的思路

### 相关代码
粘贴代码文本(请勿用截图)

txt.file如下:

1, Kelsey, 65000
2, Jake, 89000
3, Carlos, 105000
4, Clarence, 58000
5, Pacheco, 68000

SalariedEmployee class

public class SalariedEmployee {
// instance variable
    public int empId;
    public String name;
    public double salary;

    // constructor
    public SalariedEmployee(int empId, String name, double salary) {
        this.empId = empId;
        this.name = name;
        this.salary = salary;
    }
    // get methods
    public int getEmpId() {
        return empId;
    }

    public String getName(){
        return name;
    }

    public double getSalary(){
        return salary;
    }

SalariedEmployeeList

private static class Node {
        private SalariedEmployee element;
        private Node next;
        public Node(SalariedEmployee e, Node n) {
            element = e;
            next = n;
        }

        public SalariedEmployee getElement() { return element; }

        public Node getNext() { return next; }

        public void setNext(Node n) { next = n; }
      }

    // instance variables of the SinglyLinkedList
    private Node head = null;               
    private Node tail = null;               
    private int size = 0;                      
    public SalariedEmployeeList() { }              

    // access methods
    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }
    public SalariedEmployee first() {             
        if (isEmpty()) return null;
        return head.getElement();
    }

    public SalariedEmployee last() {              
        if (isEmpty()) return null;
        return tail.getElement();
    }

    public void addFirst(SalariedEmployee e) {                
        head = new Node(e, head);              
        if (size == 0)
            tail = head;                           
        size++;
    }

    public void addLast(SalariedEmployee e) {                 
        Node newest = new Node(e, null);    
        if (isEmpty())
            head = newest;                         
        else
            tail.setNext(newest);                  
        tail = newest;                           
        size++;
    }

    public SalariedEmployee removeFirst() {                   
        if (isEmpty()) return null;              
        SalariedEmployee answer = head.getElement();
        head = head.getNext();                   
        size--;
        if (size == 0)
            tail = null;                          
        return answer;
    }

    public SalariedEmployee findByName(String name) {
        SalariedEmployeeList selist = new SalariedEmployeeList();
        for (int i = 0; i < selist.size; i++) {
            if (SalariedEmployeeList (selist.get(i)).getname == name);
                return selist.get(i);
            return null;
    }
}

    public void printList() {
        SalariedEmployee se = null;
        Node walk = head;
        while (walk != null) {
            se = walk.getElement();
            System.out.println("Employee id = " + se.getEmpId());
            System.out.println("Name = " + se.getName());
            System.out.println("Salary = " + se.getSalary());
            System.out.println();
            walk = walk.getNext();
        }
    }

main method

public class Hw3_Part2 {
    public static void main(String[] args) throws IOException {
        String content = new String();
        Scanner fileInput = new Scanner(new File("/Users/hw3_employees.txt"));
        LinkedList <String> selist = new LinkedList <String>();
        while(fileInput.hasNextLine()){
            content = fileInput.nextLine();
            selist.add(content);
        }
        System.out.println(selist);
        fileInput.close();
    }
}

### 你期待的结果是什么?实际看到的错误信息又是什么?

我遇到以下问题:
1、读取文件时把所有行的员工信息都变成了一整个linked list:
[1, Kelsey, 65000,2, Jake, 89000,3, Carlos, 105000,4, Clarence, 58000,5, Pacheco, 68000],这不是我想要的。我想要[[1, Kelsey, 65000],[2, Jake, 89000],[3, Carlos, 105000],[4, Clarence, 58000],[5, Pacheco, 68000]],怎样提取每名员工的信息变成SalariedEmployee class的一个object呢?

2、findByName method 中报错:“cannot resolve method "get" in SalariedEmployeeList“, .get()不是linked list中自带的吗?怎样解决?

我现在思路有点混乱,不知道该用什么方法。还请大神多多指点,手下留情,谢谢!

关注 2 回答 2

Timondm 关注了专栏 · 10月2日

Java进阶路线

java技术分享,从小白到巨人的成长过程

关注 2052

Timondm 关注了标签 · 10月2日

java

Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台(即 JavaSE, JavaEE, JavaME)的总称。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

Java编程语言的风格十分接近 C++ 语言。继承了 C++ 语言面向对象技术的核心,Java舍弃了 C++ 语言中容易引起错误的指針,改以引用取代,同时卸载原 C++ 与原来运算符重载,也卸载多重继承特性,改用接口取代,增加垃圾回收器功能。在 Java SE 1.5 版本中引入了泛型编程、类型安全的枚举、不定长参数和自动装/拆箱特性。太阳微系统对 Java 语言的解释是:“Java编程语言是个简单、面向对象、分布式、解释性、健壮、安全与系统无关、可移植、高性能、多线程和动态的语言”。

版本历史

重要版本号版本代号发布日期
JDK 1.01996 年 1 月 23 日
JDK 1.11997 年 2 月 19 日
J2SE 1.2Playground1998 年 12 月 8 日
J2SE 1.3Kestrel2000 年 5 月 8 日
J2SE 1.4Merlin2002 年 2 月 6 日
J2SE 5.0 (1.5.0)Tiger2004 年 9 月 30 日
Java SE 6Mustang2006 年 11 月 11 日
Java SE 7Dolphin2011 年 7 月 28 日
Java SE 8JSR 3372014 年 3 月 18 日
最新发布的稳定版本:
Java Standard Edition 8 Update 11 (1.8.0_11) - (July 15, 2014)
Java Standard Edition 7 Update 65 (1.7.0_65) - (July 15, 2014)

更详细的版本更新查看 J2SE Code NamesJava version history 维基页面

新手帮助

不知道如何开始写你的第一个 Java 程序?查看 Oracle 的 Java 上手文档

在你遇到问题提问之前,可以先在站内搜索一下关键词,看是否已经存在你想提问的内容。

命名规范

Java 程序应遵循以下的 命名规则,以增加可读性,同时降低偶然误差的概率。遵循这些命名规范,可以让别人更容易理解你的代码。

  • 类型名(类,接口,枚举等)应以大写字母开始,同时大写化后续每个单词的首字母。例如:StringThreadLocaland NullPointerException。这就是著名的帕斯卡命名法。
  • 方法名 应该是驼峰式,即以小写字母开头,同时大写化后续每个单词的首字母。例如:indexOfprintStackTraceinterrupt
  • 字段名 同样是驼峰式,和方法名一样。
  • 常量表达式的名称static final 不可变对象)应该全大写,同时用下划线分隔每个单词。例如:YELLOWDO_NOTHING_ON_CLOSE。这个规范也适用于一个枚举类的值。然而,static final 引用的非不可变对象应该是驼峰式。

Hello World

public class HelloWorld {
    public static void main(String[] args) {
        System.out.println("Hello, World!");
    }
}

编译并调用:

javac -d . HelloWorld.java
java -cp . HelloWorld

Java 的源代码会被编译成可被 Java 命令执行的中间形式(用于 Java 虚拟机的字节代码指令)。

可用的 IDE

学习资源

常见的问题

下面是一些 SegmentFault 上在 Java 方面经常被人问到的问题:

(待补充)

关注 108936

Timondm 关注了标签 · 10月2日

python

Python(发音:英[ˈpaɪθən],美[ˈpaɪθɑ:n]),是一种面向对象、直译式电脑编程语言,也是一种功能强大的通用型语言,已经具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法非常简捷和清晰,与其它大多数程序设计语言不一样,它使用缩进来定义语句。

Python支持命令式程序设计、面向对象程序设计、函数式编程、面向切面编程、泛型编程多种编程范式。与Scheme、Ruby、Perl、Tcl等动态语言一样,Python具备垃圾回收功能,能够自动管理存储器使用。它经常被当作脚本语言用于处理系统管理任务和网络程序编写,然而它也非常适合完成各种高级任务。Python虚拟机本身几乎可以在所有的作业系统中运行。使用一些诸如py2exe、PyPy、PyInstaller之类的工具可以将Python源代码转换成可以脱离Python解释器运行的程序。

Python的主要参考实现是CPython,它是一个由社区驱动的自由软件。目前由Python软件基金会管理。基于这种语言的相关技术正在飞快的发展,用户数量快速扩大,相关的资源非常多。

关注 103650

Timondm 关注了标签 · 10月2日

程序员

一种近几十年来出现的新物种,是工业革命的产物。英文(Programmer Monkey)是一种非常特殊的、可以从事程序开发、维护的动物。一般分为程序设计猿和程序编码猿,但两者的界限并不非常清楚,都可以进行开发、维护工作,特别是在中国,而且最重要的一点,二者都是一种非常悲剧的存在。

国外的程序员节

国外的程序员节,(英语:Programmer Day,俄语:День программи́ста)是一个俄罗斯官方节日,日期是每年的第 256(0x100) 天,也就是平年的 9 月 13 日和闰年的 9 月 12 日,选择 256 是因为它是 2 的 8 次方,比 365 少的 2 的最大幂。

1024程序员节,中国程序员节

1024是2的十次方,二进制计数的基本计量单位之一。程序员(英文Programmer)是从事程序开发、维护的专业人员。程序员就像是一个个1024,以最低调、踏实、核心的功能模块搭建起这个科技世界。1GB=1024M,而1GB与1级谐音,也有一级棒的意思。

从2012年,SegmentFault 创办开始我们就从网络上引导社区的开发者,发展成中国程序员的节日 :) 计划以后每年10月24日定义为程序员节。以一个节日的形式,向通过Coding 改变世界,也以实际行动在浮躁的世界里,固执地坚持自己对于知识、技术和创新追求的程序员们表示致敬。并于之后的最为临近的周末为程序员们举行了一个盛大的狂欢派对。

2015的10月24日,我们SegmentFault 也在5个城市同时举办黑客马拉松这个特殊的形式,聚集开发者开一个编程大爬梯。

特别推荐:

【SF 黑客马拉松】:http://segmentfault.com/hacka...
【1024程序员闯关秀】小游戏,欢迎来挑战 http://segmentfault.com/game/

  • SF 开发者交流群:206236214
  • 黑客马拉松交流群:280915731
  • 开源硬件交流群:372308136
  • Android 开发者交流群:207895295
  • iOS 开发者交流群:372279630
  • 前端开发者群:174851511

欢迎开发者加入~

交流群信息


程序员相关问题集锦:

  1. 《程序员如何选择自己的第二语言》
  2. 《如何成为一名专业的程序员?》
  3. 《如何用各种编程语言书写hello world》
  4. 《程序员们最常说的谎话是什么?》
  5. 《怎么加入一个开源项目?》
  6. 《是要精于单挑,还是要善于合作?》
  7. 《来秀一下你屎一般的代码...》
  8. 《如何区分 IT 青年的“普通/文艺/二逼”属性?》
  9. 程序员必读书籍有哪些?
  10. 你经常访问的技术社区或者技术博客(IT类)有哪些?
  11. 如何一行代码弄崩你的程序?我先来一发
  12. 编程基础指的是什么?
  13. 后端零起步:学哪一种比较好?
  14. 大家都用什么键盘写代码的?

爱因斯坦

程序猿崛起

关注 115177

Timondm 关注了标签 · 10月2日

数据库

数据库(Database)是按照数据结构来组织、存储和管理数据的仓库,它产生于距今五十年前,随着信息技术和市场的发展,特别是二十世纪九十年代以后,数据管理不再仅仅是存储和管理数据,而转变成用户所需要的各种数据管理的方式。数据库有很多种类型,从最简单的存储有各种数据的表格到能够进行海量数据存储的大型数据库系统都在各个方面得到了广泛的应用。

关注 7671

认证与成就

  • 获得 0 次点赞
  • 获得 4 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 4 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 10月2日
个人主页被 287 人浏览