Results 1 to 1 of 1
Thread: My recursive problem
- 11-18-2011, 03:08 AM #1
Member
- Join Date
- Nov 2010
- Posts
- 40
- Rep Power
- 0
My recursive problem
So I'm trying to find the height of my Binary Search Tree using a recursive method. Here is my code for my Tree data structure
So when trying to find the height of my tree using the heightTester() method which uses the recursiveHeight(BinaryTreeNode<T> n) method in the line that calls theJava Code:package Structures; import java.util.NoSuchElementException; public class ArrayBinarySearchTree<T extends Comparable<T>> implements BinarySearchTreeADT<T> { //private Object[] dataStorage = new Object[10]; use this private BinaryTreeNode<T> root = new BinaryTreeNode<T>(); private int counter = 0; //method complete @Override public void addElement(T element) { if (counter == 0) { BinaryTreeNode<T> node = new BinaryTreeNode<T>(element); root = node; counter++; } else { addHelp(root, element); } } //method complete @Override public boolean contains(T targetElement) { BinaryTreeNode<T> node = new BinaryTreeNode<T>(); node = root; boolean temp = recursiveContainsSearch(node, targetElement); return temp; } //method complete @Override public T find(T targetElement) { BinaryTreeNode<T> node = new BinaryTreeNode<T>(); node = root; if(!recursiveContainsSearch(node, targetElement)) { throw new NoSuchElementException("The element "+targetElement+" does not excist in this tree"); } else { return recursiveElementFind(node, targetElement); } } //method complete @Override public T findMax() { BinaryTreeNode<T> node = new BinaryTreeNode<T>(); node = root; return recursiveFindMax(node); } //method complete @Override public T findMin() { BinaryTreeNode<T> node = new BinaryTreeNode<T>(); node = root; return recursiveFindMin(node); } //method complete @Override public boolean isEmpty() { if (counter == 0) return true; return false; } @Override public Iterator<T> iteratorLevelOrder() { // TODO Auto-generated method stub return null; } @Override public Iterator<T> iteratorOrdered() { // TODO Auto-generated method stub return null; } @Override public Iterator<T> iteratorPostOrder() { // TODO Auto-generated method stub return null; } @Override public Iterator<T> iteratorPreOrdered() { // TODO Auto-generated method stub return null; } @Override public T removeElement(T targetElement) { // TODO Auto-generated method stub return null; } @Override public T removeMax() { // TODO Auto-generated method stub return null; } @Override public T removeMin() { // TODO Auto-generated method stub return null; } @Override public int size() { return counter; } //helper methods private void addHelp(BinaryTreeNode<T> n, T element) { if((element.compareTo(n.getElement()) <= 0) && (n.getLeft() != null)) addHelp(n.getLeft(), element); if((element.compareTo(n.getElement()) > 0) && (n.getRight() != null)) addHelp(n.getRight(), element); if((element.compareTo(n.getElement()) <= 0) && (n.getLeft() == null)) { BinaryTreeNode<T> node = new BinaryTreeNode<T>(element); n.setLeft(node); counter++; } if((element.compareTo(n.getElement()) > 0) && (n.getRight() == null)) { BinaryTreeNode<T> node = new BinaryTreeNode<T>(element); n.setRight(node); counter++; } } //use to build array public void buildArray() { } public int heightTester() { BinaryTreeNode<T> node = new BinaryTreeNode<T>(); node = root; return recursiveHeight(node); } public int recursiveHeight(BinaryTreeNode<T> n) { if((n.getLeft() == null) && (n.getRight() == null)) // HERE IS WHERE THE PROBLEM LIES!!!!!!! return 0; int left = 0; int right = 0; if(n.getLeft() != null) return recursiveHeight(n.getLeft()) + 1; if(n.getRight() != null) return recursiveHeight(n.getLeft()) + 1; if(left < right) return right; return left; } //helper for "public boolean contains(T targetElement)" private boolean recursiveContainsSearch(BinaryTreeNode<T> n, T element) { if((element.compareTo(n.getElement()) < 0) && (n.getLeft() != null)) return recursiveContainsSearch(n.getLeft(), element); if((element.compareTo(n.getElement()) > 0) && (n.getRight() != null)) return recursiveContainsSearch(n.getRight(), element); if((element.compareTo(n.getElement()) == 0)) return true; if((element.compareTo(n.getElement()) < 0) && n.getLeft() == null) return false; else if((element.compareTo(n.getElement()) > 0) && n.getRight() == null) return false; return false;//should be no other options } //helper for "public T find(T targetElement)" private T recursiveElementFind(BinaryTreeNode<T> n, T element) { if((element.compareTo(n.getElement()) < 0) && n.getLeft() != null) return recursiveElementFind(n.getLeft(), element); if((element.compareTo(n.getElement()) > 0) && n.getRight() != null) return recursiveElementFind(n.getRight(), element); if(element.compareTo(n.getElement()) == 0) return n.getElement(); return null; } //helper for "public T findMin()" private T recursiveFindMin(BinaryTreeNode<T> n) { if(n.getLeft() != null) return recursiveFindMin(n.getLeft()); return n.getElement(); } //helper for "public T findMax()" private T recursiveFindMax(BinaryTreeNode<T> n) { if(n.getRight() != null) return recursiveFindMax(n.getRight()); return n.getElement(); } } //end class
recursiveHeight method it should pass the root node to the method. Here is where this gets very weird. Running debug on Eclipse I see that sometimes it actually does pass the node
and sometimes it doesn't. Sometimes it makes it in the recursiveHeight method and recursively loops once but then I get a null pointer exception at the line of code
Here is the client code im using to test my treeJava Code:if((n.getLeft() == null) && (n.getRight() == null))
This should produce the tree which looks likeJava Code:package projectmain; import Structures.ArrayBinarySearchTree; public class TesterMain { public static void main(String[] args) { ArrayBinarySearchTree<Integer> tester = new ArrayBinarySearchTree<Integer>(); tester.addElement(20); tester.addElement(15); tester.addElement(13); tester.addElement(14); tester.addElement(25); tester.addElement(33); tester.addElement(39); tester.addElement(21); tester.addElement(17); tester.addElement(31); System.out.println(tester.size()); System.out.println(tester.heightTester()); } }
20
/ \
15 25
/ \ / \
13 17 21 33
\ / \
14 31 39
Thanks in advance for all your help.
Similar Threads
-
Problem with recursive use of arrays.
By Falantar in forum New To JavaReplies: 8Last Post: 01-26-2011, 03:23 AM -
recursive method problem
By melody in forum New To JavaReplies: 1Last Post: 10-29-2009, 07:15 AM -
Java Recursive method problem
By kj2009 in forum Advanced JavaReplies: 2Last Post: 02-25-2009, 03:19 PM -
Recursive File List - Help me problem solve please
By caps_lock in forum New To JavaReplies: 17Last Post: 01-14-2009, 06:44 PM -
problem with recursive binary search program
By imran_khan in forum New To JavaReplies: 3Last Post: 08-02-2007, 03:08 PM


LinkBack URL
About LinkBacks
Reply With Quote

Bookmarks