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

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

问题是：以上表达式的树会是相同的？

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

---

的不同的方式来写的表达对应正好相同的树的不同traversals：用于前缀符号

• 预购（预购：F，B，A，D，C，E，G，I，H）
  • 有序对缀表示法

  

  （有序：A，B，C，d，E，F，G，H，I）

  为后缀符号
  • 后为了

  

  （后序：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这里有一个很好的参考。

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

• 如果字符是一个操作数，然后你把它压入堆栈

• 如果字符是一个运营商，那么你弹出从栈两个元素，使它们成为当前运营商的童装，然后将操作员推入堆栈。

循环终止后，最终将以堆栈中的单个元素作为树的根。