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.