data structures - bfs - Cuándo utilizar las estrategias Preorder, Postorder y Inorder Binary Search Tree Traversal

dfs pre order post order

Question

Recientemente me di cuenta de que, aunque había utilizado mucho BST en mi vida, nunca había contemplado el uso de Inorder transversal (aunque soy consciente y sé lo fácil que es adaptar un programa para utilizar el recorrido pre / post-order).

Al darme cuenta de esto, saqué algunos de mis viejos libros de texto de estructuras de datos y busqué el razonamiento detrás de la utilidad de los recorridos previos y posteriores a la orden; 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?

Answer 1

Cuándo utilizar la estrategia de seguimiento previa al pedido, en orden y posterior a la orden

Antes de que pueda entender bajo qué circunstancias utilizar el preorden, el orden y el pedido posterior para un árbol binario, debe comprender exactamente cómo funciona cada estrategia transversal. Usa el siguiente árbol como un 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 .

Cruce de prepedido :

Resumen: comienza en la raíz ( 7 ) y termina en el nodo situado 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 de recorrido: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Travesía post-pedido :

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

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

¿Cuándo usar Pre-Order, In-order o Post-Order?

La estrategia transversal que selecciona el programador depende de las necesidades específicas del algoritmo que se diseña. El objetivo es la velocidad, por lo tanto, elija la estrategia que le proporcione los nodos que necesita con mayor rapidez.

1. Si sabes que necesitas explorar las raíces antes de inspeccionar las hojas, debes hacer un pedido por adelantado porque encontrarás todas las raíces antes de todas las hojas.

2. Si sabe que necesita explorar todas las hojas antes de cualquier nodo, seleccione el pedido posterior porque no pierde 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 en su secuencia original, se debe utilizar un recorrido en orden . El árbol sería aplanado de la misma manera que fue creado. Un recorrido de preorden o posterior al pedido puede no desenrollar el árbol en la secuencia que se usó para crearlo.

Algoritmos recursivos para preordenes, en orden y post-orden (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
}

Answer 2

Hay muchos lugares en los que esta diferencia juega un papel real.

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

x := y + 32

La forma en que generaría código para eso es (ingenuamente, por supuesto) generar 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 puedes hacer operandos constantes pero lo que sea) debes 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 alguna dependencia entre el procesamiento de diferentes partes de la estructura de datos. Usted ve esto al imprimir los elementos, al generar código (el estado externo hace la diferencia, también puede ver esto monádicamente, por supuesto), o al hacer otros tipos de cálculos sobre la estructura que involucran cálculos según los niños que se procesan primero .

Answer 3

Los pedidos previos y posteriores se relacionan con algoritmos recursivos descendentes y ascendentes, respectivamente. Si desea escribir un algoritmo recursivo dado en árboles binarios de forma iterativa, esto es lo que esencialmente hará.

Observe además que las secuencias previas y posteriores a la orden juntas especifican completamente el árbol en cuestión, produciendo una codificación compacta (para árboles dispersos al menos).

Answer 4

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

Answer 5

Uso de preordenar / en orden / posterior a la orden: palabras simples

Pedido por adelantado: utilizado para crear una copia de árbol Ejemplo: si desea crear una réplica de un árbol y necesita valores de nodo en una matriz y cuando inserta esos valores desde el índice 0 para finalizar en un árbol nuevo, obtiene una réplica

En orden: para obtener valores de nodo en orden no creciente

Postorder : cuando desee eliminar un árbol de hoja en raíz