Uso del recorrido en preorden con notación polaca
Los árboles de expresiones son un tipo de árbol binario que representa expresiones aritméticas:
Aplicando el recorrido en orden a un árbol de expresión, puedes obtener la notación de infijo. Esta notación para el árbol dado será (10-5)*3.
Aplicando el recorrido en preorden a un árbol de expresión, puedes obtener la notación de prefijo, también conocida como notación polaca, en la que el operador aparece antes que sus operandos. Esta notación para el árbol dado será *-10 5 3.
Aplicando el recorrido en orden posterior a un árbol de expresión, puedes obtener la notación de postfijo, también conocida como notación polaca inversa, en la que el operador aparece después de sus operandos. Esta notación para el árbol dado será 10 5- 3*.
Programa el recorrido en preorden para que puedas obtener la notación de prefijo de este árbol de expresión.
Este ejercicio forma parte del curso
Estructuras de datos y algoritmos en Python
Instrucciones de ejercicio
- Comprueba si existe
current_node. - Imprime el valor de
current_node. - Llama a la función
pre_order()recursivamente en las mitades apropiadas del árbol.
Ejercicio interactivo práctico
Pruebe este ejercicio completando este código de muestra.
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)