是否可以构建一个后缀或前缀形式的树？

Question

让我有一些表达为2*3/(2-1) +5*(4-1)。它是中缀符号。当然，我可以为这个表达式构造一棵你可以在图像上看到的树。 enter image description here

那么，我们把这个表达式写成后缀和前缀的形式。后缀：2 3 * 2 1 - / 5 4 1 - * + 前缀：+ / * 2 3 - 2 1 * 5 - 4 1

问题是：以上表达式的树是否相同？如果没有，如何构建？

Answer 1

And the question is: a tree for above expressions will be the same?

是的，这是同一棵树 -- 不同的符号表示相同的计算。

表达式的不同写法正好对应同一棵树的不同traversals：

预购前缀符号

(预购: F, B, A, D, C, E, G, I, H)

有序中缀表示法

（按顺序：A、B、C、D、E、F、G、H、I）

post-order for postfix notation

(post-顺序：A、C、E、D、B、H、I、G、F)

Answer 2

这是从前缀表示构造树的粗略草图（将前缀表示法视为数字和运算符的流）：

preocedure buildTree(prefix):
    c := first item of prefix
    if c is a number then
        return a tree node containing the number
    else
        create a tree node t with c (an operator in this case)
        t.left := buildTree(rest of prefix)
        t.right := buildTree(rest of prefix)
        return t

您应该使用树的前缀表示来调用此方法。该方法将从中递归构建子树。

您也可以编写类似的方法从后缀表示构建树。您需要调整此算法以从右端开始并首先构建右子树。

Answer 3

有很多关于如何构建表达式树的资源。 wiki这里有很好的参考。

这个想法是，当你遍历每个字符时，例如，后缀表达式。

如果该字符是一个操作数，则将其压入堆栈
如果角色是一个运算符，那么你从栈中弹出两个元素，使它们成为当前运算符的子元素，然后将运算符压入栈中。

循环终止后，您将在堆栈中得到一个元素作为树的根。

是否可以构建一个后缀或前缀形式的树？

Is it possible to construct a tree of postfix or prefix form?

algorithm

tree

prefix

postfix-notation