1. Apprendre
    2. /
  2. Cours
    3. /
  3. Structures de données et algorithmes en Python
Connected

Exercice

Utiliser le parcours en pré-ordre avec la notation polonaise

Les arbres d'expressions sont un type d'arbre binaire qui représentent des expressions arithmétiques :

Graphical representation of a binary tree that has arithmetic expressions.

En appliquant un parcours in-order (infixe) à un arbre d'expressions, vous obtenez la notation infixe. Pour l'arbre ci-dessus, cette notation est (10-5)*3.

En appliquant un parcours pre-order (pré-ordre) à un arbre d'expressions, vous obtenez la notation préfixe, aussi appelée notation polonaise, où l'opérateur précède ses opérandes. Pour l'arbre ci-dessus, cette notation est *-10 5 3.

En appliquant un parcours post-order (post-ordre) à un arbre d'expressions, vous obtenez la notation postfixe, aussi appelée notation polonaise inversée, où l'opérateur suit ses opérandes. Pour l'arbre ci-dessus, cette notation est 10 5- 3*.

Programmez le parcours en pré-ordre afin d'obtenir la notation préfixe de cet arbre d'expressions.

Instructions

100 XP
  • Vérifiez si current_node existe.
  • Affichez la valeur de current_node.
  • Appelez récursivement la fonction pre_order() sur les sous-arbres appropriés.