Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: BinarySearchTree - Having trouble adding elements to a vector from the tree. Recursive method! Help :)

  1. #1
    Junior Member
    Join Date
    Feb 2013
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default BinarySearchTree - Having trouble adding elements to a vector from the tree. Recursive method! Help :)

    Hi, im trying to implement code for a binary search tree. This method should take all the elements in the tree and add them to a vector sorted with lowest first, the elements in the tree are inorder.

    It gives me java.lang.ArrayIndexOutOfBoundsException at a[temp]=n.element;

    /*
    	 * Adds all elements from the tree rooted at n in inorder to the array a
    	 * starting at a[index].
    	 * Returns the index of the last inserted element + 1 (the first empty
    	 * position in a).
    	 */
    	private int toArray(BinaryNode<E> n, E[] a, int index) {
     
    		return addArray(n, a, index);
     
    	}
     
    	private int addArray(BinaryNode<E> n, E[] a, int index){
    		if(n != null && index>=0 ){
    			int temp = index;
    		    temp = addArray(n.left, a, temp);
    			a[temp]=n.element;
    			temp++;
    			temp = addArray(n.right, a, temp);
    			return temp;
    		} else {
    			return index;
    	}}

    Its a part of another public method that rebuilds the tree. The purpose of the rebuild method is to make the tree balanced.

    /** 
    	 * Builds a complete tree from the elements in the tree.
    	 */
    	public void rebuild() {
    		E[] a = (E[]) new Comparable[size];
    		int first= 0;
    		int last = toArray(root, a, first);
    		root= buildTree(a, first, last-1 );
     
    	}

    And this is my main program where i test to add elements (ints) to the tree and then rebuild it:

    public static void main(String[] args){
     
    	BSTVisualizer bstv = new BSTVisualizer("Fint träd", 500, 500);
    	BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
    //	for(int i=3; i<10; i++){
    //	tree.add(i);
    //	tree.add(i);
    //	}
    	tree.add(4);
    	tree.add(5);
    	tree.add(3);
    	tree.add(1);
    	tree.add(1);
    	tree.add(2);
    	tree.add(8);
    	tree.add(7);
    	tree.rebuild();
    	bstv.drawTree(tree);
     
    	System.out.println(tree.height());
    	System.out.println("//");
    	System.out.println(tree.size());
    	System.out.println("//");
    	tree.printTree();
     
     
    }
    }


    I appreciate any help i receive! Ty!


  2. #2
    Administrator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    24,848
    Thanks
    64
    Thanked 2,645 Times in 2,615 Posts

    Default Re: BinarySearchTree - Having trouble adding elements to a vector from the tree. Recursive method! Help :)

    its not working
    Please explain what "not working" means. There are many ways for code to not work.

    How can the code be compiled and executed for testing?


    Please edit your post and wrap your code with
    [code=java]
    <YOUR CODE HERE>
    [/code]
    to get highlighting and preserve formatting.

  3. #3
    Junior Member
    Join Date
    Feb 2013
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: BinarySearchTree - Having trouble adding elements to a vector from the tree. Recursive method! Help :)

    Quote Originally Posted by Norm View Post
    Please explain what "not working" means.
    Sorry, ive edited the post now

  4. #4
    Administrator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    24,848
    Thanks
    64
    Thanked 2,645 Times in 2,615 Posts

    Default Re: BinarySearchTree - Having trouble adding elements to a vector from the tree. Recursive method! Help :)

    java.lang.ArrayIndexOutOfBoundsException
    Why is the index to the array past the end of the array?
    Remember that the range of index for an array is 0 to the length-1.

    The code should test for invalid indexes and not use them.

  5. #5
    Junior Member
    Join Date
    Feb 2013
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: BinarySearchTree - Having trouble adding elements to a vector from the tree. Recursive method! Help :)

    Well when i use the method i insert a empty vector with the length equal to the number of elements in the tree, u can see it under the method rebuild().
    So it shouldnt be out of bounds.

    I post the full binary search tree class here and maybe ull get a better picture of the problem.

    package bst;
     
    import java.util.NoSuchElementException;
     
    import sun.org.mozilla.javascript.internal.Node;
     
    public class BinarySearchTree<E extends Comparable<? super E>> {
    	BinaryNode<E> root;
        int size;
     
    	/**
    	 * Constructs an empty binary searchtree.
    	 */
    	public BinarySearchTree() {
    		root=null;
    	}
     
    	/**
    	 * Inserts the specified element in the tree if no duplicate exists.
    	 * @param x element to be inserted
    	 * @return true if the the element was inserted
    	 */
    	public boolean add(E x) {
    		if(root==null){
    			root = new BinaryNode<E>(x);
    			return true;
    		} else{
    			return add(root,x);
    		}
     
    	}
     
    	private boolean add(BinaryNode<E> node, E x) {
    		int comp = node.element.compareTo(x);
    		if(comp==0){
    			return false;
    		} else if(comp>0){
    			if(node.left==null){
    				node.left=new BinaryNode<E>(x);
    				return true;
    			} else {
    			return add(node.left,x);
    			}
    		} else if(node.right==null){
    			node.right= new BinaryNode<E>(x);
    			return true;
    		}
    			return add(node.right,x);
    		}
     
     
    	/**
    	 * Computes the height of tree.
    	 * @return the height of the tree
    	 */
    	public int height() {
    		return heightOfBinaryTree(root);
    	}
     
    	/**
    	 * Returns the number of elements in this tree.
    	 * @return the number of elements in this tree
    	 */
     
    	public int size() {
    		size=countsize(root);
    		return size;
    	}
     
        private int countsize(BinaryNode<E> node) {
        	if(node==null){
        		return 0;
        	}
            if (node.left == null && node.right == null) {
                return 1;
            } else {
                return 1+countsize(node.left) + countsize(node.right); }
        }
     
    	/**
    	 * Print tree contents in order.
    	 */
    	public void printTree() {
    		printNodes(root);
    	}
     
    	private void printNodes(BinaryNode<E> node) {
    //		if(node==null){
    //			throw new NoSuchElementException("Inget element");
    //		} else {
    		if(node != null){
    			printNodes(node.left);
    			System.out.println(node.element);
    			printNodes(node.right);
    		}
    	}
     
    	/** 
    	 * Builds a complete tree from the elements in the tree.
    	 */
    	public void rebuild() {
    		E[] a = (E[]) new Comparable[size];
    		int first= 0;
    		int last = toArray(root, a, first);
    		root= buildTree(a, first, last-1 );
     
    	}
     
    	/*
    	 * Adds all elements from the tree rooted at n in inorder to the array a
    	 * starting at a[index].
    	 * Returns the index of the last inserted element + 1 (the first empty
    	 * position in a).
    	 */
    	private int toArray(BinaryNode<E> n, E[] a, int index) {
     
    		return addArray(n, a, index);
     
    	}
     
    	private int addArray(BinaryNode<E> n, E[] a, int index){
    		if(n != null && index>=0 ){
    			int temp = index;
    		    temp = addArray(n.left, a, temp);
    			a[temp]=n.element;
    			temp++;
    			temp = addArray(n.right, a, temp);
    			return temp;
    		} else {
    			return index;
    	}}
     
    	/*
    	 * Builds a complete tree from the elements a[first]..a[last].
    	 * Elements in the array a are assumed to be in ascending order.
    	 * Returns the root of tree.
    	 */
    	private BinaryNode<E> buildTree(E[] a, int first, int last) {
     
    		return constructTree(a, first, last);
    	}
     
    	private BinaryNode<E> constructTree(E[] a, int first, int last) {
    		int temp = (first+last)/2;
    		if(first>last){
    		BinaryNode<E> node = new BinaryNode<E>(a[temp]);
    		return node;
    		}
    	    BinaryNode<E> nodeleft = constructTree(a, first, temp);
    	    BinaryNode<E> noderoot = new BinaryNode<E>(a[temp]);
    	    noderoot.left=nodeleft;
    		BinaryNode<E> noderight = constructTree(a, temp, last);
    		noderoot.right=noderight;
    		return noderoot;
     
    	}
     
    	private int heightOfBinaryTree(BinaryNode<E> node)
    	{
    	    if (node == null)
    	    {
    	        return 0;
    	    }
    	    else
    	    {
    	        return 1 +
    	        Math.max(heightOfBinaryTree(node.left),
    	            heightOfBinaryTree(node.right));
    	    }
    	}
     
     
     
    	static class BinaryNode<E> {
    		E element;
    		BinaryNode<E> left;
    		BinaryNode<E> right;
     
    		private BinaryNode(E element) {
    			this.element = element;
    		}	
    	}
     
    }

    And these are my full error messages, all linked to the same problem (using addArray method).

     
    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
    	at bst.BinarySearchTree.addArray(BinarySearchTree.java:125)
    	at bst.BinarySearchTree.addArray(BinarySearchTree.java:124)
    	at bst.BinarySearchTree.addArray(BinarySearchTree.java:124)
    	at bst.BinarySearchTree.toArray(BinarySearchTree.java:117)
    	at bst.BinarySearchTree.rebuild(BinarySearchTree.java:104)
    	at bst.Main.main(Main.java:21)

Similar Threads

  1. Having trouble understanding recursive methods??
    By orbin in forum What's Wrong With My Code?
    Replies: 0
    Last Post: November 17th, 2012, 00:08
  2. Binary Tree Longest Increasing Path (Recursive)
    By varsis in forum Algorithms & Recursion
    Replies: 0
    Last Post: April 13th, 2012, 22:19
  3. Replies: 3
    Last Post: January 6th, 2012, 08:18
  4. [SOLVED] ArrayList object's elements confusing??? doesnt replace the elements? set() method?
    By chronoz13 in forum What's Wrong With My Code?
    Replies: 10
    Last Post: June 21st, 2011, 13:20
  5. Method Adding elements to an array with certain restrictions
    By Newoor in forum Collections and Generics
    Replies: 1
    Last Post: December 13th, 2009, 10:13