L'évaluation de l'expression des arbres

Skiena du livre de l'Algorithme contient la question suivante:

1) d'Évaluer l'expression donnée en arbre binaire en O(n) le temps, étant donné les n noeuds.

2) Évaluer l'expression que DAG en O(n+m) temps, compte tenu de n nœuds et m arêtes dans le DAG.

L'évaluation de l'expression des arbres

Je pourrais penser à un moyen pour la première question:

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

Puisque nous rendre visite à chaque nœud une fois, il faudra du temps O(n) fois.

Puisque le livre n'a pas de solutions, quelqu'un peut s'il vous plaît dites si c'est correct ?

Aussi n'importe qui peut proposer une solution pour la deuxième question.

Grâce.

OriginalL'auteur Jake | 2012-05-26

  1. 5

    Première méthode semble bien pour moi.

    Pour le groupe, si vous pouvez en modifier l'arbre pour ajouter des valeurs mises en cache pour chaque nœud, vous pouvez utiliser le même algorithme avec un petit tweak pour ne pas répéter si un opérateur nœud a une valeur mise en cache. Cela devrait être O(n+m) temps (au plus une opération arithmétique par nœud et au plus un pointeur de recherche par le bord). Explicitement:

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

    OriginalL'auteur Dougal