如何在二叉树中放置后缀表达式

Question

所以我有一个二叉树和一个后缀表达式"6 2 * 3/"把它放到树里的算法是什么?如,

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

Answer 1

要从表达式构造树，假设您正在直接求值，但是构造树而不是计算数字。(这个技巧适用于比后缀表达式更多的东西。)

算法:有一个堆栈来存储中间值(它们是树)，并从左到右检查每个令牌:

• 如果它是一个数字，把它变成一个叶子节点，并把它推到堆栈上。
• 如果是一个操作符，从堆栈中弹出两个项目，用这些子节点构造一个操作符节点，并将新节点推入堆栈。

最后，如果表达式格式正确，那么堆栈上应该只有一个树，这是树形式的整个表达式。

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)
}