如何将后缀表达式放入二叉树中？

Question

我有一个二叉树和一个后缀表达式 "6 2 * 3 /"，如何将其放入树中？

算法是什么？

          [/]
          / \
        [*]  [3]
        / \
      [6] [2]

- Mudasir Soomro

---

您尝试了什么？一个递归下降函数吗？ - Basile Starynkevitch

如果这是作业，请注明。 - H H

反转，即将其转换为前缀吗？是的，这就是我想到的，也就是说，在反转后，创建第一个运算符的节点，然后将下一个操作数/运算符作为其左节点，再将其右边的节点作为其右节点！以此类推... - Mudasir Soomro

如果您需要正向处理，则可以使用堆栈。 - BLUEPIXY

阿汉，我用了栈，它正常工作。 - Mudasir Soomro

为什么？你已经有后缀表达式了，而且你只需要一个栈。你不需要一棵树。不清楚你在问什么。 - user207421

Answer 1

构建表达式的树形结构，可以像直接计算数字一样来构造树形结构。这个技巧不仅在后缀表达式中有用，而且在许多其他情况下也非常实用。

算法: 使用一个栈来存储中间值(即树)，从左到右检查每个标记：

• 如果它是一个数字，则将其转换为叶节点并将其推入栈中。
• 如果它是运算符，则从栈中弹出两个元素，使用这些子节点构造运算符节点，并将新节点推入栈中。

最后，如果表达式格式正确，则您应该在栈上恰好有一棵表示整个表达式的树形结构。

- Kevin Reid

Answer 2

Postfix-to-tree(j){
  n <--ALLOCATE_NODE(A[j],NULL,NULL)
    Switch
      case Postfix[j] is a binary operator
        do j <--j-1
         right[n] <-- Postfix-to-tree(j)
              j <-- j-1
              left[n] <--postfix-to-tree(j)
                 case postfix[j] is a unary operator 
               do j <-- j-1
                  right[n] <-- Postfix-to-tree(j)
}

- Naghme246