Results 1 to 9 of 9
Thread: tree algorithm question
 05062012, 08:41 AM #1Senior Member
 Join Date
 Jan 2012
 Posts
 151
 Rep Power
 3
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!
 05062012, 11:04 AM #2AN21XX
 Join Date
 Mar 2012
 Location
 Munich
 Posts
 297
 Rep Power
 3
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!
 05062012, 02:22 PM #3
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,762
 Blog Entries
 7
 Rep Power
 21
Re: tree algorithm question
That recursive algorithm prints an infix representation of a tree; your example prints as ((5+6)(6/2)).
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
 05062012, 03:55 PM #4Senior Member
 Join Date
 Jan 2012
 Posts
 151
 Rep Power
 3
 05062012, 04:40 PM #5
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,762
 Blog Entries
 7
 Rep Power
 21
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,
Joscenosillicaphobia: the fear for an empty beer glass
 05062012, 06:26 PM #6Senior Member
 Join Date
 Jan 2012
 Posts
 151
 Rep Power
 3
Re: tree algorithm question
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.
 05062012, 07:41 PM #7
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,762
 Blog Entries
 7
 Rep Power
 21
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,
Joscenosillicaphobia: the fear for an empty beer glass
 05062012, 10:26 PM #8Senior Member
 Join Date
 Jan 2012
 Posts
 151
 Rep Power
 3
 05062012, 10:41 PM #9
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,762
 Blog Entries
 7
 Rep Power
 21
Similar Threads

Huffman coding algorithm question?
By knguye88 in forum New To JavaReplies: 1Last Post: 03122012, 10:06 AM 
Tree Set question
By Adomini in forum New To JavaReplies: 5Last Post: 02142011, 01:12 AM 
New java student, question about algorithm, please help :)
By siick in forum New To JavaReplies: 10Last Post: 08272010, 04:31 AM 
build search tree on minimax algorithm...
By me26 in forum Java GamingReplies: 2Last Post: 06292010, 09:24 AM 
Alphabeta algorithm, game tree
By ljaf_1985 in forum New To JavaReplies: 0Last Post: 03282008, 05:21 PM
Bookmarks