Utiliser le parcours en pré-ordre avec la notation polonaise
Les arbres d'expression sont un type d'arbre binaire qui représentent des expressions arithmétiques :
En appliquant un parcours en ordre à un arbre d'expression, vous obtenez la notation infixée. Pour l'arbre donné, cette notation est (10-5)*3.
En appliquant un parcours en pré-ordre à un arbre d'expression, vous obtenez la notation préfixée, aussi appelée notation polonaise, où l'opérateur apparaît avant ses opérandes. Pour l'arbre donné, cette notation est *-10 5 3.
En appliquant un parcours en post-ordre à un arbre d'expression, vous obtenez la notation postfixée, aussi appelée notation polonaise inversée, où l'opérateur apparaît après ses opérandes. Pour l'arbre donné, cette notation est 10 5- 3*.
Codez le parcours en pré-ordre afin d'obtenir la notation préfixée de cet arbre d'expression.
Cet exercice fait partie du cours
<cours>Structures de données et algorithmes en Python</cours>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)