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

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?

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 .

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
}

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

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

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).

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. .