8

所以我有一个二叉树和一个后缀表达式“6 2 * 3 /”将它放在树中的算法是什么?像,

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

2 回答 2

18

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

算法:有一个堆栈来存储中间值(即树),并从左到右检查每个标记:

  • 如果是数字,则将其转为叶子节点并压入堆栈。
  • 如果是运算符,则从堆栈中弹出两个项目,用这些子节点构造一个运算符节点,并将新节点压入堆栈。

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

于 2011-12-04T19:46:39.587 回答
0
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)
}
于 2019-01-18T17:29:53.440 回答