tree algorithm question

[stuckonjava]

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!

[Sierra]

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?

[JosAH]

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

kind regards,

Jos

[stuckonjava]

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

[JosAH]

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

[stuckonjava]

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.

[JosAH]

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

[stuckonjava]

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.

[JosAH]

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