表达式树问题

Question

我正在手工绘制表达式树，我总是遇到一个我不理解的问题。

我对表达式树的理解可能是错误的，即您选择一个根，创建树，然后如果您按顺序、按顺序或后顺序遍历树，这就是您将获得的相应-fix表达式。

所以如果我有..。

中缀：A + B + C - D

前缀表达式将如下所示：-++ABCD

后缀表达式将如下所示：AB+C+D-

我的树是这样的..。

                       +
                     /   \
                   +       -
                 /   \   /   \
                A     B C     D

现在，我假设您选择了看起来最明显的根，并相应地创建了树，因此我选择了中间的+操作符。当我按顺序遍历树时，它会产生正确的表达式。然而，当我按预序遍历时，答案是：++AB-CD，这是不正确的。后缀也是不正确的，在后序中遍历树时，答案是AB+CD-+。

我犯了什么错误？

这是我选择的根吗？我从根及其后续子项创建子对象的方法？或者，后缀和前缀表达式不能总是使用中缀表达式树找到？

Answer 1

您不能只选择一个根。

如果您认为运算符是left-associative，就像通常对算术表达式所做的那样，那么A + B + C - D等同于((A + B) + C) - D。这表明根是-，正确的树是：

      -
     / \
    +   D
   / \
  +   C
 / \
A   B

遍历此树将给出正确的前缀和后缀表达式。

现在，整数加法是关联的，所以((A + B) + C) - D会给出与(A + B) + (C - D)相同的结果，但它不是同一个表达式。这可能就是让你困惑的地方。