03/29/2008, 04:01 PM

bo198214 Wrote:[...]I've not thought about that... but I assume it must be possible since the algorithm obviously can be expressed as a Turing machine, so it must be recursive. I'm not sure how exactly to go about deriving a recursive definition for it, though.

Just skimmed through your article and asking myself how this function can be expressed with a recursive definition ...

Maybe one way is to perform a depth-first traversal on the tree, left child first, and recursively linearize the left-most children. So, in computer pseudocode, it could be something like this:

Code:

`linearize(T,m) {`

if (is_rightbranching_chain(T.left_subtree) and

is_rightbranching_chain(T.right_subtree))

{

... (perform the transformation... not sure how to express this recursively yet)

} else {

T.left_subtree = linearize(T.left_subtree, m);

T.right_subtree = linearize(T.right_subtree, m);

return T;

}

}

Once we work out the pseudocode, maybe there's a way to factor it into a recursive function...?