Results 1 to 13 of 13

Thread: Help anyone!

  1. #1
    ~ HP9200 ~ is offline Member
    Join Date
    Jul 2009
    Posts
    5
    Rep Power
    0

    Exclamation Help anyone!

    I am a beginner in Java Programming and I am writing a code for Binary Tree without using a node as specified by our teacher. I haven't finished it yet and am actually at the beginning phase. Here is the code.

    Binary Tree code:
    Java Code:
    public class BinaryTree {
    
    	public Integer root;
    	public BinaryTree leftSubTree = new BinaryTree();
    	public BinaryTree rightSubTree = new BinaryTree();
    
    	public BinaryTree() {
    		root = null;
    		leftSubTree = null;
    		rightSubTree = null;
    	}
    
    	public BinaryTree(Integer value) {
    		root = value;
    		leftSubTree = null;
    		rightSubTree = null;
    	}
    
    	public BinaryTree(Integer value, BinaryTree left, BinaryTree right) {
    		root = value;
    		leftSubTree = left;
    		rightSubTree = right;
    	}
    
    	public void insert(Integer value) {
    		System.out.println(value);
    		if (root == null) {
    			root = value;
    		} else if (value > root) {
    			rightSubTree.insert(value);
    		} else if (value < root) {
    			leftSubTree.insert(value);
    		}
    	}
    
    	public int getHeight() {
    		int height = 0;
    
    		return height;
    	}
    
    	public boolean isEmpty() {
    		if (true) {
    			return true;
    		} else
    			return false;
    	}
    
    	public int countNodes() {
    		int numberOfNodes = 0;
    		return numberOfNodes;
    	}
    
    	public int countLeaves() {
    		int numberOfLeaves = 0;
    		return numberOfLeaves;
    	}
    
    	public void destroy() {
    
    	}
    
    	public void inorderTraversal() {
    
    	}
    
    	public void preorderTraversal() {
    
    	}
    
    	public void postorderTraversal() {
    
    	}
    
    	public void levelorderTraversal() {
    
    	}
    
    }
    Here is the application:

    Java Code:
    import java.util.Scanner;
    
    public class BinaryTreeApplication {
    	public static BinaryTree BT = new BinaryTree();
    	public static Scanner scan = new Scanner(System.in);
    
    	public static void main(String[] args) {
    		insertToBT();
    	}
    
    	public static void insertToBT() {
    		Integer input;
    		int numberOfInput;
    		System.out.println("How many input do you like?");
    		numberOfInput = scan.nextInt();
    		System.out
    				.println("Enter the numbers to be inputed! Input first the root:");
    		for (int i = 0; i < numberOfInput; i++) {
    			input = (Integer) scan.nextInt();
    			BT.insert(input);
    		}
    	}
    }
    This are the errors I get:

    Could not find the main class. Program will exit
    Stack Overflow

    Thanks for the time! And can someone explain this to me?!o HEHEHEHEHE....

  2. #2
    hardwired's Avatar
    hardwired is offline Senior Member
    Join Date
    Jul 2007
    Posts
    1,576
    Rep Power
    9

    Default

    Java Code:
        public BinaryTree leftSubTree;// = new BinaryTree();
        public BinaryTree rightSubTree;// = new BinaryTree();

  3. #3
    lada314 is offline Member
    Join Date
    Jul 2009
    Posts
    5
    Rep Power
    0

    Default

    Hi,

    maybe you could try to double check the -classpath parameter when u execute it

  4. #4
    ~ HP9200 ~ is offline Member
    Join Date
    Jul 2009
    Posts
    5
    Rep Power
    0

    Default

    maybe you could try to double check the -classpath parameter when u execute it
    kindly enlighten me on this one...

    Java Code:
    public BinaryTree leftSubTree;// = new BinaryTree();
        public BinaryTree rightSubTree;// = new BinaryTree();
    I have tried this one but unfortunately it has a stack overflow error...May you enlighten me on this problem sirs and madams...Thanks

  5. #5
    hardwired's Avatar
    hardwired is offline Senior Member
    Join Date
    Jul 2007
    Posts
    1,576
    Rep Power
    9

    Default

    I have tried this one but unfortunately it has a stack overflow error
    When I made this change to the code you posted, compiled and ran it I got this output in the console:
    Java Code:
    C:\jexp>java BTA
    How many input do you like?
    3
    Enter the numbers to be inputed! Input first the root:
    123
    123
    and no more stack overflow.

  6. #6
    mtyoung is offline Senior Member
    Join Date
    Dec 2008
    Location
    Hong Kong
    Posts
    473
    Rep Power
    6

    Default

    hardwired is right, you make an infinite loop for create new BinaryTree object

    i found that you did not handle input number equal to value of root...
    i also found that you do not ensure existence of subBinaryTree, before insert value to them...

  7. #7
    corlettk is offline Member
    Join Date
    Apr 2009
    Location
    Brisbane
    Posts
    86
    Rep Power
    0

    Default

    My favourite dictionary entry:

    Recursion - See Recursion.

  8. #8
    ~ HP9200 ~ is offline Member
    Join Date
    Jul 2009
    Posts
    5
    Rep Power
    0

    Exclamation URGENT PROBLEM!!!!! Life and Death Situation!!

    well...I have found a way and completed my program....
    Java Code:
    import java.util.Queue;
    import java.util.concurrent.ArrayBlockingQueue;
    
    public class BinaryTree {
    
    	public Integer root;
    	public BinaryTree leftSubTree;
    	public BinaryTree rightSubTree;
    
    	public BinaryTree() {
    		root = null;
    		leftSubTree = null;
    		rightSubTree = null;
    	}
    
    	public BinaryTree(Integer value) {
    		root = value;
    		leftSubTree = null;
    		rightSubTree = null;
    	}
    
    	public BinaryTree(Integer value, BinaryTree left, BinaryTree right) {
    		root = value;
    		leftSubTree = left;
    		rightSubTree = right;
    	}
    
    	public void insert(Integer i) {
    		// System.out.println(i);
    		if (this.root == null) {
    			this.root = i;
    		} else {
    			if (this.root > i) {
    				if (this.leftSubTree == null) {
    					this.leftSubTree = new BinaryTree(i);
    
    				} else {
    					this.leftSubTree.insert(i);
    				}
    			} else {
    				if (this.rightSubTree == null) {
    					this.rightSubTree = new BinaryTree(i);
    				} else {
    					this.rightSubTree.insert(i);
    				}
    			}
    		}
    	}
    
    	public int getHeight() {
    		return getHeight(this) - 1;
    	}
    
    	private int getHeight(BinaryTree BT) {
    		// System.out.println(BT.root);
    		if (BT == null) {
    			return 0;
    		} else {
    			return 1 + Math.max(getHeight(BT.leftSubTree),
    					getHeight(BT.rightSubTree));
    		}
    	}
    
    	public boolean isEmpty() {
    		return (root == null);
    	}
    
    	public int countNodes() {
    		return countNodes(this);
    	}
    
    	private int countNodes(BinaryTree BT) {
    		//System.out.println(BT);
    		if (BT == null)
    			return 0;
    		else
    			return 1 + countNodes(BT.leftSubTree) + countNodes(BT.rightSubTree);
    	}
    
    	public int countLeaves() {
    		return countLeaves(this);
    	}
    
    	private int countLeaves(BinaryTree BT) {
    		if (BT == null)
    			return 0;
    		else if (BT.leftSubTree == null && BT.rightSubTree == null)
    			return 1;
    		else
    			return countLeaves(BT.leftSubTree) + countLeaves(BT.rightSubTree);
    	}
    
    	public void destroy() {
    		this.root = null;
    		this.leftSubTree = null;
    		this.rightSubTree = null;
    	}
    
    	public void preorderTraversal() {
    		preorderTraversal(this);
    	}
    
    	private void preorderTraversal(BinaryTree BT) {
    		if (BT != null) {
    			process(BT.root);
    			preorderTraversal(BT.leftSubTree);
    			preorderTraversal(BT.rightSubTree);
    		}
    	}
    
    	public void inorderTraversal() {
    		inorderTraversal(this);
    	}
    
    	private void inorderTraversal(BinaryTree BT) {
    		if (BT != null) {
    			inorderTraversal(BT.leftSubTree);
    			process(BT.root);
    			inorderTraversal(BT.rightSubTree);
    		}
    	}
    
    	public void postorderTraversal() {
    		postorderTraversal(this);
    	}
    
    	private void postorderTraversal(BinaryTree BT) {
    		if (BT != null) {
    			postorderTraversal(BT.leftSubTree);
    			postorderTraversal(BT.rightSubTree);
    			process(BT.root);
    		}
    	}
    
    	public void levelorderTraversal() {
    		Queue<BinaryTree> Q = new ArrayBlockingQueue<BinaryTree>(10000);
    		Q.add(this);
    		BinaryTree t;
    		while (Q.size() > 0) {
    			t = Q.remove();
    			process(t.root);
    			if (t.leftSubTree != null)
    				Q.add(t.leftSubTree);
    			if (t.rightSubTree != null)
    				Q.add(t.rightSubTree);
    		}
    	}
    
    	private void process(Integer value) {
    		System.out.print(value + " ");
    	}
    
    }
    main application:
    Java Code:
    public class BinaryTreeApplication {
    	public static BinaryTree BT = new BinaryTree();
    
    	public static void main(String[] args) {
    		insertToBT();
    		outputResults();
    		BT.destroy();
    		System.out.println("\n\nBinary Tree BT is destroyed!\n");
    		outputResults();
    	}
    
    	public static void insertToBT() {
    		int[] inputNumbers = { 50, 17, 76, 9, 23, 54, 14, 19, 72, 12, 67 };
    		for (int i = 0; i < inputNumbers.length; i++)
    			BT.insert(inputNumbers[i]);
    	}
    
    	public static void outputResults() {
    		System.out.println("height: " + BT.getHeight());
    		System.out.println("Is Empty: " + BT.isEmpty());
    		System.out.println("Number of Nodes: " + BT.countNodes());
    		System.out.println("Number of Leaves: " + BT.countLeaves());
    		System.out.print("Preorder Traversal: ");
    		BT.preorderTraversal();
    		System.out.print("\nInorder Traversal: ");
    		BT.inorderTraversal();
    		System.out.print("\nPostorder Traversal: ");
    		BT.postorderTraversal();
    		System.out.print("\nLevelorder Traversal: ");
    		BT.levelorderTraversal();
    	}
    }
    everything works fine except on this condition...

    Java Code:
    private int getHeight(BinaryTree BT) {
    		if (BT == null) {
    			return 0;
    		} else {
    			return 1 + Math.max(getHeight(BT.leftSubTree),
    					getHeight(BT.rightSubTree));
    		}
    	}
    Java Code:
    if(BT == null){...
    it's not supposed to be that way. It should be...

    Java Code:
    if(BT.root == null){...
    but when I replace it with the above syntax, there would be an error...

    Java Code:
    [COLOR="Red"]Exception in thread "main" java.lang.NullPointerException
    	at BinaryTree.getHeight(BinaryTree.java:55)
    	at BinaryTree.getHeight(BinaryTree.java:58)
    	at BinaryTree.getHeight(BinaryTree.java:58)
    	at BinaryTree.getHeight(BinaryTree.java:58)
    	at BinaryTree.getHeight(BinaryTree.java:51)
    	at BinaryTreeApplication.outputResults(BinaryTreeApplication.java:20)
    	at BinaryTreeApplication.main(BinaryTreeApplication.java:7)[/COLOR]
    Can anyone help me debug this problem?! I need to finish this ASAP within this week! Thanks!!

  9. #9
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    URGENT PROBLEM!!!!! Life and Death Situation!!
    You may wish to tone this down a bit as this type of statement often has the opposite effect that you desire since many here bristle over it. True this problem is important to you, but your post is no more important here than anyone elses'. Also, we're all just volunteers here with our own jobs, our own families and our own lives, and most of us do this for the pleasure of helping. Putting pressuring us to help you faster is not going to gain you any fans or get you faster help. Just a little advice.

    Best of luck.
    Last edited by Fubarable; 07-21-2009 at 11:45 PM.

  10. #10
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    Quote Originally Posted by ~ HP9200 ~ View Post
    Java Code:
    if(BT == null){...
    it's not supposed to be that way. It should be...
    Java Code:
    if(BT.root == null){...
    Why do you think it must be this way?

    This method recursively walks up the tree to the end branches trying to find the longest path, and as with any recursive routine, it needs a good ending condition. That ending condition is not when the root is null (you must know which way your recursion is going, and this is heading to the branches, not the root), but when the leaves are null. Thus, I believe that this:
    Java Code:
    if(BT.root == null){...
    is not what you want.

  11. #11
    ~ HP9200 ~ is offline Member
    Join Date
    Jul 2009
    Posts
    5
    Rep Power
    0

    Default

    I am sorry for pressuring...I didn't mean to...Really! Gomenasai!

    Anyways, regarding my problem...

    Java Code:
    private int countLeaves(BinaryTree BT) {
    		if (BT == null)
    			return 0;
    		else if (BT.leftSubTree == null && BT.rightSubTree == null)
    			return 1;
    		else
    			return countLeaves(BT.leftSubTree) + countLeaves(BT.rightSubTree);
    	}
    the code snippet above shows the method of counting the leaves of the binary tree. The problem I faced in here is that when the BinaryTree is empty the condition BT == null will not be achieved and the result number of leaves is 1 which is supposed to be 0. This is also the problem in this snippet where countNodes() will result to 1 instead of 0 in an empty Binary Tree...

    Java Code:
    private int countNodes(BinaryTree BT) {
    		//System.out.println(BT);
    		if (BT == null)
    			return 0;
    		else
    			return 1 + countNodes(BT.leftSubTree) + countNodes(BT.rightSubTree);
    	}
    But I found a solution to this problem which is adding another condition which is BT.root == null...

    Java Code:
    private int countNodes(BinaryTree BT) {
    		//System.out.println(BT);
    		if (BT == null || BT.root == null)
    			return 0;
    		else
    			return 1 + countNodes(BT.leftSubTree) + countNodes(BT.rightSubTree);
    	}
    this code will generate no nullpointerexception error and will yield the correct answer, that is 0 nodes for an empty Binary Tree.

    What I want to ask is why did

    Java Code:
    if(BT.root == null){...
    generate a NullPointerException error while

    Java Code:
    if(BT == null || BT.root == null){...
    doesn't?

    Thanks for your time! And sorry!

    God bless and keep the faith intact!

  12. #12
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    Again, it's because of the direction you're walking along the tree. Again, this recursion goes out to the branches, so the root of the branches will always be non-null. Again, if you don't test that the current node is null, you will not know that you've gone past a leaf.

    The problem I faced in here is that when the BinaryTree is empty the condition BT == null will not be achieved and the result number of leaves is 1 which is supposed to be 0.
    Hm, I'm no binary tree expert, but I would consider the empty tree a leaf and would agree that the leaf count should be 1. Why do you think it should be zero?
    Last edited by Fubarable; 07-22-2009 at 12:25 AM.

  13. #13
    ~ HP9200 ~ is offline Member
    Join Date
    Jul 2009
    Posts
    5
    Rep Power
    0

    Default

    because the root itself is null and does not contain a value...am I right?

    Hmmm...Anyways, so you really need to check the Binary Tree first before checking if the root of that Binary Tree is null? Hehe...First time for me to encounter this one...Another lesson learned...

    Thank you so much and God bless!

    I think this thread is solved

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •