Preorder to Postorder
I am making another thread but at the moment i am very much bogged down due to unavailality of algorithms in my books....
Let T be a tree in which every non leaf node has two children and we have to convert the preoder listing of T into post order listing..
I can think that first element will be root and and subtracting that the two halfs will give left and right subtree and it has to be done recursively..
But please can you write it into a form of Pseudo Algorithm...I will be highly grateful to you
problem can not be solved without more information.
Here is a tree in pre order
a b c d e
What is the post order?
unless you can tell the difference between leaves and internal nodes and the arity of any of those internal nodes you can't solve the problem.
For example had the pree order tree been
+ a * b c
you might have guessed that the post order would be
a b c * +
but that is because you guessed that a, b & c are leaves (of arity 0) and the operaters are internal nodes of arity 2.
On the other hand, if you can tell all those things, just read in the string and build the tree, then output the tree you just read in post order.
How do you read a tree in pre-order? Take the algorithm for writing in pre-order and change the recursive routine name "writePreOrder" to "readPreOrderOfKnownArity" change the writes to reads and recurse to readPreOrderOfKnownArity whenever you read an internal node and once you know its arity.
