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 :
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.
Cette activité fait partie du cours
Structures de données et algorithmes en Python
Instructions de l’exercice
- Vérifiez si
current_nodeexiste. - Affichez la valeur de
current_node. - Appelez récursivement la fonction
pre_order()sur les sous-arbres appropriés.
Exercice interactif pratique
Essayez cet exercice en complétant ce code d’exemple.
import queue
class ExpressionTree:
def __init__(self):
self.root = None
def pre_order(self, current_node):
# Check if current_node exists
____:
# Print the value of the current_node
____
# Call pre_order recursively on the appropriate half of the tree
____
____
et = CreateExpressionTree()
et.pre_order(et.root)