Binary trees, construct a tree based on preorder

constructing a tree given it's inorder is easy enough. But, let's say you are supposed to construct a tree based on it's preorder (+ + y z + * x y z for example).

It's开发者_运维百科 easy to see that + is the root, and how to continue in the left subtree from there. But.. how do you know when you are supposed to "switch" to the right subtree?

Usually, inorder is considered the difficult case.

For preorder, you'll just have a grammar like this.

expr ::= operator expr expr | var

An operator is followed by exactly two well-formed expressions. This can be parsed easily using recursion

If you parse a tree and get a variable, return the variable. If you parse a tree and get an operator, parse the two following trees as right/left subtrees.