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...?