Cuándo utilizar las estrategias de recorrido de árbol de búsqueda binaria de preorden, posorden y orden

97

Recientemente me di cuenta de que, si bien había usado mucho BST en mi vida, nunca había contemplado usar nada más que el recorrido Inorder (aunque soy consciente y sé lo fácil que es adaptar un programa para usar el recorrido previo / posterior al pedido).

Al darme cuenta de esto, saqué algunos de mis viejos libros de texto sobre estructuras de datos y busqué el razonamiento detrás de la utilidad de los recorridos previos y posteriores al pedido; sin embargo, no dijeron mucho.

¿Cuáles son algunos ejemplos de cuándo usar preorder / postorder en la práctica? ¿Cuándo tiene más sentido que en orden?

John Humphreys - w00te
fuente

Respuestas:

135

Cuándo utilizar la estrategia transversal de pedido anticipado, en pedido y posterior al pedido

Antes de que pueda comprender en qué circunstancias utilizar el pedido anticipado, en orden y el pedido posterior para un árbol binario, debe comprender exactamente cómo funciona cada estrategia transversal. Utilice el siguiente árbol como ejemplo.

La raíz del árbol es 7 , el nodo más a la izquierda es 0 , el nodo más a la derecha es 10 .

ingrese la descripción de la imagen aquí

Recorrido de reserva :

Resumen: comienza en la raíz ( 7 ), termina en el nodo más a la derecha ( 10 )

Secuencia transversal: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Recorrido en orden :

Resumen: comienza en el nodo más a la izquierda ( 0 ), termina en el nodo más a la derecha ( 10 )

Secuencia transversal: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Recorrido posterior al pedido :

Resumen: comienza con el nodo más a la izquierda ( 0 ), termina con la raíz ( 7 )

Secuencia transversal: 0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

¿Cuándo usar el pedido anticipado, el pedido en pedido o el pedido posterior?

La estrategia transversal que selecciona el programador depende de las necesidades específicas del algoritmo que se está diseñando. El objetivo es la velocidad, así que elija la estrategia que le brinde los nodos que necesita más rápido.

  1. Si sabe que necesita explorar las raíces antes de inspeccionar las hojas, elija el pedido por adelantado porque encontrará todas las raíces antes que todas las hojas.

  2. Si sabe que necesita explorar todas las hojas antes que los nodos, seleccione el pedido posterior porque no pierde el tiempo inspeccionando las raíces en busca de hojas.

  3. Si sabe que el árbol tiene una secuencia inherente en los nodos y desea aplanar el árbol de nuevo en su secuencia original, entonces se debe usar un recorrido en orden . El árbol se aplastaría de la misma forma en que se creó. Es posible que un recorrido de pedido previo o posterior no desenrolle el árbol en la secuencia que se utilizó para crearlo.

Algoritmos recursivos para pedidos anticipados, pedidos y pedidos posteriores (C ++):

struct Node{
    int data;
    Node *left, *right;
};
void preOrderPrint(Node *root)
{
  print(root->name);                                  //record root
  if (root->left != NULL) preOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) preOrderPrint(root->right);//traverse right if exists
}

void inOrderPrint(Node *root)
{
  if (root.left != NULL) inOrderPrint(root->left);   //traverse left if exists
  print(root->name);                                 //record root
  if (root.right != NULL) inOrderPrint(root->right); //traverse right if exists
}

void postOrderPrint(Node *root)
{
  if (root->left != NULL) postOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) postOrderPrint(root->right);//traverse right if exists
  print(root->name);                                   //record root
}
Eric Leschinski
fuente
3
¿Qué pasa con los recorridos no recursivos? Me parece que es mucho más fácil atravesar un árbol de forma no recursiva en preorden en comparación con en orden / posorden, ya que no requiere volver a los nodos anteriores.
bluenote10
@ bluenote10 ¿Puedes dar más detalles sobre lo que quieres decir? En el pedido por adelantado, todavía "regresa" a un nodo para procesar su hijo derecho después de procesar su hijo izquierdo. Claro, podría usar una cola de "nodos aún no visitados", pero en realidad eso es solo intercambiar almacenamiento implícito (pila) por una cola explícita. En todos los métodos de recorrido, se deben procesar los elementos secundarios izquierdo y derecho, lo que significa que después de realizar uno de ellos debe "regresar" al elemento primario.
Joshua Taylor
@JoshuaTaylor: Sí, todos son de la misma clase de complejidad, pero si observa las implementaciones típicas, el pedido posterior es probablemente un poco más complicado.
bluenote10
2
El recorrido de pedido anticipado proporciona los valores de nodo en una secuencia de inserción. Si desea crear una copia del árbol, debe atravesar el árbol de origen de esta manera. El recorrido en orden proporciona los valores de nodo ordenados. En cuanto al recorrido posterior al pedido, puede usar este método para eliminar todo el árbol porque visita los nodos de hoja primero.
albin
Creo que es cierto incluso si el árbol no está ordenado correctamente, quiero decir, en orden no daría la secuencia ordenada si la secuencia no estuviera ordenada al principio.
CodeYogi
29

Pedido anticipado : se utiliza para crear una copia de un árbol. Por ejemplo, si desea crear una réplica de un árbol, coloque los nodos en una matriz con un recorrido de pedido previo. Luego, realice una operación Insertar en un árbol nuevo para cada valor de la matriz. Terminarás con una copia de tu árbol original.

En orden: se utiliza para obtener los valores de los nodos en orden no decreciente en una BST.

Pedido posterior : se utiliza para eliminar un árbol de la hoja a la raíz

Viraj Nimbalkar
fuente
2
Esta es una respuesta excelente y concisa que me ayudó a comprender los casos de uso de pedidos previos y posteriores al pedido. aunque, puede ser obvio dado que la pregunta menciona esto directamente, pero tenga en cuenta que este es el caso de los árboles de BÚSQUEDA binarios y no necesariamente funciona para árboles binarios generales. por ejemplo, no puede usar necesariamente el recorrido de preorden para copiar un árbol binario general, ya que la lógica de inserción durante el proceso de copia no funcionaría.
Markckim
7
En orden:: Para obtener valores de nodo en orden "no decreciente", no "no creciente"
rahil008
26

Si quisiera simplemente imprimir el formato jerárquico del árbol en un formato lineal, probablemente usaría el recorrido de preorden. Por ejemplo:

- ROOT
    - A
         - B
         - C
    - D
         - E
         - F
             - G
Oliver Charlesworth
fuente
4
O en un TreeViewcomponente de una aplicación GUI.
svick
4

El pedido previo y posterior se relacionan con algoritmos recursivos de arriba hacia abajo y de abajo hacia arriba, respectivamente. Si desea escribir un algoritmo recursivo dado en árboles binarios de manera iterativa, esto es lo que esencialmente hará.

Observe además que las secuencias de pre-orden y post-orden juntas especifican completamente el árbol en cuestión, produciendo una codificación compacta (para árboles dispersos al menos).

Raphael
fuente
1
Creo que está tratando de decir algo importante, ¿podría explicar la primera mitad?
CodeYogi
@CodeYogi ¿Qué necesitas específicamente que te expliquen?
Raphael
1
"El pedido previo y posterior se relacionan con algoritmos recursivos de arriba hacia abajo y de abajo hacia arriba" Creo que quiere decir que en el primer caso el nodo se procesa antes de llamar a cualquiera de los métodos recursivos y viceversa en el último, a la derecha ?
CodeYogi
@CodeYogi Sí, básicamente.
Raphael
2

Hay toneladas de lugares en los que ve que esta diferencia juega un papel real.

Uno excelente que señalaré es la generación de código para un compilador. Considere la declaración:

x := y + 32

La forma en que generaría código para eso es (ingenuamente, por supuesto) generar primero código para cargar y en un registro, cargar 32 en un registro y luego generar una instrucción para agregar los dos. Debido a que algo tiene que estar en un registro antes de manipularlo (supongamos que siempre puede hacer operandos constantes, pero lo que sea) debe hacerlo de esta manera.

En general, las respuestas que puede obtener a esta pregunta básicamente se reducen a esto: la diferencia realmente importa cuando existe cierta dependencia entre el procesamiento de diferentes partes de la estructura de datos. Esto se ve al imprimir los elementos, al generar código (el estado externo marca la diferencia, también puede ver esto de manera monádica, por supuesto), o al hacer otros tipos de cálculos sobre la estructura que involucran cálculos dependiendo de los hijos que se procesan primero. .

Kristopher Micinski
fuente