Member Avatar for cgen

Can someone please help me go over these codes? There are no bugs in all except LinkedListBinary.java and I have no idea why. The lines that are causing me problems are:

/** Returns an iterator of the elements stored at the nodes */
  public Iterator<E> iterator() {
	   Iterable<Position<E>> positions = positions();
	   PositionList<E> elements = new NodePositionList<E>();
	   for (Position<E> pos: positions) 
	     elements.addLast(pos.element());
	    return elements.iterator();  // An iterator of elements
   }

The error is that I can only iterate from an array or an instance of java.lang.Iterable

I attached all the files, excluding the exception classes

package LinkedBinaryTree;




/**
 * An interface for a binary tree, where each node can have zero, one,
 * or two children.
 */
public interface BinaryTree<E> extends Tree<E> {
  /** Returns the left child of a node. */
  public Position<E> left(Position<E> v) 
    throws InvalidPositionException, BoundaryViolationException;
  /** Returns the right child of a node. */
  public Position<E> right(Position<E> v) 
    throws InvalidPositionException, BoundaryViolationException;
  /** Returns whether a node has a left child. */
  public boolean hasLeft(Position<E> v) throws InvalidPositionException;
  /** Returns whether a node has a right child. */
  public boolean hasRight(Position<E> v) throws InvalidPositionException;
}
package LinkedBinaryTree;




/**
 * Class implementing a node of a binary tree by storing references to
 * an element, a parent node, a left node, and a right node.
 */
public class BTNode<E> implements BTPosition<E> {
  private E element;  // element stored at this node
  private BTPosition<E> left, right, parent;  // adjacent nodes
  /** Main constructor */
  public BTNode(E element, BTPosition<E> parent, 
		BTPosition<E> left, BTPosition<E> right) { 
    setElement(element);
    setParent(parent);
    setLeft(left);
    setRight(right);
  }
  /** Returns the element stored at this position */
  public E element() { return element; }
  /** Sets the element stored at this position */
  public void setElement(E o) { element=o; }
  /** Returns the left child of this position */
  public BTPosition<E> getLeft() { return left; }
  /** Sets the left child of this position */
  public void setLeft(BTPosition<E> v) { left=v; }
  /** Returns the right child of this position */
  public BTPosition<E> getRight() { return right; }
  /** Sets the right child of this position */
  public void setRight(BTPosition<E> v) { right=v; }
  /** Returns the parent of this position */
  public BTPosition<E> getParent() { return parent; }
  /** Sets the parent of this position */
  public void setParent(BTPosition<E> v) { parent=v; }
}
package LinkedBinaryTree;

public interface BTPosition<E> extends Position<E> {
	public void setElement(E o);
	public BTPosition<E> getLeft();
	public void setLeft(BTPosition<E> v);
	public BTPosition<E> getRight();
	public void setRight(BTPosition<E> v);
	public BTPosition<E> getParent();
	public void setParent(BTPosition<E> v);
}
package LinkedBinaryTree;

public class DNode<E> implements Position<E>{
		protected E element;
		protected DNode<E> next, prev;
		public DNode(){ this(null, null, null);}
		public DNode(DNode<E> p, DNode<E> n, E e)
		{
			element = e;
			prev = p;
			next = n;
		}
		public E element() throws InvalidPositionException { return element;}
		public DNode<E> getPrev() { return prev;}
		public DNode<E> getNext() { return next;}
		public void setNext(DNode<E> newNext) { next = newNext;}
		public void setPrev(DNode<E> newPrev) { prev = newPrev;}
		public void setElement(E newElem) { element = newElem;}

}
package LinkedBinaryTree;

public interface Iterable<T> {
	public Iterator<T> iterator();
}
package LinkedBinaryTree;

public interface Iterator<E> {

	public boolean hasNext();
	public E next();
	public void remove();
}
package LinkedBinaryTree;



/**
  * An implementation of the BinaryTree interface by means of a linked structure.
  */
public class LinkedBinaryTree<E> implements BinaryTree<E>, Tree<E> {
  protected BTPosition<E> root;	// reference to the root
  protected int size;		// number of nodes
  /**  Creates an empty binary tree. */
  public LinkedBinaryTree() { 		    
    root = null;  // start with an empty tree
    size = 0;
  }
  /** Returns the number of nodes in the tree. */
  public int size() {
    return size; 
  } 
  /** Returns whether a node is internal. */
  public boolean isInternal(Position<E> v) throws InvalidPositionException {
    checkPosition(v);		// auxiliary method
    return (hasLeft(v) || hasRight(v));
  }
  /** Returns whether a node is the root. */
  public boolean isRoot(Position<E> v) throws InvalidPositionException { 
    checkPosition(v);
    return (v == root()); 
  }
  /** Returns whether a node has a left child. */
  public boolean hasLeft(Position<E> v) throws InvalidPositionException { 
    BTPosition<E> vv = checkPosition(v);
    return (vv.getLeft() != null);
  }
  /** Returns the root of the tree. */
  public Position<E> root() throws EmptyTreeException {
    if (root == null)
      throw new EmptyTreeException("The tree is empty");
    return root;
  } 

  
  /** Returns the left child of a node. */
  public Position<E> left(Position<E> v) 
    throws InvalidPositionException, BoundaryViolationException { 
    BTPosition<E> vv = checkPosition(v);
    Position<E> leftPos = vv.getLeft();
    if (leftPos == null)
      throw new BoundaryViolationException("No left child");
    return leftPos;
  }
  

  /** Returns the parent of a node. */
  public Position<E> parent(Position<E> v) 
    throws InvalidPositionException, BoundaryViolationException { 
    BTPosition<E> vv = checkPosition(v);
    Position<E> parentPos = vv.getParent();
    if (parentPos == null)
      throw new BoundaryViolationException("No parent");
    return parentPos; 
  }
  /** Returns an iterable collection of the children of a node. */
  public Iterable<Position<E>> children(Position<E> v) 
    throws InvalidPositionException { 
   PositionList<Position<E>> children = new NodePositionList<Position<E>>();
    if (hasLeft(v))
      children.addLast(left(v));
    if (hasRight(v))
      children.addLast(right(v));
    return children;
  }
  /** Returns an iterable collection of the tree nodes. */
  public Iterable<Position<E>> positions() {
   PositionList<Position<E>> positions = new NodePositionList<Position<E>>();
    if(size != 0)
      preorderPositions(root(), positions);  // assign positions in preorder
    return positions;
  }
  
 /** Returns an iterator of the elements stored at the nodes */
  public Iterator<E> iterator() {
	   Iterable<Position<E>> positions = positions();
	   PositionList<E> elements = new NodePositionList<E>();
	   for (Position<E> pos: positions) 
	     elements.addLast(pos.element());
	    return elements.iterator();  // An iterator of elements
   }
  
  /** Replaces the element at a node. */
  public E replace(Position<E> v, E o) 
    throws InvalidPositionException {
    BTPosition<E> vv = checkPosition(v);
    E temp = v.element();
    vv.setElement(o);
    return temp;
  }
  
  
  // Additional accessor method
  /** Return the sibling of a node */
  public Position<E> sibling(Position<E> v) 
    throws InvalidPositionException, BoundaryViolationException {
      BTPosition<E> vv = checkPosition(v);
      BTPosition<E> parentPos = vv.getParent();
      if (parentPos != null) {
	BTPosition<E> sibPos;
	BTPosition<E> leftPos = parentPos.getLeft();
	if (leftPos == vv)
	  sibPos = parentPos.getRight();
	else
	  sibPos = parentPos.getLeft();
	if (sibPos != null)
	  return sibPos;
      }
      throw new BoundaryViolationException("No sibling");
  }
  // Additional update methods
  /** Adds a root node to an empty tree */
  public Position<E> addRoot(E e) throws NonEmptyTreeException {
    if(!isEmpty())
      throw new NonEmptyTreeException("Tree already has a root");
    size = 1;
    root = createNode(e,null,null,null);
    return root;
  }
  /** Inserts a left child at a given node. */
  public Position<E>  insertLeft(Position<E> v, E e)
    throws InvalidPositionException {
    BTPosition<E> vv = checkPosition(v);
    Position<E> leftPos = vv.getLeft();
    if (leftPos != null)
      throw new InvalidPositionException("Node already has a left child");
    BTPosition<E> ww = createNode(e, vv, null, null);
    vv.setLeft(ww);
    size++;
    return ww;
  }
  



  /** Removes a node with zero or one child. */
  public E remove(Position<E> v)
    throws InvalidPositionException {
    BTPosition<E> vv = checkPosition(v);
    BTPosition<E> leftPos = vv.getLeft();
    BTPosition<E> rightPos = vv.getRight();
    if (leftPos != null && rightPos != null)
      throw new InvalidPositionException("Cannot remove node with two children");
    BTPosition<E> ww; 	// the only child of v, if any
    if (leftPos != null)
      ww = leftPos;
    else if (rightPos != null)
      ww = rightPos;
    else 		// v is a leaf
      ww = null;
    if (vv == root) { 	// v is the root
      if (ww != null)
	ww.setParent(null);
      root = ww;
    }
    else { 		// v is not the root
      BTPosition<E> uu = vv.getParent();
      if (vv == uu.getLeft())
	uu.setLeft(ww);
      else
	uu.setRight(ww);
      if(ww != null)
	ww.setParent(uu);
    }
    size--;
    return v.element();
  }




  /** Attaches two trees to be subtrees of an external node. */
  public void attach(Position<E> v, BinaryTree<E> T1, BinaryTree<E> T2) 
    throws InvalidPositionException {
    BTPosition<E> vv = checkPosition(v);
    if (isInternal(v))
      throw new InvalidPositionException("Cannot attach from internal node");
    if (!T1.isEmpty()) {
      BTPosition<E> r1 = checkPosition(T1.root());
      vv.setLeft(r1);
      r1.setParent(vv);		// T1 should be invalidated
    }
    if (!T2.isEmpty()) {
      BTPosition<E> r2 = checkPosition(T2.root());
      vv.setRight(r2);
      r2.setParent(vv);		// T2 should be invalidated
    }
  }
  /** If v is a good binary tree node, cast to BTPosition, else throw exception */
  protected BTPosition<E> checkPosition(Position<E> v) 
    throws InvalidPositionException {
    if (v == null || !(v instanceof BTPosition))
      throw new InvalidPositionException("The position is invalid");
    return (BTPosition<E>) v;
  }
  /** Creates a new binary tree node */
  protected BTPosition<E> createNode(E element, BTPosition<E> parent, 
				  BTPosition<E> left, BTPosition<E> right) {
    return new BTNode<E>(element,parent,left,right); }
  /** Creates a list storing the the nodes in the subtree of a node,
    * ordered according to the preorder traversal of the subtree. */
  protected void preorderPositions(Position<E> v, PositionList<Position<E>> pos) 
    throws InvalidPositionException {
    pos.addLast(v);
    if (hasLeft(v))
      preorderPositions(left(v), pos);	// recurse on left child
    if (hasRight(v))
      preorderPositions(right(v), pos);	// recurse on right child
  }
  
  
  public int depth(Position<E> a) {
	  BTPosition<E> x=checkPosition(a);
	  return depth(x,0);
	  }
	  public int depth(BTPosition<E> x,int n){
	  if(x.getParent()==null) return n;
	  n++;
	  int ret=depth(x.getParent(),n);
	  return ret;
	  }
	  
	  public int height(Position<E> p){
		  int h = 0;
		  if(isExternal(p))
			  return 0;
		  else{
			  Iterator<Position<E>> it = children(p).iterator();
	  	while(it.hasNext())
		  h = Math.max(h,height((Position<E>)it.next())+1);
	  	}
	  	return h;
	  }
  
public boolean isEmpty() {
	if(size == 0)
		return true;
	return false;
}

public boolean isExternal(Position<E> v) throws InvalidPositionException {
    checkPosition(v);		// auxiliary method
    return (!(hasLeft(v) || hasRight(v)));
}

public Position<E> right(Position<E> v) throws InvalidPositionException,
		BoundaryViolationException {
    BTPosition<E> vv = checkPosition(v);
    Position<E> rightPos = vv.getRight();
    if (rightPos == null)
      throw new BoundaryViolationException("No right child");
    return rightPos;
}

public boolean hasRight(Position<E> v) throws InvalidPositionException {
    BTPosition<E> vv = checkPosition(v);
    return (vv.getRight() != null);
}

}
package LinkedBinaryTree;

/**
 * File: NodePositionList.java
 * 
 * This class implements the ADT node list using a doubly-linked list.
 *
 * @author Roberto Tamassia
 * @author Michael Goodrich
 * @see BoundaryViolationException
 * @see EmptyListException
 * @see InvalidPositionException 
 */

public class NodePositionList<E> implements PositionList<E> {

  protected int numElts;            	// Number of elements in the list
  protected DNode<E> header, trailer;	// Special sentinels

  /** 
   * Constructor that creates an empty list - O(1) time
   */
  public NodePositionList() {
    numElts = 0;
    header = new DNode<E>(null, null, null);
    trailer = new DNode<E>(header, null, null);
    header.setNext(trailer);
  }

  /** 
   * Checks if position is valid for this list and converts it to DNode if it
   * is valid - O(1) time
   */
  protected DNode<E> checkPosition(Position<E> p)
    throws InvalidPositionException {
    if (p == null)
      throw new InvalidPositionException
	("Null position passed to NodeList");
    if (p == header)
	throw new InvalidPositionException
	  ("The header node is not a valid position");
    if (p == trailer)
	throw new InvalidPositionException
	  ("The trailer node is not a valid position");
    try {
      DNode<E> temp = (DNode<E>) p;
      if ((temp.getPrev() == null) || (temp.getNext() == null))
	throw new InvalidPositionException
	  ("Position does not belong to a valid NodeList");
      return temp;
    } catch (ClassCastException e) {
      throw new InvalidPositionException
	("Position is of wrong type for this list");
    }
  }

  /**
   * Returns the number of elements in the list - O(1) time
   */
  public int size() { return numElts; }

  /**
   * Returns whether the list is empty - O(1) time
   */
  public boolean isEmpty() { return (numElts == 0); }

  /**
   * Returns the first position in the list - O(1) time
   */
  public Position<E> first() throws EmptyListException {
    if (isEmpty())
      throw new EmptyListException("List is empty");
    return header.getNext();
  }

  /**
   * Returns the position before the given one - O(1) time
   */
  public Position<E> prev(Position<E> p)
    throws InvalidPositionException, BoundaryViolationException {
    DNode<E> v = checkPosition(p);
    DNode<E> prev = v.getPrev();
    if (prev == header)
      throw new BoundaryViolationException
	("Cannot advance past the beginning of the list");
    return prev;
  }

  /**
   * Inserts the given element at the beginning of the list, returning the new
   * position - O(1) time
   */
  public void addFirst(E element) {
    numElts++;
    DNode<E> newNode = new DNode<E>(header, header.getNext(), element);
    header.getNext().setPrev(newNode);
    header.setNext(newNode);
  }

  /** 
   * Inserts the given element before the given position, returning the new
   * position - O(1) time
   */
  public void addBefore(Position<E> p, E element) 
      throws InvalidPositionException {
    DNode<E> v = checkPosition(p);
    numElts++;
    DNode<E> newNode = new DNode<E>(v.getPrev(), v, element);
    v.getPrev().setNext(newNode);
    v.setPrev(newNode);
  }

  /**
   * Removes the given position from the list - O(1) time
   */
  public E remove(Position<E> p) throws InvalidPositionException {
    DNode<E> v = checkPosition(p);
    numElts--;
    DNode<E> vPrev = v.getPrev();
    DNode<E> vNext = v.getNext();
    vPrev.setNext(vNext);
    vNext.setPrev(vPrev);
    E vElem = v.element();
    v.setNext(null);
    v.setPrev(null);
    return vElem;
  }

  /**
   * Replaces the element at the given position with the new element
   * and return the old element - O(1) time
   */
  public E set(Position<E> p, E element)
      throws InvalidPositionException {
    DNode<E> v = checkPosition(p);
    E oldElt = v.element();
    v.setElement(element);
    return oldElt;
  }

  /**
   * Returns an iterator of all the elements.
   */
  public Iterator<E> iterator() {
    return new ElementIterator<E>(this);
  }

public Position<E> last() {
	return trailer.getPrev();
}

public Position<E> next(Position<E> p) throws InvalidPositionException,
		BoundaryViolationException {
	DNode<E> v = checkPosition(p);
	return v.getNext();
}

public void addLast(E e) {
    DNode<E> newNode=new DNode<E>(trailer.getPrev(), trailer, e);
    numElts++;
    trailer.getPrev().setNext(newNode);
    trailer.setPrev(newNode);
}

public void addAfter(Position<E> p, E e) throws InvalidPositionException {
	DNode<E> v= checkPosition(p);
	numElts++;
	DNode<E> newNode=new DNode<E>(v,v.getNext(), e);
	v.getNext().setPrev(newNode);
	v.setNext(newNode);
}

public Iterable<Position<E>> positions() {
	PositionList<Position<E>> toReturn = new NodePositionList<Position<E>>();
	Position<E> current = first();
	if(!isEmpty()){
	  for (int i = 0; i < size()-1; i++) {
		  toReturn.addLast(current);
		  current=next(current);
	  }
	toReturn.addLast(last());
	}
	return toReturn;
}
}
package LinkedBinaryTree;

public interface Position<E> {

	public E element();
}
package LinkedBinaryTree;

public interface PositionList<E> extends Iterable<E>{
	public int size();
	public boolean isEmpty();
	public Position<E> first();
	public Position<E> last();
	public Position<E> next(Position<E> p)
    throws InvalidPositionException,
           BoundaryViolationException;
	public Position<E> prev(Position<E> p)
    throws InvalidPositionException,
           BoundaryViolationException;
	public void addFirst(E e);
	public void addLast(E e);
	public void addAfter(Position<E> p, E e)
            throws InvalidPositionException;
	public void addBefore(Position<E> p,
            E e)
            throws InvalidPositionException;
	public E remove(Position<E> p)
    throws InvalidPositionException;
	public E set(Position<E> p,
		      E e)
		      throws InvalidPositionException;
	public Iterable<Position<E>> positions();
	public Iterator<E> iterator();
	
}
package LinkedBinaryTree;




/**
 * An interface for a tree where nodes can have an arbitrary number of children.
 */
public interface Tree<E> {
  /** Returns the number of nodes in the tree. */
  public int size();
  /** Returns whether the tree is empty. */
  public boolean isEmpty();
  /** Returns an iterator of the elements stored in the tree. */
  public Iterator<E> iterator();
  /** Returns an iterable collection of the the nodes. */
  public Iterable<Position<E>> positions();
  /** Replaces the element stored at a given node. */
  public E replace(Position<E> v, E e)
    throws InvalidPositionException;
  /** Returns the root of the tree. */
  public Position<E> root() throws EmptyTreeException;
  /** Returns the parent of a given node. */
  public Position<E> parent(Position<E> v)
    throws InvalidPositionException, BoundaryViolationException;
  /** Returns an iterable collection of the children of a given node. */
  public Iterable<Position<E>> children(Position<E> v) 
    throws InvalidPositionException;
  /** Returns whether a given node is internal. */
  public boolean isInternal(Position<E> v) 
    throws InvalidPositionException;
  /** Returns whether a given node is external. */
  public boolean isExternal(Position<E> v) 
    throws InvalidPositionException;
  /** Returns whether a given node is the root of the tree. */
  public boolean isRoot(Position<E> v)
    throws InvalidPositionException;
}
  • 2 Contributors
  • 3 Replies
  • 479 Views
  • 16 Hours Discussion Span
  • Latest Post Latest Post by hiddepolen

Recommended Answers

All 3 Replies

Member Avatar for hiddepolen

I think it would help if you let the LinkedBinaryTree class implement Iterable<E>.
Then, you should be able to iterate in a for loop.

Member Avatar for cgen

I found another way to do it. I deleted Iterable.java and Iterator.java and then imported java.util.Iterator

Member Avatar for hiddepolen

Great, good luck with the project!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.