Utilidad del recorrido anterior y posterior de los árboles binarios

Question

Utilidad del recorrido anterior y posterior de los árboles binarios

#1 de Mike Dunlavey (12 votos)
#2 de Karl Bielefeldt (11 votos)
#3 de Kilian Foth (5 votos)

13

Esto puede ser muy ingenuo, pero me preguntaba, el contexto de los árboles binarios (lisos, ordenados y equilibrados), de todos los tipos de recorrido:

pre-orden de profundidad primero
profundidad primero en orden
orden posterior de profundidad
amplitud primero

¿cuál es la utilidad real de los pre y post-order? Quiero decir, ¿hay algún tipo y / o configuración de árbol binario en el que el recorrido previo y / o posterior al pedido daría una (alguna) ventaja (s) sobre los otros dos?

AFAICS, hay ciertos tipos y configuraciones de árboles binarios para los cuales, en orden y amplitud, podrían dar cierta ventaja:

para un árbol binario equilibrado, cualquier recorrido primero en profundidad utilizará menos espacio de almacenamiento de memoria en comparación con el ancho primero (por ejemplo, para un árbol binario equilibrado de 6 o 7 nodos, la altura es 2, por lo que cualquier recorrido primero en profundidad es necesario almacenar un máximo de 2 nodos en un momento dado, mientras que el último nivel tiene 3 o 4 nodos, por lo que el recorrido transversal más amplio deberá almacenar hasta 3 o 4 nodos en algún punto). En este caso, el uso del recorrido en orden utiliza la menor cantidad de memoria y visita los nodos en su orden natural.
para un árbol binario no balanceado, si está cerca del escenario de inserción en el peor de los casos, atravesarlo primero en amplitud usaría menos memoria en comparación con cualquiera de los recorridos en profundidad primero. Así que en este caso la amplitud ofrece una ventaja. El recorrido en orden tiene nuevamente la ventaja de visitar los valores en su orden natural.

Sin embargo, no puedo pensar en una situación en la que el pre y post-recorrido daría una ventaja sobre los otros dos.

graph-traversal binary-tree

pregunta Shivan Dragon 11.02.2013 - 14:49

3 respuestas

Lea otras preguntas en las etiquetas graph-traversal binary-tree

¿Qué es la "lógica de presentación" y cuánto es aceptable en las vistas? ¿Cómo puedo probar mi propio algoritmo de cifrado?

score 12 · Answer 1

Debe hacer varias cosas con árboles, como la traducción entre la estructura de datos y alguna representación en serie, como en un archivo o en un idioma.

Por ejemplo, supongamos que tienes un árbol de análisis como este:

    *
   / \
  +   \
 / \   \
A   B   C

Se podría serializar como * + A B C recorriéndolo en orden prefijo, o como A B + C * recorriéndolo en orden postfix. Si trabajas con procesadores de lenguaje, estas cosas deben ser de segunda naturaleza.

score 11 · Answer 2

El artículo de wikipedia tiene una buena descripción concisa de cuándo querría usar los diferentes tipos de profundidad. primera búsqueda:

El recorrido previo de la orden mientras se duplican los nodos y los valores puede hacer un duplicado completo de un árbol binario. También se puede usar para hacer una expresión de prefijo (notación polaca) a partir de árboles de expresiones: recorrer el árbol de expresiones en orden.
El recorrido en orden se usa muy comúnmente en los árboles de búsqueda binarios porque devuelve valores del conjunto subyacente en orden, de acuerdo con el comparador que configuró el árbol de búsqueda binario (de ahí el nombre).
El recorrido de la orden posterior al eliminar o liberar nodos y valores puede eliminar o liberar un árbol binario completo. También puede generar una representación postfix de un árbol binario.

Se reduce a las necesidades logísticas de un algoritmo. Por ejemplo, si no utiliza el recorrido posterior al pedido durante la eliminación, perderá las referencias que necesita para eliminar los árboles secundarios.

score 5 · Answer 3

El punto de tener diferentes algoritmos para tratar con árboles binarios no es hacer cosas con árboles. En este nivel abstracto, una orden es en gran medida tan buena como cualquier otra, ya que solo obtiene símbolos abstractos fuera del procedimiento.

Pero los árboles se utilizan normalmente para representar cosas interesantes, y eso puede hacer una gran diferencia en el resultado. Por ejemplo, si los nodos representan estados de búsqueda en una búsqueda completa a través de un dominio grande (tal vez incluso un dominio infinito), el primero y el procesamiento descendentes primero no solo determinan en qué orden se encuentran los resultados, sino que también puede determinar si Alguna vez encontrarás soluciones . El punto es más fácil de ver con dominios infinitos: si desciende de manera imprudente, podría pasar por alto una solución que se encuentra bastante arriba en el árbol, simplemente porque tomó un giro equivocado. Pero en la práctica, como la memoria y los discos también son finitos, esto se aplica incluso a dominios que son simplemente muy grandes en lugar de realmente infinitos.