Quando usar as estratégias Preorder, Postorder e Inorder Binary Search Tree Traversal

97

Percebi recentemente que, embora tenha usado bastante o BST na minha vida, nunca pensei em usar nada além da travessia Inorder (embora eu esteja ciente e saiba como é fácil adaptar um programa para usar a travessia pré / pós-pedido).

Ao perceber isso, peguei alguns dos meus antigos livros didáticos de estruturas de dados e procurei um raciocínio por trás da utilidade das passagens de pré-pedido e pós-pedido - eles não disseram muito.

Quais são alguns exemplos de quando usar a pré-encomenda / pós-encomenda na prática? Quando isso faz mais sentido do que em ordem?

John Humphreys - w00te
fonte

Respostas:

135

Quando usar a estratégia de pré-pedido, pedido e pós-pedido transversal

Antes que você possa entender sob quais circunstâncias usar a pré-ordem, a ordem e a pós-ordem para uma árvore binária, você precisa entender exatamente como cada estratégia de passagem funciona. Use a seguinte árvore como exemplo.

A raiz da árvore é 7 , o nó mais à esquerda é 0 , o nó mais à direita é 10 .

insira a descrição da imagem aqui

Traversal de pré-encomenda :

Resumo: começa na raiz ( 7 ), termina no nó mais à direita ( 10 )

Sequência transversal: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Percurso em ordem :

Resumo: começa no nó mais à esquerda ( 0 ), termina no nó mais à direita ( 10 )

Sequência transversal: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Traversal pós-pedido :

Resumo: começa com o nó mais à esquerda ( 0 ), termina com a raiz ( 7 )

Sequência transversal: 0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

Quando usar a pré-encomenda, encomenda ou pós-encomenda?

A estratégia de passagem que o programador seleciona depende das necessidades específicas do algoritmo que está sendo projetado. O objetivo é a velocidade, então escolha a estratégia que traz os nós de que você precisa com mais rapidez.

  1. Se você sabe que precisa explorar as raízes antes de inspecionar as folhas, faça uma pré-encomenda porque encontrará todas as raízes antes de todas as folhas.

  2. Se você sabe que precisa explorar todas as folhas antes de qualquer nó, selecione pós-pedido porque não perde tempo inspecionando raízes em busca de folhas.

  3. Se você sabe que a árvore tem uma sequência inerente nos nós e deseja achatar a árvore de volta à sua sequência original, uma travessia em ordem deve ser usada. A árvore seria achatada da mesma forma que foi criada. Uma passagem de pré-pedido ou pós-pedido pode não desdobrar a árvore de volta à sequência que foi usada para criá-la.

Algoritmos recursivos para pré-pedido, pedido e pós-pedido (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
fonte
3
E quanto a travessias não recursivas? Parece-me que é muito mais fácil percorrer uma árvore não recursivamente na pré-ordem do que na ordem / pós-ordem, uma vez que não requer o retorno aos nós anteriores.
bluenote10
@ bluenote10 Você pode explicar o que quer dizer? Na pré-encomenda, você ainda "retorna" a um nó para processar seu filho direito após processar seu filho esquerdo. Claro, você poderia usar uma fila de "nós ainda não visitados", mas isso na verdade é apenas trocar o armazenamento implícito (pilha) por uma fila explícita. Em todos os métodos de travessia, os filhos esquerdo e direito devem ser processados, o que significa que, depois de fazer um deles, você deve "retornar" ao pai.
Joshua Taylor
@JoshuaTaylor: Sim, eles são todos da mesma classe de complexidade, mas se você olhar as implementações típicas, a pós-encomenda provavelmente é um pouco mais complicada.
bluenote10
2
A transversal de pré-pedido fornece os valores dos nós em uma sequência de inserção. Se você deseja criar uma cópia da árvore, você precisa percorrer a árvore de origem desta forma. A travessia em ordem fornece os valores dos nós classificados. Quanto à travessia pós-ordem, você pode usar este método para excluir a árvore inteira, pois ela visita os nós folha primeiro.
albin
Eu acho que é verdade mesmo que a árvore não esteja ordenada corretamente, quero dizer, a ordem não daria a sequência ordenada se a sequência não fosse ordenada primeiro.
CodeYogi
29

Pré-encomenda: Usado para criar uma cópia de uma árvore. Por exemplo, se você deseja criar uma réplica de uma árvore, coloque os nós em uma matriz com uma travessia de pré-ordem. Em seguida, execute uma operação Insert em uma nova árvore para cada valor do array. Você vai acabar com uma cópia de sua árvore original.

Em ordem:: usado para obter os valores dos nós em ordem não decrescente em um BST.

Pós-pedido:: usado para excluir uma árvore da folha à raiz

Viraj Nimbalkar
fonte
2
esta é uma resposta ótima e concisa e me ajudou a entender os casos de uso de pré-pedido e pós-pedido. embora possa ser óbvio, visto que a pergunta menciona isso diretamente, mas observe que este é o caso para árvores SEARCH binárias e não necessariamente funciona para árvores binárias gerais. por exemplo, você não pode necessariamente usar a passagem de pré-pedido para copiar uma árvore binária geral, pois a lógica de inserção durante o processo de cópia não funcionaria.
markckim de
7
Em ordem: Para obter valores de nó na ordem "não decrescente" - não "não crescente"
rahil008
26

Se eu quisesse simplesmente imprimir o formato hierárquico da árvore em um formato linear, provavelmente usaria travessia de pré-ordem. Por exemplo:

- ROOT
    - A
         - B
         - C
    - D
         - E
         - F
             - G
Oliver Charlesworth
fonte
4
Ou em um TreeViewcomponente em um aplicativo GUI.
svick
4

A pré e pós-ordem estão relacionadas a algoritmos recursivos de cima para baixo e de baixo para cima, respectivamente. Se você quiser escrever um determinado algoritmo recursivo em árvores binárias de maneira iterativa, é isso que você essencialmente fará.

Observe, além disso, que as sequências de pré e pós-ordem em conjunto especificam completamente a árvore em questão, produzindo uma codificação compacta (para árvores esparsas, pelo menos).

Rafael
fonte
1
Acho que você está tentando dizer algo importante, por favor, explique a primeira parte?
CodeYogi
@CodeYogi O que especificamente você precisa explicar?
Raphael
1
"Pré e pós-pedido estão relacionados a algoritmos recursivos de cima para baixo e de baixo para cima" Acho que você quer dizer que no primeiro caso o nó é processado antes de chamar qualquer um dos métodos recursivos e vice-versa no último, certo ?
CodeYogi
@CodeYogi Sim, basicamente.
Raphael
2

Há muitos lugares onde você vê que essa diferença desempenha um papel real.

Um ótimo que vou apontar é a geração de código para um compilador. Considere a declaração:

x := y + 32

A maneira como você geraria código para isso é (ingenuamente, é claro) primeiro gerar o código para carregar y em um registrador, carregar 32 em um registrador e então gerar uma instrução para adicionar os dois. Porque algo tem que estar em um registro antes de você manipulá-lo (vamos supor que você sempre pode fazer operandos constantes, mas tanto faz), você deve fazer dessa maneira.

Em geral, as respostas que você pode obter para essa pergunta se reduzem basicamente a isto: a diferença realmente importa quando há alguma dependência entre o processamento de diferentes partes da estrutura de dados. Você vê isso ao imprimir os elementos, ao gerar o código (o estado externo faz a diferença, você também pode ver isso monadicamente, é claro) ou ao fazer outros tipos de cálculos sobre a estrutura que envolvem cálculos dependendo dos filhos sendo processados ​​primeiro .

Kristopher Micinski
fonte