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 7 of 7

Thread: Java Binary Tree (Beginners)?

  1. #1
    Junior Member
    Join Date
    Jun 2011
    Posts
    21
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Java Binary Tree (Beginners)?

    I'm suppose to add up all the number that are in a node of a binary tree.

    Is this correct???

    This is just the algorithm:::

    static int weight(BinaryTree t, Node v)
    if t.size == 0 then //if BinaryTree t is an empty tree
    return 0
    else
     
    if t.hasLeft(v) then /** if Node v of BinaryTree t doesn't have a left children, it means Node v is an external node. */
    return v.element
    else
    return weight(t, t.left(v)) + weight(t, t.right(v))


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Java Binary Tree (Beginners)?

    if t.hasLeft(v) then /** if Node v of BinaryTree t doesn't have a left children, it means Node v is an external node. */
    return v.element
    else
    return weight(t, t.left(v)) + weight(t, t.right(v))
    It looks like you're assuming that if a node doesn't have a left child, it must not have a right child. That assumption is not necessarily true for binary trees.

    I would suggest implementing a true in-order traversal:

    1. Check to see if there's a left child. If there is, get the weight of the left child. Set the calculated weight of this node to that value. Otherwise, set the calculated weight of this node to zero.
    2. Add the value of the current node to the calculated weight of this node.
    3. Check to see if there's a right child. If there is, add the weight of the right child to the calculated weight of this node.
    4. return the calculated weight.

  3. The Following User Says Thank You to helloworld922 For This Useful Post:

    IAmHere (June 18th, 2011)

  4. #3
    Junior Member
    Join Date
    Jun 2011
    Posts
    21
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Java Binary Tree (Beginners)?

    Quote Originally Posted by helloworld922 View Post
    I would suggest implementing a true in-order traversal:

    1. Check to see if there's a left child. If there is, get the weight of the left child. Set the calculated weight of this node to that value. Otherwise, set the calculated weight of this node to zero.
    2. Add the value of the current node to the calculated weight of this node.
    3. Check to see if there's a right child. If there is, add the weight of the right child to the calculated weight of this node.
    4. return the calculated weight.

    I was about to do it your way, but I notice that in my book, there's no method t.hasRight(v) and t.right(v) . It only checks for the left children.
    So, I guess I have to stick to my original code.

    Is my code on my first post correct?

    Thank you for your help.

  5. #4
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Java Binary Tree (Beginners)?

    Only if the assumption I said holds. Actually, the assumption you're making is:

    If and only if node v has a left child, then there must be a right child.

    I can think of several scenarios where this is not true.

    Consider the tree with 2 elements:

    1 2

    There is no possible way the above assumption could be true, since one of these elements must be the root node, and the other must be either the left child or the right child, but not both.

    I would suggest thoroughly reading your book to make sure that this kind of scenario will not happen. If this scenario can happen, then your book is wrong (don't worry, it happens). In the real world, I can tell you that this assumption is almost always a bad assumption.

  6. The Following User Says Thank You to helloworld922 For This Useful Post:

    IAmHere (June 18th, 2011)

  7. #5
    Junior Member
    Join Date
    Jun 2011
    Posts
    21
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Red face Re: Java Binary Tree (Beginners)?

    Quote Originally Posted by helloworld922 View Post
    Only if the assumption I said holds. Actually, the assumption you're making is:
    .........
    I think you're right.

    So, I changed my code so that the base case meets your requirement.
    So my code right???


    // returns the weight of node v
    static int weight(BinaryTree t, Node v)
    	if t.size == 0 then 	// base case: if BinaryTree t is an empty tree
    		return 0
    	else
     
    	if not(t.hasLeft(v) or t.hasRight(v)) then 	// base case: if Node v has no left child and right child, it means Node v is an external node. 
    		return v.element
    	else
    		return weight(t, t.left(v)) + weight(t, t.right(v))

    So my code right???

  8. #6
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Java Binary Tree (Beginners)?

    mmm, not quite.

    Now you're making the assumption that the node must either not have any children, or it must have both a left and right child.

    You must check for each child individually and add the weight from each node separately. The pseudo-code I provided is basically a line-by-line of what the code should do.

  9. The Following User Says Thank You to helloworld922 For This Useful Post:

    IAmHere (June 19th, 2011)

  10. #7
    Junior Member
    Join Date
    Jun 2011
    Posts
    21
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Java Binary Tree (Beginners)?

    if t.hasALeft(v) then
        {
            left = t.left(v)
        }
     
        return weight(t, left) + weight(t, right)    
     
        if t.hasARight(v) then
        {
            right = t.Right(v)
        }

    Would this be right?
    It look right to me.

Similar Threads

  1. Java Binary Tree
    By comwizzz in forum What's Wrong With My Code?
    Replies: 2
    Last Post: February 28th, 2011, 02:15 PM
  2. Binary Search Tree in Java [HELP]
    By alan in forum Algorithms & Recursion
    Replies: 2
    Last Post: February 5th, 2011, 05:44 AM
  3. Binary Search Tree
    By lex25288 in forum Algorithms & Recursion
    Replies: 3
    Last Post: January 19th, 2011, 08:10 AM
  4. need help with binary tree
    By vash0047 in forum Java Theory & Questions
    Replies: 5
    Last Post: July 12th, 2010, 08:23 AM
  5. Data Structures(Binary Search Tree to AVL Tree)ASAP
    By jfAdik in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 5th, 2010, 03:58 AM