二叉树，基于前序构建树

Question

构造一棵树，因为它的中序非常简单。 但是，假设您应该基于它的预先构建树（例如+ + y z + * x y z）。

很容易看出，+是根，以及如何从那里继续左子树。 但是..你怎么知道什么时候你应该“切换”到正确的子树？

Answer 1

通常情况下，inorder被认为是困难的情况。

对于预购，你只需要这样的语法。

expr ::= operator expr expr | var 

操作者后跟正好两个合式表达式。这可以很容易地使用递归来解析

如果您解析树并获取变量，则返回该变量。 如果你解析一棵树并得到一个操作符，解析后面的两棵树为右/左子树。