LinkedBinaryTree Dictionary

  • (2 Pages)
  • +
  • 1
  • 2

18 Replies - 7422 Views - Last Post: 25 April 2008 - 07:02 PM Rate Topic: -----

#1 Samer   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-July 07

LinkedBinaryTree Dictionary

Posted 25 December 2007 - 04:39 PM

First of all, Merry Christmas and Happy New Year for everyone.
Guys I was trying to implement a Dictionary using LinkedBinaryTrees.
I'm desperate in implementing some of the methods of the dictionary, as well as a Hashcode error in the BinaryTree tester..

import InvalidPositionException.InvalidPositionException;
public class DNode {
	private DNode prev, next;
	private Object element;
	
	public DNode(DNode newPrev, DNode newNext, Object elem) {
		prev = newPrev;
		next = newNext;
		element = elem;
	}
	
	public Object element() throws InvalidPositionException {
		if((prev == null) && (next == null))
			throw new InvalidPositionException("Position is not in a list!");
		return element;
	}
	public DNode getNext() {
		return next;
	}
	
	public DNode getPrev() {
		return prev;
	}
	
	public void setNext(DNode newNext) {
		next = newNext;
	}
	
	public void setPrev(DNode newPrev) {
		prev = newPrev;
	}
	
	public void setELement(Object newElement) {
		element = newElement;
	}
}



public class BTNode {
	private Object element;
	private BTNode left, right, parent;
	
	public BTNode(Object element, BTNode parent, BTNode left, BTNode right) {
		setElement(element);
		setParent(parent);
		setLeft(left);
		setRight(right);
	}
	
	public Object element() {
		return element;
	}
	
	public void setElement(Object o) {
		element = o;
	}
	
	public BTNode getLeft() {
		return left;
	}
	
	public void setLeft(BTNode v) {
		left = v;
	}

	public BTNode getRight() {
		return right;
	}
	
	public void setRight(BTNode v) {
		right = v;
	}
	
	public BTNode getParent() {
		return parent;
	}
	
	public void setParent(BTNode v) {
		parent = v;
	}
}




import BoundaryViolationException.BoundaryViolationException;
import EmptyListException.EmptyListException;
import InvalidPositionException.InvalidPositionException;
import java.util.NoSuchElementException;
public class ElementIterator implements Iterator {
	protected NodeList list;
	protected DNode cur;
	
	public ElementIterator() {
	}
	
	public ElementIterator(NodeList L) {
		list = L;
		if(list.isEmpty())
			cur = null;
		else
			cur = list.first();
	}
	
	public boolean hasNext() throws NoSuchElementException, EmptyListException, InvalidPositionException, BoundaryViolationException {
		return (cur != null);
	}
	
	public Object next() throws NoSuchElementException {
		if(!hasNext()) throw new NoSuchElementException("No next element.");
		Object toReturn = cur;
		if(cur.element() == list.last().element())
			cur = null;
		else
			cur = list.next(cur);
		return toReturn;
	}
}




import BoundaryViolationException.BoundaryViolationException;
import EmptyListException.EmptyListException;
import InvalidPositionException.InvalidPositionException;
import java.util.NoSuchElementException;
public interface Iterator {
	public boolean hasNext();
	public Object next() throws NoSuchElementException, EmptyListException, InvalidPositionException, BoundaryViolationException;
	
}




import BoundaryViolationException.BoundaryViolationException;
import EmptyTreeException.EmptyTreeException;
import InvalidPositionException.InvalidPositionException;
import NonEmptyTreeException.NonEmptyTreeException;
public class LinkedBinaryTree
{
	protected BTNode root;
	protected int size;
	public LinkedBinaryTree() {
		root = null;
		size = 0;
	}
	public int size() {
		return size;
	}
	public boolean isEmpty() {
		return (size==0);
	}
	public boolean isInternal(BTNode v) throws InvalidPositionException {
		checkPosition(v);
		return (hasLeft(v) || hasRight(v));
	}
	public boolean isExternal(BTNode v) throws InvalidPositionException {
		return !isInternal(v);
	}
	public boolean isRoot(BTNode v) throws InvalidPositionException {
		checkPosition(v);
		return (v == root());
	}
	
	public boolean hasLeft(BTNode v)throws InvalidPositionException {
		BTNode vv = checkPosition(v);
		return (vv.getLeft() != null);
	}
	public boolean hasRight(BTNode v)throws InvalidPositionException {
		BTNode vv = checkPosition(v);
		return (vv.getRight() != null);
	}
	public BTNode root() throws EmptyTreeException {
		if (root == null)
			throw new EmptyTreeException("The tree has no root");
		return root;
	}
	public BTNode left(BTNode v)throws InvalidPositionException, BoundaryViolationException
	{
		if (! hasLeft(v))
			throw new BoundaryViolationException("No left child");
		return ((BTNode)v).getLeft();
	}
	public BTNode right(BTNode v)throws InvalidPositionException, BoundaryViolationException
	{
		if (! hasRight(v))
			throw new BoundaryViolationException("no right child");
		return ((BTNode)v).getRight();
	}
	public BTNode parent(BTNode v)throws InvalidPositionException, BoundaryViolationException
	{
		if (isRoot(v))
			throw new BoundaryViolationException("Root has no parent");
		return ((BTNode)v).getParent();
	}
	public Iterator children(BTNode v) throws InvalidPositionException
	{
		NodeList children = new NodeList();
		if (hasLeft(v))
			children.insertLast(left(v));
		if (hasRight(v))
			children.insertLast(right(v));
		return children.elements();
	}   
	public Iterator positions()
	{
		NodeList positions = new NodeList();
		if (size != 0)
			inorderPositions(root(), positions);
		return positions.elements();
	}
	public Iterator elements()
	{
		Iterator positer = positions();
		NodeList elements = new NodeList();
		for (int i = 0; i < size; i++)
		{
			elements.insertLast(((BTNode) positer.next()).element());
			
		}
		return elements.elements();
	}
	public Object replace(BTNode v, Object o) throws InvalidPositionException
	{
		BTNode vv = checkPosition(v);
		Object temp = v.element();
		vv.setElement(o);
		return temp;
		
		
	}
	public BTNode sibling(BTNode v)throws InvalidPositionException, BoundaryViolationException
	{
		try
		{
			BTNode p = parent(v);
			BTNode lc = left(p);
			if (v == lc)
				return right(p);
			else
				return lc;
		}
		catch(BoundaryViolationException e)
		{
			throw new BoundaryViolationException("Node has  no sibling");
		}
	}
	
	public BTNode insertLeft (BTNode v, Object e)throws InvalidPositionException
	{
		if (hasLeft(v))
			throw new InvalidPositionException("Node already has a left child");
		BTNode vv = (BTNode)v;
		BTNode ww = createNode(e, vv, null, null);
		vv.setLeft((ww));
		size++;
		return ww;
	}
	public BTNode insertRight(BTNode v, Object e) throws InvalidPositionException {
		if(hasRight(v))
			throw new InvalidPositionException("Node already has a right child.");
		BTNode vv = (BTNode) v;
		BTNode w = createNode(e, vv, null, null);
		vv.setRight(w);
		size++;
		return w;
	}
	
	public Object remove(BTNode v) throws InvalidPositionException {
		if(hasLeft(v) && hasRight(v))
			throw new InvalidPositionException("Cannot remove node with 2 children.");
		BTNode vv = (BTNode) v;
		BTNode ww;
		if(hasLeft(v))
			ww = (BTNode) left(v);
		else if (hasRight(v))
			ww = (BTNode) right(v);
		else
			ww = null;
		if(v == root()) {
			if(ww != null)
				ww.setParent(null);
			root = ww;
		}
		else {
			BTNode uu = (BTNode) parent(v);
			if(hasLeft(uu) && v == left(uu))
				uu.setLeft(ww);
			else
				uu.setRight(ww);
			if(ww != null)
				ww.setParent(uu);
		}
		size--;
		return v.element();
	}
	public BTNode addRoot(Object e) throws NonEmptyTreeException {
		if(!isEmpty())
			throw new NonEmptyTreeException("Tree already has a root.");
		size = 1;
		root = createNode(e, null, null, null);
		return root;
		
	}
	
	public void attach(BTNode v, LinkedBinaryTree T1, LinkedBinaryTree T2) throws InvalidPositionException {
		if(isInternal(v))
			throw new InvalidPositionException("Cannot attach from internal node.");
		BTNode vv = (BTNode) v;
		if(!T1.isEmpty()) {
			vv.setLeft((BTNode) T1.root());
			((BTNode) T1.root()).setParent(vv);
			
		}
		if(!T2.isEmpty()) {
			vv.setRight((BTNode) T2.root());
			((BTNode) T2.root()).setParent(vv);
		}
		
		size = T1.size() + T2.size() + 1;
	}
	
	protected BTNode checkPosition(BTNode v) throws InvalidPositionException {
		if(v == null || !(v instanceof BTNode))
			throw new InvalidPositionException("The position is invalid.");
		return (BTNode) v;
	}
	
	protected BTNode createNode(Object element, BTNode parent, BTNode left, BTNode right) {
		return new BTNode(element, parent, left, right);
	}
	
	protected void inorderPositions(BTNode v, NodeList pos) throws InvalidPositionException {
		if(hasLeft(v))
			inorderPositions(left(v), pos);
		pos.insertLast(v);
		if(hasRight(v))
			inorderPositions(right(v), pos);
	}
	
}




import BoundaryViolationException.BoundaryViolationException;
import EmptyListException.EmptyListException;
import InvalidPositionException.InvalidPositionException;
public class NodeList {
	protected int numElts;
	protected DNode header, trailer;
	
	public NodeList() {
		numElts = 0;
		header = new DNode(null, null, null);
		trailer = new DNode(header, null, null);
		header.setNext(trailer);
	}
	
	protected DNode checkPosition(DNode 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 temp = (DNode) 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.");
		}
	}
	
	public int size() {
		return numElts;
	}
	
	public boolean isEmpty() {
		return (numElts == 0);
	}
	
	public DNode first() throws EmptyListException {
		if(isEmpty())
			throw new EmptyListException("List is empty");
		return header.getNext();
	}
	
	public DNode last() throws EmptyListException {
		if(isEmpty())
			throw new EmptyListException("List is empty");
		return trailer.getPrev(); 
	}
	
	public DNode prev(DNode p) throws InvalidPositionException, BoundaryViolationException {
		DNode v = checkPosition(p);
		DNode prev = v.getPrev();
		if(prev == header)
			throw new BoundaryViolationException("Cannot advance past the beginning of the list.");
		return prev;
	}
	
	public DNode next(DNode p) throws InvalidPositionException, BoundaryViolationException {
		DNode v = checkPosition(p);
		DNode next = v.getNext();
		if(next == trailer)
			throw new BoundaryViolationException("Cannot advance post the end of the list.");
		return next;
	}
	
	public DNode insertBefore(DNode p, Object element) throws InvalidPositionException {
		DNode v = checkPosition(p);
		numElts++;
		DNode newNode = new DNode(v.getPrev(), v, element);
		v.getPrev().setNext(newNode);
		v.setPrev(newNode);
		return newNode;
	}
	
	public DNode insertAfter(DNode p, Object element) throws InvalidPositionException {
		DNode v = checkPosition(p);
		numElts++;
		DNode newNode = new DNode(v, v.getNext(), element);
		v.getNext().setPrev(newNode);
		v.setNext(newNode);
		return newNode;
	}
	public DNode insertFirst(Object element) {
		numElts++;
		DNode newNode = new DNode(header, header.getNext(), element);
		header.getNext().setPrev(newNode);
		header.setNext(newNode);
		return newNode;
	}
	
	public DNode insertLast(Object element) {
		numElts++;
		DNode newNode = new DNode(trailer.getPrev(), trailer, element);
		trailer.getPrev().setNext(newNode);
		trailer.setPrev(newNode);
		return newNode;
		
	}
	public Object remove(DNode p) throws InvalidPositionException {
		DNode v = checkPosition(p);
		numElts--;
		DNode vPrev = v.getPrev();
		DNode vNext = v.getNext();
		vPrev.setNext(vNext);
		vNext.setPrev(vPrev);
		Object vElem = v.element();
		
		v.setNext(null);
		v.setPrev(null);
		return vElem;
	}
	
	public Object replace(DNode p, Object element) throws InvalidPositionException {
		DNode v = checkPosition(p);
		Object oldElt = v.element();
		v.setELement(element);
		return oldElt;
	}

	public Iterator elements() {
		return new ElementIterator(this);
	}
}





import java.util.NoSuchElementException;
public class PositionIterator implements Iterator {
	protected NodeList list;
	protected DNode cur;
	
	public PositionIterator() {
	}
	
	public PositionIterator(NodeList L) {
		list = L;
		if(list.isEmpty())
			cur = null;
		else
			cur = list.first();
	}
	
	public boolean hasNext() {
		return (cur != null);
	}
	
	public Object next() throws NoSuchElementException {
		if(!hasNext()) throw new NoSuchElementException("No next position.");
		DNode toReturn = cur;
		if(cur == list.last())
			cur = null;
		else
			cur = list.next(cur);
		return toReturn;
	}
}





package BoundaryViolationException;
public class BoundaryViolationException extends java.lang.RuntimeException {
	public BoundaryViolationException() {
		super();
	}

	public BoundaryViolationException(String s) {
		super(s);
	}
}




package EmptyListException;
public class EmptyListException extends java.lang.RuntimeException {
	public EmptyListException() {
		super();
	}

	public EmptyListException(String s) {
		super(s);
	}
}



package EmptyTreeException;
public class EmptyTreeException extends java.lang.RuntimeException {
	public EmptyTreeException() {
		super();
	}

	public EmptyTreeException(String s) {
		super(s);
	}
}





package InvalidPositionException;
public class InvalidPositionException extends java.lang.RuntimeException {
	public InvalidPositionException() {
		super();
	}

	public InvalidPositionException(String s) {
		super(s);
	}
}




package NonEmptyTreeException;
public class NonEmptyTreeException extends java.lang.RuntimeException {
	public NonEmptyTreeException() {
		super();
	}

	public NonEmptyTreeException(String s) {
		super(s);
	}
}






public class LBTTester {
	public static void main(String[] args) {
		LinkedBinaryTree T1 = new LinkedBinaryTree();
		LinkedBinaryTree T2 = new LinkedBinaryTree();
		BTNode root1 = T1.createNode("Root of T1", null, null, null);
		T1.addRoot(root1);
		T1.insertLeft(root1, "Left of T1");
		T1.insertRight(root1, "Right of T1");
		BTNode root2 = T2.createNode("Root of T2", null, null, null);
		T2.addRoot(root2);
		T2.insertLeft(root2, "Left of T2");
		T2.insertRight(root2, "Right of T2");
		
		System.out.println("The root of the T1 is: " + root1.element());
		System.out.println("The left of T1 is: " + T1.left(root1).element());
		System.out.println("The right of T1 is: " + T1.right(root1).element());
		System.out.println("The size of T1 is: " + T1.size());
		
		System.out.println("The root of the T2 is: " + root2.element());
		System.out.println("The left of T2 is: " + T2.left(root2).element());
		System.out.println("The right of T2 is: " + T2.right(root2).element());
		System.out.println("The size of T2 is: " + T2.size());
		
		LinkedBinaryTree T = new LinkedBinaryTree();
		BTNode root = T.createNode("This is the root of T", null, null, null);
		T.addRoot(root);
		T.attach(root, T1, T2);
		
		System.out.println("We will check now if root of T1 is internal: " + T.isInternal(root1));
		System.out.println("We will check now if root of T2 is external: " + T.isExternal(root2));
		System.out.println("We will check now if root1 is root: " + T.isRoot(root1));
		System.out.println("We will check now if root is root: " + T.isRoot(root));
		System.out.println("We will check now if root has left and right: " + T.hasLeft(root) + " and " + T.hasRight(root));
		System.out.println("The root of T is: " + T.root().element());
		System.out.println("We will check now if T is empty: " + T.isEmpty());
		System.out.println("The parent of the most left node is: " + T.parent(T.left(root1)));
		System.out.println("The children of the root are: " + T.children(root));
		T.positions();

		T.replace(T.left(root1), "This is the new left of root 1");
		System.out.println("The left of root1 is: " + T.left(root1));
		System.out.println("The sibling of root 1 is: " + T.sibling(root1).element());
		System.out.println("We will remove the right of root2");
		T.remove(T.right(root2));
		System.out.println("The right of T2 is: " + T2.hasRight(root2));
		NodeList x = new NodeList();
		T.inorderPositions(root1, x);
		
	}	
}


This is for the LinkedBinaryTree
The output of the LBTTester is:
The root of the T1 is: Root of T1
The left of T1 is: Left of T1
The right of T1 is: Right of T1
The size of T1 is: 3
The root of the T2 is: Root of T2
The left of T2 is: Left of T2
The right of T2 is: Right of T2
The size of T2 is: 3
We will check now if root of T1 is internal: true
We will check now if root of T2 is external: false
We will check now if root1 is root: false
We will check now if root is root: false
We will check now if root has left and right: true and true
The root of T is: [email protected]
We will check now if T is empty: false
The parent of the most left node is: [email protected]
The children of the root are: [email protected]
The left of root1 is: [email protected]
Exception in thread "main" InvalidPositionException.InvalidPositionException: The position is invalid.
		at LinkedBinaryTree.checkPosition(LinkedBinaryTree.java:191)
		at LinkedBinaryTree.hasLeft(LinkedBinaryTree.java:32)
		at LinkedBinaryTree.left(LinkedBinaryTree.java:46)
		at LinkedBinaryTree.sibling(LinkedBinaryTree.java:103)
		at LBTTester.main(LBTTester.java:42)
Java Result: 1



As for the dictionary, we have a comparator class, it takes two Keys, A and B, if A = B, it return 0, if A > B it returns 1, else it returns -1
package EmptyDictionaryException;
public class EmptyDictionaryException extends java.lang.RuntimeException {
	public EmptyDictionaryException() {
		super();
	}

	public EmptyDictionaryException(String s) {
		super(s);
	}
}





package InvalidKeyException;
public class InvalidKeyException extends java.lang.RuntimeException {
	public InvalidKeyException() {
		super();
	}

	public InvalidKeyException(String s) {
		super(s);
	}
}



import EmptyDictionaryException.EmptyDictionaryException;
import InvalidKeyException.InvalidKeyException;

public class Dictionary {
	protected Comparator comp;
	protected LinkedBinaryTree T;
	
	public Dictionary(Comparator c) {
		T = new LinkedBinaryTree();
		comp = c;
	}
	
	public boolean find() {
		/* find a key in the binary tree T.
		 * if the key exists, return true;
		 * else return false.*/
	}
	
	public NodeList findall() {
		/* Return a list that contains all the objects in T in
		 * a nondecreasing order
		 * The order of the objects is determind by comparator comp.*/
	}
	
	public void insertKey(Object key) throws InvalidKeyException {
		checkKey(key); // may throw and InvalidKeyException
		//it inserts the key into T
	}
	
	public void removeKey(Object key) throws EmptyDictionaryException {
		if(T.isEmpty())
			throw new EmptyDictionaryException("Dictionary is empty");
		/*it removes all the occurences of key in T,
		 * knowing that T might contain multiple instances of key.*/
	}
	
	protected void checkKey(Object Key) throws InvalidKeyException {
		try {
			comp.compare(key, key);
		}
		catch(Exception e) {
			throw new InvalidKeyException("Invalid key");
		}
	}
}




Is This A Good Question/Topic? 0
  • +

Replies To: LinkedBinaryTree Dictionary

#2 Samer   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-July 07

Re: LinkedBinaryTree Dictionary

Posted 26 December 2007 - 12:06 PM

So no one is willing to offer some help?
Was This Post Helpful? 0
  • +
  • -

#3 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7295
  • View blog
  • Posts: 15,185
  • Joined: 16-October 07

Re: LinkedBinaryTree Dictionary

Posted 26 December 2007 - 01:07 PM

View PostSamer, on 26 Dec, 2007 - 02:06 PM, said:

So no one is willing to offer some help?


You have to admit, it's a lot of code to look at. Just getting it into a format that could compile would take at least twenty minutes of cut and paste.

I believe I've never, ever, seen this before; too many exceptions! The code in nearly unreadable for them.

Some of the code is strangely redundant. e.g.
protected BTNode checkPosition(BTNode v) throws InvalidPositionException {
// Why !(v instanceof BTNode)?!?  We wouldn't have gotten here is it wasn't the case.
   if(v == null || !(v instanceof BTNode))
	  throw new InvalidPositionException("The position is invalid.");
// why cast the thing  BTNode?  It's that type already.
// For that matter, why are we returning it on a check?
   return (BTNode) v;
}


And stuff like BTNode vv = (BTNode) v;? This odd casting stuff is repeated over and over. There's a class paranoia here that doesn't make sense in context. Perhaps this code was adapted from some thing more generic? I'd trying pruning out all the methods you don't use, and at first glance there seem to be a lot, and see if you can get a handle on what's going on.

Hope this helps.
Was This Post Helpful? 0
  • +
  • -

#4 1lacca   User is offline

  • code.rascal
  • member icon

Reputation: 44
  • View blog
  • Posts: 3,822
  • Joined: 11-August 05

Re: LinkedBinaryTree Dictionary

Posted 26 December 2007 - 04:02 PM

And what exactly your question is?
I see a bunch of code, and that you want to implement something. Could you specify the exact nature of your problem? Does it compile? Do you have a runtime exception? A compiler error? Or simply can't implement a feature?
Was This Post Helpful? 0
  • +
  • -

#5 Samer   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-July 07

Re: LinkedBinaryTree Dictionary

Posted 27 December 2007 - 02:47 AM

View Post1lacca, on 26 Dec, 2007 - 04:02 PM, said:

And what exactly your question is?
I see a bunch of code, and that you want to implement something. Could you specify the exact nature of your problem? Does it compile? Do you have a runtime exception? A compiler error? Or simply can't implement a feature?

It compiles perfectly, but output of the LBTTester shows some hashcode and them a runtime exception, that's the first thing i want to fix.. the other thing is implementing few methods in the dictionary class..
Was This Post Helpful? 0
  • +
  • -

#6 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7295
  • View blog
  • Posts: 15,185
  • Joined: 16-October 07

Re: LinkedBinaryTree Dictionary

Posted 27 December 2007 - 05:28 AM

The point of a binary tree structure is to hold values. Your binary tree is confused because you're manually messing with it's nodes. It wants you to leave it's nodes alone. Nodes are a private thing.

Seriously, any storage structure should implement basic things like addValue, removeValue, findValue, listContents, that sort of thing. How it stores that information, the structure of it's nodes, should not be the concern of the user of the structure.

These lines make no sense in context:
LinkedBinaryTree T1 = new LinkedBinaryTree();
BTNode root1 = T1.createNode("Root of T1", null, null, null);
T1.addRoot(root1);
T1.insertLeft(root1, "Left of T1");
T1.insertRight(root1, "Right of T1");



Who am I, that I should have access to createNode, or determine what value is the root, or if it's left or right? I shouldn't care. I should just be able to do something like:
LinkedBinaryTree T1 = new LinkedBinaryTree();
T1.add("Root of T1");
T1.add("Left of T1");
T1.add("Right of T1");



And be done.

This very manual approach to a binary tree has led to the expected errors.

For example:
public BTNode addRoot(Object e) throws NonEmptyTreeException {
   if(!isEmpty()) { throw new NonEmptyTreeException("Tree already has a root."); }
   size = 1;
   root = createNode(e, null, null, null);
   return root;
}



Hold on, the object we gave this method was already a node:
BTNode root1 = T1.createNode("Root of T1", null, null, null);
T1.addRoot(root1);



We now have a node of a node! There are a few places where this happens. This is a big cause of your problems.

There are tons of binary tree implementations out there. You might want to look at them. Here's a very simple one I wrote to give an idea.

public class BinTree {
	   private class Node implements Comparable {
			   public Comparable value = null;
			   public Node left = null;
			   public Node right = null;
			   public Node(Comparable value) { this.value = value; }
			   public int compareTo(Object obj) {
					   if (obj==null) { return 0; }
					   if (obj instanceof Node) {
							   return this.value.compareTo(((Node)obj).value);
					   }
					   return this.value.compareTo(obj.toString());
			   }
			   public String toString() {
					   return this.value.toString();
			   }
	   }

	   private Node rootNode;
	   public BinTree() {
			   this.rootNode = null;
	   }

	   public void addValue(Comparable value) {
			   addNode(new Node(value));
	   }

	   private void addNode(Node newNode) {
			   if(newNode==null) { return; }
			   if (rootNode == null) {
					   rootNode = newNode;
			   } else {
					   Node currentNode = rootNode;
					   while (true) {
							   if (currentNode.compareTo(newNode) > 0) {
									   if (currentNode.left == null) {
											   currentNode.left = newNode;
											   return;
									   }
									   currentNode = currentNode.left;
							   } else {
									   if (currentNode.right == null) {
											   currentNode.right = newNode;
											   return;
									   }
									   currentNode = currentNode.right;
							   }
					   }
			   }
	   }

	   private void removeNode(Node removeNode, Node parentNode) {
			   // needs to be written, you don't get all the code
	   }

	   public boolean removeValue(Comparable value) {
			   // needs to be written, you don't get all the code
			   return false;
	   }

	   private void printInOrder(Node node) {
			   if (node.left != null) { printInOrder(node.left); }
			   System.out.println(node);
			   if (node.right != null) { printInOrder(node.right); }
	   }

	   public void printInOrder() {
			   printInOrder(this.rootNode);
	   }

	   private void printTree(Node node, String location) {
			   if (node.left != null) { printTree(node.left, location + "L"); }
			   System.out.println(location + " : " + node);
			   if (node.right != null) { printTree(node.right, location + "R"); }
	   }

	   public void printTree() {
			   printTree(this.rootNode, "-");
	   }

  
	   public static void test() {
			   BinTree tree = new BinTree();
			   tree.addValue("M Root");
			   tree.addValue("A Left");
			   tree.addValue("Z Right");
			   tree.addValue("F");
			   tree.addValue("A");
			   tree.addValue("R");
			   tree.addValue("ZZ");
			   tree.printInOrder();
			   System.out.println();
			   System.out.println();
			   tree.printTree();
	   }
}



Note, the node is private. The node operations are private. I don't have to know the nodes to use the class. You'll find most implementations share this.

Hope this helps.
Was This Post Helpful? 0
  • +
  • -

#7 1lacca   User is offline

  • code.rascal
  • member icon

Reputation: 44
  • View blog
  • Posts: 3,822
  • Joined: 11-August 05

Re: LinkedBinaryTree Dictionary

Posted 27 December 2007 - 08:09 AM

Excellent answer baavgai, I was about to write somwthing similar, but I just couldn't get back to it in time!
Was This Post Helpful? 0
  • +
  • -

#8 Samer   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-July 07

Re: LinkedBinaryTree Dictionary

Posted 27 December 2007 - 09:22 AM

Thanks a lot baavgai, I got what you mean.. I was really helpful.. But I want to clarify something, that the whole point of the Tester is to test the methods of the binary tree if they are working in order to use them in the dictionary.. So I still need the implementation of the methods of the dictionary.. can anyone help..

The code I already implemented for this moment.. You can give me pseudo code and I'll will translate it to java in case you want to follow my code exactly..
import EmptyDictionaryException.EmptyDictionaryException;
import InvalidKeyException.InvalidKeyException;

public class Dictionary {
	protected Comparator comp;
	protected LinkedBinaryTree T;
	
	public Dictionary(Comparator c) {
		T = new LinkedBinaryTree();
		comp = c;
	}
	
	public boolean find() {
		/* find a key in the binary tree T.
		 * if the key exists, return true;
		 * else return false.*/
	}
	
	public NodeList findall() {
		/* Return a list that contains all the objects in T in
		 * a nondecreasing order
		 * The order of the objects is determind by comparator comp.*/
	}
	
	public void insertKey(Object key) throws InvalidKeyException {
		checkKey(key); // may throw and InvalidKeyException
		//it inserts the key into T
	}
	
	public void removeKey(Object key) throws EmptyDictionaryException {
		if(T.isEmpty())
			throw new EmptyDictionaryException("Dictionary is empty");
		/*it removes all the occurences of key in T,
		 * knowing that T might contain multiple instances of key.*/
	}
	
	protected void checkKey(Object Key) throws InvalidKeyException {
		try {
			comp.compare(key, key);
		}
		catch(Exception e) {
			throw new InvalidKeyException("Invalid key");
		}
	}
}


Was This Post Helpful? 0
  • +
  • -

#9 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7295
  • View blog
  • Posts: 15,185
  • Joined: 16-October 07

Re: LinkedBinaryTree Dictionary

Posted 27 December 2007 - 10:32 AM

Seriously? That's the easy part. You're just doing a wrapper class around a list!

Here's an example using Java's ArrayList as a base:
import java.util.ArrayList;
import java.util.List;
import java.util.Comparator;
   
public class MyDictionary {
   protected Comparator comp;
   protected List internalStorage;
	
	public MyDictionary(Comparator c) {
	   this.internalStorage = new ArrayList();
	   this.comp = c;
	}
	
	private int fileObjectIndex(Object key) {
	   for(int i=0, j=this.internalStorage.size(); i<j; i++) {
		  if (comp.compare(key, this.internalStorage.get(i))==0) {
			 return i;
		  }
	   }
	   return -1;
	}
	
	public boolean find(Object key) {
		/* find a key in the binary tree T.
		 * if the key exists, return true;
		 * else return false.*/
	   return fileObjectIndex(key)!=-1;
	}
	
	
	public void insertKey(Object key) throws Exception {
		checkKey(key); // may throw and InvalidKeyException
		//it inserts the key into T
		int index = fileObjectIndex(key);
		if (index!=-1) { 
		   this.internalStorage.remove(index);
		}
		this.internalStorage.add(key);
	}
	
	public Object[] findall() {
		/* Return a list that contains all the objects in T in
		 * a nondecreasing order
		 * The order of the objects is determind by comparator comp.*/
	   return this.internalStorage.toArray();
	}

	public void removeKey(Object key) throws Exception {
		if(this.internalStorage.size()==0)
			throw new Exception("Dictionary is empty");
		/*it removes all the occurences of key in T,
		 * knowing that T might contain multiple instances of key.*/
		int index = fileObjectIndex(key);
		if (index!=-1) { 
		   this.internalStorage.remove(index);
		}
	}
	
	protected void checkKey(Object key) throws Exception {
		try {
		   comp.compare(key, key);
		} catch(Exception e) {
			throw new Exception("Invalid key");
		}
	}
 }



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

#10 Samer   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-July 07

Re: LinkedBinaryTree Dictionary

Posted 28 December 2007 - 10:35 AM

Thanks a lot
Was This Post Helpful? 0
  • +
  • -

#11 Samer   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-July 07

Re: LinkedBinaryTree Dictionary

Posted 04 January 2008 - 08:27 AM

Guys I implemented the method, and I also implemented a tester, but it seems I'm still having a problem, in the execution of the program.. Here's the code.

import BoundaryViolationException.BoundaryViolationException;
import EmptyTreeException.EmptyTreeException;
import InvalidPositionException.InvalidPositionException;
import NonEmptyTreeException.NonEmptyTreeException;
public class LinkedBinaryTree
{
	protected BTNode root;
	protected int size;
	public LinkedBinaryTree() {
		root = null;
		size = 0;
	}
	public int size() {
		return size;
	}
	public boolean isEmpty() {
		return (size==0);
	}
	public boolean isInternal(BTNode v) throws InvalidPositionException {
		checkPosition(v);
		return (hasLeft(v) || hasRight(v));
	}
	public boolean isExternal(BTNode v) throws InvalidPositionException {
		return !isInternal(v);
	}
	public boolean isRoot(BTNode v) throws InvalidPositionException {
		checkPosition(v);
		return (v == root());
	}
	
	public boolean hasLeft(BTNode v)throws InvalidPositionException {
		BTNode vv = checkPosition(v);
		return (vv.getLeft() != null);
	}
	public boolean hasRight(BTNode v)throws InvalidPositionException {
		BTNode vv = checkPosition(v);
		return (vv.getRight() != null);
	}
	public BTNode root() throws EmptyTreeException {
		if (root == null)
			throw new EmptyTreeException("The tree has no root");
		return root;
	}
	public BTNode left(BTNode v)throws InvalidPositionException, BoundaryViolationException
	{
		if (! hasLeft(v))
			throw new BoundaryViolationException("No left child");
		return ((BTNode)v).getLeft();
	}
	public BTNode right(BTNode v)throws InvalidPositionException, BoundaryViolationException
	{
		if (! hasRight(v))
			throw new BoundaryViolationException("no right child");
		return ((BTNode)v).getRight();
	}
	public BTNode parent(BTNode v)throws InvalidPositionException, BoundaryViolationException
	{
		if (isRoot(v))
			throw new BoundaryViolationException("Root has no parent");
		return ((BTNode)v).getParent();
	}
	public Iterator children(BTNode v) throws InvalidPositionException
	{
		NodeList children = new NodeList();
		if (hasLeft(v))
			children.insertLast(left(v).element());
		if (hasRight(v))
			children.insertLast(right(v).element());
		return children.elements();
	}   
	public Iterator positions()
	{
		NodeList positions = new NodeList();
		if (size != 0)
			inorderPositions(root(), positions);
		return positions.elements();
	}
	public Iterator elements()
	{
		Iterator positer = positions();
		NodeList elements = new NodeList();
		for (int i = 0; i < size; i++)
		{
			elements.insertLast((positer.next()));
			
		}
		return elements.elements();
	}
	public Object replace(BTNode v, Object o) throws InvalidPositionException
	{
		BTNode vv = checkPosition(v);
		Object temp = v.element();
		vv.setElement(o);
		return temp;
		
		
	}
	public BTNode sibling(BTNode v)throws InvalidPositionException, BoundaryViolationException
	{
		try
		{
			BTNode p = parent(v);
			BTNode lc = left(p);
			if (v == lc)
				return right(p);
			else
				return lc;
		}
		catch(BoundaryViolationException e)
		{
			throw new BoundaryViolationException("Node has  no sibling");
		}
	}
	
	public BTNode insertLeft (BTNode v, Object e)throws InvalidPositionException
	{
		if (hasLeft(v))
			throw new InvalidPositionException("Node already has a left child");
		BTNode vv = (BTNode)v;
		BTNode ww = createNode(e, vv, null, null);
		vv.setLeft((ww));
		size++;
		return ww;
	}
	public BTNode insertRight(BTNode v, Object e) throws InvalidPositionException {
		if(hasRight(v))
			throw new InvalidPositionException("Node already has a right child.");
		BTNode vv = (BTNode) v;
		BTNode w = createNode(e, vv, null, null);
		vv.setRight(w);
		size++;
		return w;
	}
	
	public Object remove(BTNode v) throws InvalidPositionException {
		if(hasLeft(v) && hasRight(v))
			throw new InvalidPositionException("Cannot remove node with 2 children.");
		BTNode vv = (BTNode) v;
		BTNode ww;
		if(hasLeft(v))
			ww = (BTNode) left(v);
		else if (hasRight(v))
			ww = (BTNode) right(v);
		else
			ww = null;
		if(v == root()) {
			if(ww != null)
				ww.setParent(null);
			root = ww;
		}
		else {
			BTNode uu = (BTNode) parent(v);
			if(hasLeft(uu) && v == left(uu))
				uu.setLeft(ww);
			else
				uu.setRight(ww);
			if(ww != null)
				ww.setParent(uu);
		}
		size--;
		return v.element();
	}
	public BTNode addRoot(Object e) throws NonEmptyTreeException {
		if(!isEmpty())
			throw new NonEmptyTreeException("Tree already has a root.");
		size = 1;
		root = createNode(e, null, null, null);
		return root;
		
	}
	
	public void attach(BTNode v, LinkedBinaryTree T1, LinkedBinaryTree T2) throws InvalidPositionException {
		if(isInternal(v))
			throw new InvalidPositionException("Cannot attach from internal node.");
		BTNode vv = (BTNode) v;
		if(!T1.isEmpty()) {
			vv.setLeft((BTNode) T1.root());
			((BTNode) T1.root()).setParent(vv);
			
		}
		if(!T2.isEmpty()) {
			vv.setRight((BTNode) T2.root());
			((BTNode) T2.root()).setParent(vv);
		}
		
		size = T1.size() + T2.size() + 1;
	}
	
	protected BTNode checkPosition(BTNode v) throws InvalidPositionException {
		if(v == null || !(v instanceof BTNode))
			throw new InvalidPositionException("The position is invalid.");
		return (BTNode) v;
	}
	
	protected BTNode createNode(Object element, BTNode parent, BTNode left, BTNode right) {
		return new BTNode(element, parent, left, right);
	}
	
	protected void inorderPositions(BTNode v, NodeList pos) throws InvalidPositionException {
		if(hasLeft(v))
			inorderPositions(left(v), pos);
		pos.insertLast(v.element());
		if(hasRight(v))
			inorderPositions(right(v), pos);
	}
	
}


import NonComparableException.NonComparableException;

public class Comparator {
	public int compare(Object A, Object B) throws NonComparableException {
		try {
			if(((Comparable)A).compareTo((Comparable)B) < 0)
				return -1; 
			if(((Comparable)A).compareTo((Comparable)B) > 0)
				return 1;
				return 0;
		}
		catch(Exception e) {
			throw new NonComparableException("The keys of the entries cannot be compared");
		}
	}
}


import EmptyDictionaryException.EmptyDictionaryException;
import InvalidKeyException.InvalidKeyException;

public class Dictionary {
	protected Comparator comp;
	protected LinkedBinaryTree T;
	
	public Dictionary(Comparator c) {
		T = new LinkedBinaryTree();
		comp = c;
	}
	
	public boolean find(Object key) throws InvalidKeyException {
		checkKey(key);
			if(T.isEmpty())
				return false;
		BTNode t_root = T.root();
		while(true) {
			if(comp.compare(key, t_root) < 0) {
				if(T.hasLeft(t_root))
					t_root = T.left(t_root);
				else
					return false;
			}
			else if(comp.compare(key, t_root)>0) {
				if(T.hasRight(t_root))
					t_root = T.right(t_root);
				else
					return false;
			}
			else
				return true; 
		}
	}
	
	public NodeList findall() {
		NodeList list = new NodeList();
		Iterator i = T.elements();
		while(i.hasNext())
			list.insertLast(i.next());
		return list;
	}
	
	
	public void insertKey(Object key) throws InvalidKeyException {
		checkKey(key);
		if(T.isEmpty())
			T.addRoot(key);
		BTNode t_root = T.root();
		while(true) {
			if(comp.compare(key, t_root.element()) < 0) {
				if(T.hasLeft(t_root))
					t_root = T.left(t_root);
				else {
					T.insertLeft(t_root,key);
					return;
				}
			}
			else {
				if(T.hasRight(t_root))
					t_root = T.right(t_root);
				else {
					T.insertRight(t_root,key);
					return;
				}
			}
		}
	}

	public void removeKey(Object key) throws EmptyDictionaryException, InvalidKeyException {
		checkKey(key);
		if(T.isEmpty())
			throw new EmptyDictionaryException("Dictionary is empty");
		BTNode t_root = T.root(), temp;
		while(true) {
			if(comp.compare(key, t_root.element()) < 0) {	 
				if(T.hasLeft(t_root))
					t_root = T.left(t_root);
				else
					return;	
			}
			else if(comp.compare(key, t_root.element()) > 0) {
				if(T.hasRight(t_root))
					t_root = T.right(t_root);
				else
					return;
			}
			else {
				temp = t_root;
				if(!T.hasLeft(t_root)) {
					t_root = T.right(t_root);
					T.remove(temp);
				}
				else if(!T.hasRight(t_root)) {
					t_root=T.left(t_root);
					T.remove(temp);
				}
				else {
					temp = T.right(t_root);
					while(T.hasLeft(temp))
						temp=T.left(temp);
					t_root.setElement(T.remove(temp));
				}
			}
		}
	}
	
	protected void checkKey(Object Key) throws InvalidKeyException {
		try {
			comp.compare(Key, Key);
		}
		catch(Exception e) {
			throw new InvalidKeyException("Invalid key");
		}
	}
}


import java.util.Scanner;

public class DictionaryTester {
	public static void main(String[] args) {
		
		Scanner input = new Scanner(System.in);
		Comparator c = new Comparator();
		Dictionary d = new Dictionary(c);
		int choice;
		System.out.println("Welcome To The Dictionary");
		System.out.println("--------------------------------------------");
				
		do {
			System.out.println("1- Find a word.");
			System.out.println("2- View a list of all words.");
			System.out.println("3- Insert a new word.");
			System.out.println("4- Remove a word.");
			System.out.println("Press 0 to exit the Dictionary.");
			System.out.println("--------------------------------------------");
			System.out.println("Select one of the options: ");
			choice = input.nextInt();
			if(choice == 1) {
				System.out.println("Enter the word you want to find: ");
				String f = input.next();
				d.find(f);
			}
			
			else if(choice == 2)
				d.findall();
			
			else if(choice == 3) { 
				System.out.print("Enter the word you want to insert: ");
				String i = input.next();
				d.insertKey(i);
			}
			
			else if(choice == 4){
				System.out.print("Enter the word you want to remove: ");
				String r = input.next();
				d.removeKey(r);
			}
		}
		while(choice != 0);
	}
}



When I choose the 3rd choice, which inserting words in the dictionary, I get no problem, but in the other methods i'm getting the following exceptions:

Select one of the options:
1
Enter the word you want to find:
samer
Exception in thread "main" NonComparableException.NonComparableException: The keys of the entries cannot be compared
at Comparator.compare(Comparator.java:13)
at Dictionary.find(Dictionary.java:19)
at DictionaryTester.main(DictionaryTester.java:25)
Java Result: 1

Select one of the options:
2
Exception in thread "main" java.util.NoSuchElementException: No next element.
at ElementIterator.next(ElementIterator.java:25)
at LinkedBinaryTree.elements(LinkedBinaryTree.java:84)
at Dictionary.findall(Dictionary.java:38)
at DictionaryTester.main(DictionaryTester.java:29)
Java Result: 1


Select one of the options:
4
Enter the word you want to remove:
hi
Exception in thread "main" BoundaryViolationException.BoundaryViolationException: no right child
at LinkedBinaryTree.right(LinkedBinaryTree.java:53)
at Dictionary.removeKey(Dictionary.java:91)
Was This Post Helpful? 0
  • +
  • -

#12 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7295
  • View blog
  • Posts: 15,185
  • Joined: 16-October 07

Re: LinkedBinaryTree Dictionary

Posted 04 January 2008 - 09:51 AM

Your Comparator is blocking the first error, make a simple test one. Try something like this:
public class Comparator {
	public int compare(Object a, Object b)  { return ((Comparable)a).compareTo(b); }
}



Also, it looks like your dictionary isn't growing like you think it is. Double check by giving yourself more feedback. In the menu, put a line like:
System.out.println(d.size() + " items available.");


Was This Post Helpful? 0
  • +
  • -

#13 Samer   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-July 07

Re: LinkedBinaryTree Dictionary

Posted 05 January 2008 - 06:32 AM

I tried these, the size is working but for the first word i add, the size was 2, and then it started increasing by 1..
The find method worked fine with the comparator that you gave me.
find all returned [email protected], and it uses the ElementIterator class and the method elements() which returns a new ElementIterator(this) and the method insertLast

	public DNode insertLast(Object element) {
		numElts++;
		DNode newNode = new DNode(trailer.getPrev(), trailer, element);
		trailer.getPrev().setNext(newNode);
		trailer.setPrev(newNode);
		return newNode;


import BoundaryViolationException.BoundaryViolationException;
import EmptyListException.EmptyListException;
import InvalidPositionException.InvalidPositionException;
import java.util.NoSuchElementException;
public class ElementIterator implements Iterator {
	protected NodeList list;
	protected DNode cur;
	
	public ElementIterator() {
	}
	
	public ElementIterator(NodeList L) {
		list = L;
		if(list.isEmpty())
			cur = null;
		else
			cur = list.first();
	}
	
	public boolean hasNext() throws NoSuchElementException, EmptyListException, InvalidPositionException, BoundaryViolationException {
		return (cur != null);
	}
	
	public Object next() throws NoSuchElementException {
		if(!hasNext()) throw new NoSuchElementException("No next element.");
		Object toReturn = cur.element();
		if(cur.element() == list.last().element())
			cur = null;
		else
			cur = list.next(cur);
		return toReturn;
	}
}


Was This Post Helpful? 0
  • +
  • -

#14 Samer   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-July 07

Re: LinkedBinaryTree Dictionary

Posted 05 January 2008 - 06:47 AM

Oh i forgot to mentipn about the remove.. its giving me No Right Child exception..

	public BTNode insertRight(BTNode v, Object e) throws InvalidPositionException {
		if(hasRight(v))
			throw new InvalidPositionException("Node already has a right child.");
		BTNode vv = (BTNode) v;
		BTNode w = createNode(e, vv, null, null);
		vv.setRight(w);
		size++;
		return w;
	}
	


	public BTNode right(BTNode v)throws InvalidPositionException, BoundaryViolationException
	{
		if (! hasRight(v))
			throw new BoundaryViolationException("No right child");
		return ((BTNode)v).getRight();
	}

Was This Post Helpful? 0
  • +
  • -

#15 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7295
  • View blog
  • Posts: 15,185
  • Joined: 16-October 07

Re: LinkedBinaryTree Dictionary

Posted 05 January 2008 - 09:46 AM

You're still trying to get that homemade binary tree to work as storage for your dictionary?

Well, then, don't even bother with playing with the dictionary part until the tree works. The code I see looks like the original stuff, which has a myriad of problems.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2