Algorithm for converting Binary tree to post-fix mathematical expression?

Tag: algorithm Author: zouxiujie Date: 2009-08-11

I have a Binary tree for a mathematical expression(infix), i want to convert directly this TREE to a postfix(Stack) can any body suggest the algorithm?

Best Answer

What you’re searching for is known as post-order tree traversal:

postorder(node)
  if node.left  ? null then postorder(node.left)
  if node.right ? null then postorder(node.right)
  print node.value

comments:

thanx Konrad Rudolph,for clearing the exact terminology.

Other Answer1

Easy, each node is (Left, Right, Data).

Start with the first node. execute the algorithm for the left subtree if available and then execute the algorithm for the right subtree and then print the data.

TreeNode = ([TreeNode], Data, [TreeNode])

TreeToPostfix: [TreeNode] -> Data*
TreeToPostfix(nil) = []
TreeToPostfix((left, data, right)) ==
  TreeToPostfix(left) ++ TreeToPostfix(right) ++ Data

For example:

              +
            /   \
           *     -
          / \   / \
         2   3 4   5

Produces: 2 3 * 4 5 - +

comments:

can u plz explain the approach as data will always be at lowset level of tree
Data in this case is both value and operator. My algorithm prduced prefix, but is now fixed to postfix.
thanx Gamecat For the help..