Question

Skiena Skiena的《算法书》载有如下问题:

(1) 评价在O(n) 时间给定的二进制树表达式, 给定 n节点。

2) 评价O(n+m) 时间、给定的 n 节点和 m 边缘在 DAG 中作为 DAG 表达式的表达式。

""https://i.sstatic.net/vjOjF.jpg" alt="在这里输入图像描述"/ >

我可以想出办法解决第一个问题:

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)时间。

既然这本书没有解决办法, 任何人都能知道这是否正确吗?

任何人也可以建议解决第二个问题。

谢谢

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

友情链接