Results 1 to 9 of 9
  1. #1
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default tree algorithm question

    Can someone talk me through this please:

    Algorithm: printExpression(Tree T, Position v)
    if T.isInternal(v) then
    print (
    if T.hasLeft(v) then
    printExpression(T, T.left(v))
    if T.isInternal(v) then
    print the operator stored at v
    else
    print the value stored at v
    if T.hasRight(v) then
    printExpression(T, T.right(v))
    if T.isInternal(v) then
    print )



    I am finding it extremely confusing, for eg a tree of:

    _
    + /
    5 6 6 2


    Thanks so much!

  2. #2
    Sierra is offline AN21XX
    Join Date
    Mar 2012
    Location
    Munich
    Posts
    297
    Rep Power
    3

    Default Re: tree algorithm question

    This is not Java and you do not use the forum code brackets... and you do not name a problem. I guess you need to talk yourself through this, code it in java and then come back if you have a problem, right?
    I like likes!

  3. #3
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,365
    Blog Entries
    7
    Rep Power
    20

    Default Re: tree algorithm question

    That recursive algorithm prints an infix representation of a tree; your example prints as ((5+6)-(6/2)).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  4. #4
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default Re: tree algorithm question

    Quote Originally Posted by JosAH View Post
    That recursive algorithm prints an infix representation of a tree; your example prints as ((5+6)-(6/2)).

    kind regards,

    Jos
    Could you explain how this happens? I don't understand how it works

  5. #5
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,365
    Blog Entries
    7
    Rep Power
    20

    Default Re: tree algorithm question

    Follow the algorithm line by line; the first node is an internal node (it's the - node) so a ( is printed followed by (recursively) printing the left sub node; that prints (5+6); because the current node is an internal node its operator is printed (the minus sign) followed by (recursively) printing the right sub node; that prints (6/2) and finally a right parenthesis is printed; that makes ((5+6)-(6/2)).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  6. #6
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default Re: tree algorithm question

    Quote Originally Posted by JosAH View Post
    Follow the algorithm line by line; the first node is an internal node (it's the - node) so a ( is printed followed by (recursively) printing the left sub node; that prints (5+6); because the current node is an internal node its operator is printed (the minus sign) followed by (recursively) printing the right sub node; that prints (6/2) and finally a right parenthesis is printed; that makes ((5+6)-(6/2)).

    kind regards,

    Jos
    Thanks very much for the detailed response.
    But I am still confused, this is what i get from the algorithm,

    first at - is an internal node the ( is printed.
    next we recursively call (T, T.left(v)). // where T.left(v) is the +

    Now what confuses me here do I carry on with the rest of the if statements ?

    Because this is the way im doing it and getting lost:

    This means another ( is printed so so far we have ((.

    then I call the method again (T, T.left(v)) // where T.left(v) is the 5.



    as this node is not internal we print 5. Now i have ((5.

    But now I'm confused on what happens next, could you tell me where I'm going wrong please.

    Much appreciated and thanks for your time.

  7. #7
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,365
    Blog Entries
    7
    Rep Power
    20

    Default Re: tree algorithm question

    That's what recursion is all about, i.e you don't continue with the next line until you have finished the curent code line completely; if you 'dive' down in the recursion, you have to finish it completey before you can 'pop' up again and continue where you left of. After ((5 has been printed you continue printing the nodes' data item (which is a + and you 'dive' down again in the next line of the (recursive) algorithm. For convenience, jot down where you dived down so when you're ready to pop up, check what you've written down so you know where to continue.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  8. #8
    stuckonjava is offline Senior Member
    Join Date
    Jan 2012
    Posts
    151
    Rep Power
    3

    Default Re: tree algorithm question

    Quote Originally Posted by JosAH View Post
    That's what recursion is all about, i.e you don't continue with the next line until you have finished the curent code line completely; if you 'dive' down in the recursion, you have to finish it completey before you can 'pop' up again and continue where you left of. After ((5 has been printed you continue printing the nodes' data item (which is a + and you 'dive' down again in the next line of the (recursive) algorithm. For convenience, jot down where you dived down so when you're ready to pop up, check what you've written down so you know where to continue.

    kind regards,

    Jos
    Hi Jos, Thanks so much for clearing this up for me. Genuinely appreciated.

  9. #9
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,365
    Blog Entries
    7
    Rep Power
    20

    Default Re: tree algorithm question

    Quote Originally Posted by stuckonjava View Post
    Hi Jos, Thanks so much for clearing this up for me. Genuinely appreciated.
    I'm glad you're understanding it now; once you fully understand the elegance of recursion you'll appreciate it; e.g. tree data structures almost beg for recursion.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Huffman coding algorithm question?
    By knguye88 in forum New To Java
    Replies: 1
    Last Post: 03-12-2012, 09:06 AM
  2. Tree Set question
    By Adomini in forum New To Java
    Replies: 5
    Last Post: 02-14-2011, 12:12 AM
  3. Replies: 10
    Last Post: 08-27-2010, 03:31 AM
  4. build search tree on minimax algorithm...
    By me26 in forum Java Gaming
    Replies: 2
    Last Post: 06-29-2010, 08:24 AM
  5. Alpha-beta algorithm, game tree
    By ljaf_1985 in forum New To Java
    Replies: 0
    Last Post: 03-28-2008, 04:21 PM

Posting Permissions

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