Ejemplos de recorrido del árbol anterior/posterior al del mundo real

Question

Entiendo muy bien los algoritmos de cruce de árboles preordenados, en orden y posteriores a la orden. (Reference). Comprendo algunos usos: en orden para recorrer árboles de búsqueda binarios en orden, preordenar para clonar un árbol. Pero no puedo, por mi propia vida, proponer una tarea del mundo real que necesite un recorrido posterior al pedido para lograrlo.

¿Me puede dar un ejemplo? Y: ¿puedes darme mejores usos para el recorrido previo a la orden?

Editar: ¿Alguien me puede dar un ejemplo que no sea árboles de expresión y RPN? ¿Es eso realmente bueno para todos?

Answer 1

Topological sorting es un recorrido post-orden de los árboles (o gráficos acíclicos dirigidos).

La idea es que los nodos del gráfico representan tareas y un borde desde el A a B indica que A tiene que ser realizada antes de B. Un tipo topológico organizará estas tareas en una secuencia tal que todas las dependencias de una tarea aparezcan antes que la tarea misma. Cualquier sistema de compilación como UNIX make tiene que implementar este algoritmo.

El ejemplo que ha mencionado Darío, que destruye todos los nodos de un árbol con gestión manual de memoria, es una instancia de este problema. Después de todo, la tarea de destruir un nodo depende de la destrucción de sus hijos.

Answer 2

El pedido de los ejemplares es (puede ser) utilizado por los compiladores. Considere un árbol de expresiones para a + b + c, el lenguaje de máquina requeriría una secuencia como a b + c +. Esto también se llama Reverse polish Notation (RPN). En la página de la Wikipedia dice: "RPN también conocido como Postfix"

El pedido posterior también es necesario para destruir un árbol, al igual que se necesita un pedido previo para crearlo/clonarlo.

Answer 3

Como señaló Henk Holterman, la destrucción de un árbol mediante el uso de la gestión manual de la memoria suele ser un recorrido posterior a la orden.

Pseudocódigo:

destroy(node) { 
    if (node == null) return; 

    destroy(node.left) 
    destroy(node.right) 

    // Post-order freeing of current node 
    free(node) 
}