Trees

Trees using JAVA generics

Page 1 of 1

7 Replies - 2429 Views - Last Post: 25 April 2008 - 09:10 AM Rate Topic: -----

#1 AdnanShafique   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 24-April 08

Trees

Post icon  Posted 24 April 2008 - 07:05 PM

Hi Everyone,
Can anyone add a main method to this LinkedBinaryTree method and show me how to add nodes.
I would really appreciate if anyone can add upto 6 integer items.
Thanks.



	package net.datastructures;
	import java.util.Iterator;

	//begin#fragment LinkedBinaryTree
	/**
	  * An implementation of the BinaryTree interface by means of a linked structure.
	//end#fragment LinkedBinaryTree
	  * This class serves as a superclass for the BinarySearchTree
	  * implementation.  This design decision was made to emphasize the
	  * conceptual relationship that a BinarySearchTree is a specialized
	  * LinkedBinaryTree.  An unwanted side-effect of this is that the
	  * {@link #size() size} method returns the number of total nodes
	  * whereas the {@link BinarySearchTree#size() size} method in the
	  * {@link BinarySearchTree BinarySearchTree} class returns the number
	  * of internal nodes only.  For this reason, the the {@link #size
	  * size} variable instead of the {@link #size() size} method is used
	  * within this class.
	  *
	  * @author Luca Vismara, Roberto Tamassia, Michael Goodrich, Eric
	  * Zamore
	  * @see BinaryTree
	//begin#fragment LinkedBinaryTree
	  */
	public class LinkedBinaryTree<E> implements BinaryTree<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; 
	  } 
	//end#fragment LinkedBinaryTree
	  /** Returns whether the tree is empty. */
	  public boolean isEmpty() {
		return (size == 0); 
	  } 
	//begin#fragment LinkedBinaryTree
	  /** Returns whether a node is internal. */
	  public boolean isInternal(Position<E> v) throws InvalidPositionException {
		checkPosition(v);		// auxiliary method
		return (hasLeft(v) || hasRight(v));
	  }
	//end#fragment LinkedBinaryTree
	  /** Returns whether a node is external. */
	  public boolean isExternal(Position<E> v) throws InvalidPositionException {
		return !isInternal(v);
	  }
	//begin#fragment LinkedBinaryTree
	  /** 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);
	  }
	//end#fragment LinkedBinaryTree
	  /** Returns whether a node has a right child. */
	  public boolean hasRight(Position<E> v) throws InvalidPositionException { 
		BTPosition<E> vv = checkPosition(v);
		return (vv.getRight() != null);
	  }
	//begin#fragment LinkedBinaryTree
	  /** 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;
	  }
	//end#fragment LinkedBinaryTree
	  /** Returns the right child of a node. */
	  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;
	   }
	//begin#fragment LinkedBinaryTree2
	  /** 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;
	  }
	//end#fragment LinkedBinaryTree2
	//begin#fragment LinkedBinaryTree3
	  // 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;
	  }
	//end#fragment LinkedBinaryTree3
	  /** Inserts a right child at a given node. */
	  public Position<E>  insertRight(Position<E> v, E e)
		throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		Position<E> rightPos = vv.getRight();
		if (rightPos != null)
		  throw new InvalidPositionException("Node already has a right child");
		BTPosition<E> w = createNode(e, vv, null, null);
		vv.setRight(w);
		size++;
		return w;
	  }
	//begin#fragment LinkedBinaryTree4
	  /** 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();
	  }

	//end#fragment LinkedBinaryTree4
	//begin#fragment LinkedBinaryTree5
	  /** 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
		}
	  }
	//end#fragment LinkedBinaryTree5
	  /** Swap the elements at two nodes */
	  public void swapElements(Position<E> v, Position<E> w)
		throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		BTPosition<E> ww = checkPosition(w);
		E temp = w.element();
		ww.setElement(v.element());
		vv.setElement(temp);	
	  }
	  /** Expand an external node into an internal node with two external
		  node children */
	  public void expandExternal(Position<E> v, E l, E r) 
		throws InvalidPositionException {
		if (!isExternal(v)) 
		  throw new InvalidPositionException("Node is not external");
		insertLeft(v, l);
		insertRight(v, r);
	  }
	  /** Remove an external node v and replace its parent with v's
		  sibling */
	  public void removeAboveExternal(Position<E> v) 
		throws InvalidPositionException {
		if (!isExternal(v)) 
		  throw new InvalidPositionException("Node is not external");
		if (isRoot(v))
		  remove(v);
		else {
		  Position<E> u = parent(v);
		  remove(v);
		  remove(u);
		}
	  }
	  // Auxiliary methods
	//begin#fragment LinkedBinaryTree5
	  /** 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
	  }
	//end#fragment LinkedBinaryTree5
	  /** Creates a list storing the the nodes in the subtree of a node,
		* ordered according to the inorder traversal of the subtree. */
	  protected void inorderPositions(Position<E> v, PositionList<Position<E>> pos) 
		throws InvalidPositionException {
		if (hasLeft(v))
		  inorderPositions(left(v), pos);  // recurse on left child
		pos.addLast(v);
		if (hasRight(v))
		  inorderPositions(right(v), pos); // recurse on right child
	  }
	  public void removeSubtree(Position<E>v)throws InvalidPositionException{
		  Position<E> vv = checkPosition(v);
		  if( vv == null){System.out.println("Node does not exist.");}
		  
		  
	  }
	 // public void printroot(){
		  //System.out.println("Root: "+root());
	  //}
	 
	}






Is This A Good Question/Topic? 0
  • +

Replies To: Trees

#2 AdnanShafique   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 24-April 08

Re: Trees

Posted 24 April 2008 - 07:20 PM

The problem I have is that I cannot figure out how to enter items after Im done with entering the root and its children, for example I use

tree.root and then insert left or right child

but after that how do I access or call the children to add nodes to them?

Can anyone help?
Was This Post Helpful? 0
  • +
  • -

#3 pbl   User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8379
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: Trees

Posted 24 April 2008 - 07:41 PM

View PostAdnanShafique, on 24 Apr, 2008 - 07:20 PM, said:

The problem I have is that I cannot figure out how to enter items after Im done with entering the root and its children, for example I use

tree.root and then insert left or right child

but after that how do I access or call the children to add nodes to them?

Can anyone help?


I guess you cannot enter even the root
There are dozeins of compilation errors

A BinaryTree contains node objects
Node must be defined as having a left and a right node (initialized to null)
do not see any reference to that in your "pseudo code"

You throw undefined InvalidPositionException everywhere.. you are kind of paranoiac... why would you have exceptions ?

This post has been edited by pbl: 24 April 2008 - 07:43 PM

Was This Post Helpful? 0
  • +
  • -

#4 AdnanShafique   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 24-April 08

Re: Trees

Posted 24 April 2008 - 08:50 PM

View Postpbl, on 24 Apr, 2008 - 07:41 PM, said:

View PostAdnanShafique, on 24 Apr, 2008 - 07:20 PM, said:

The problem I have is that I cannot figure out how to enter items after Im done with entering the root and its children, for example I use

tree.root and then insert left or right child

but after that how do I access or call the children to add nodes to them?

Can anyone help?


I guess you cannot enter even the root
There are dozeins of compilation errors

A BinaryTree contains node objects
Node must be defined as having a left and a right node (initialized to null)
do not see any reference to that in your "pseudo code"

You throw undefined InvalidPositionException everywhere.. you are kind of paranoiac... why would you have exceptions ?


Well actually that is the code given to me to work with form my instructor.
This is not the whole code I have a bunch of interfaces and methods that make it work.
I just don't know how to call the left and right node to insert their children.
like if the children of the root cal be called by tree.root(addLeft) and tree.root(addRight)
after Im done with this how do I add the grand chlidren of the root???
Was This Post Helpful? 0
  • +
  • -

#5 AdnanShafique   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 24-April 08

Re: Trees

Posted 24 April 2008 - 09:00 PM

Please see the attachment so that you can understand what Im trying to ask.
Thanks

Attached File(s)


Was This Post Helpful? 0
  • +
  • -

#6 pbl   User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8379
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: Trees

Posted 24 April 2008 - 09:39 PM

View PostAdnanShafique, on 24 Apr, 2008 - 08:50 PM, said:

Well actually that is the code given to me to work with form my instructor.
This is not the whole code I have a bunch of interfaces and methods that make it work.
I just don't know how to call the left and right node to insert their children.
like if the children of the root cal be called by tree.root(addLeft) and tree.root(addRight)
after Im done with this how do I add the grand chlidren of the root???


Search for Binary Tree is this forum there are a lot of examples

And if you are only posting the code from your instructor I'll remember you one of this site policy

Quote

Dream.In.Code has a policy by which we prefer to see a good faith effort on your part before providing source code for homework assignments. Please post the code you have written in an effort to resolve the problem, and our members would be happy to provide some guidance. Be sure to include a description of any errors you are encountering as well.


We won't do your assignment.
Was This Post Helpful? 0
  • +
  • -

#7 AdnanShafique   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 24-April 08

Re: Trees

Posted 24 April 2008 - 10:28 PM

View Postpbl, on 24 Apr, 2008 - 09:39 PM, said:

View PostAdnanShafique, on 24 Apr, 2008 - 08:50 PM, said:

Well actually that is the code given to me to work with form my instructor.
This is not the whole code I have a bunch of interfaces and methods that make it work.
I just don't know how to call the left and right node to insert their children.
like if the children of the root cal be called by tree.root(addLeft) and tree.root(addRight)
after Im done with this how do I add the grand chlidren of the root???


Search for Binary Tree is this forum there are a lot of examples

And if you are only posting the code from your instructor I'll remember you one of this site policy

Quote

Dream.In.Code has a policy by which we prefer to see a good faith effort on your part before providing source code for homework assignments. Please post the code you have written in an effort to resolve the problem, and our members would be happy to provide some guidance. Be sure to include a description of any errors you are encountering as well.


We won't do your assignment.

Well I know the policy :) My assignment is to write a remove subtree method. So I'm just asking for some help in making the code work so that I'm clear about how to work with generics and trees and I can see how they actually work. And the question I'm asking can't be the actual assignment I'm sure you figured that out.

Thanks.
Was This Post Helpful? 0
  • +
  • -

#8 AdnanShafique   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 24-April 08

Re: Trees

Posted 25 April 2008 - 09:10 AM

View PostAdnanShafique, on 24 Apr, 2008 - 10:28 PM, said:

View Postpbl, on 24 Apr, 2008 - 09:39 PM, said:

View PostAdnanShafique, on 24 Apr, 2008 - 08:50 PM, said:

Well actually that is the code given to me to work with form my instructor.
This is not the whole code I have a bunch of interfaces and methods that make it work.
I just don't know how to call the left and right node to insert their children.
like if the children of the root cal be called by tree.root(addLeft) and tree.root(addRight)
after Im done with this how do I add the grand chlidren of the root???


Search for Binary Tree is this forum there are a lot of examples

And if you are only posting the code from your instructor I'll remember you one of this site policy

Quote

Dream.In.Code has a policy by which we prefer to see a good faith effort on your part before providing source code for homework assignments. Please post the code you have written in an effort to resolve the problem, and our members would be happy to provide some guidance. Be sure to include a description of any errors you are encountering as well.


We won't do your assignment.

Well I know the policy :) My assignment is to write a remove subtree method. So I'm just asking for some help in making the code work so that I'm clear about how to work with generics and trees and I can see how they actually work. And the question I'm asking can't be the actual assignment I'm sure you figured that out.

Thanks.

Help Anyone??? please see the attachment.

Attached File(s)


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1