评估表达式树

Question

Skiena的算法书包含以下问题：

1）在给定n个节点的情况下，以O(n)时间计算二叉树中的表达式。

2）在给定DAG中的n个节点和m条边的情况下，以O（n+m）时间计算表达式。

我可以想到一种解决第一个问题的方法：

evaluate(node) {
     if(node has children){
          left_val = evaluate(node->left);
          right_val = evaluate(node->right);

          // find operation symbol for node and use it as
          // val = left_val operation right_val

          return val;
     }
     else {
          return node_value;
     }
}

由于我们只访问每个节点一次，所以需要O(n)的时间。

由于这本书没有解决方案，有人能否告诉我这是否正确？

同时，有人能为第二个问题提供一个解决方案吗？

谢谢。

- Jake

Answer 1

第一种方法对我来说看起来不错。

对于DAG，如果您可以修改树以向每个节点添加缓存值，则可以使用相同的算法进行微小调整，以使操作节点具有缓存值时不会递归。这应该是O（n+m）时间（每个节点最多一个算术运算符和每条边最多一个指针查找）。明确地说：

evaluate(node) {
     if (node has value) {
          return node->value;
     } else {
          left = evaluate(node->left);
          right = evaluate(node->right);

          // find operation symbol for node and use it as
          // val = left_val operation right_val

          node->value = val;
          return val;
     }
}

- Danica