O percurso de pré-encomenda é o mesmo que a pesquisa de profundidade inicial?

12

Parece-me que a travessia de pré-ordem e o DFS são os mesmos que nos dois casos, atravessamos da raiz até o ramo esquerdo e de volta à raiz e depois ao ramo direito recursivamente. Alguém poderia me corrigir se eu estiver errado?

Desde já, obrigado!

algorithms trees binary-tree graph-traversal Srikanth Kandalam
fonte

Respostas:

10

passagem de pré-ordem é uma travessia, ela visita todos os nós em uma árvore binária

O Depth First Search é uma pesquisa, percorre um gráfico arbitrário procurando um determinado nó (que funciona melhor em um gráfico não cíclico (também conhecido como árvore) é irrelevante)

isso por si só é uma diferença grande o suficiente para chamá-los de nomes de diferenças

catraca arrepiante
fonte
1
+1, mas gostaria de acrescentar que as travessias de pré e pós-ordem são apenas casos especiais da estratégia DFS mais geral.
5304 Frank
1
A travessia de pré-encomenda não significa simplesmente processar nós antes dos filhos? Onde se diz que os nós formam uma árvore binária ou mesmo uma árvore?
Kilian Foth
@KilianFoth Eu esperaria que a implicação de um nó com filhos (em oposição a vizinhos) implique uma estrutura em árvore, pois sugere uma hierarquia de nós. O topo da hierarquia é a raiz da árvore. Mas posso imaginar a travessia de pré-ordem e a pós-ordem fazendo sentido em qualquer árvore, mesmo naquelas que não são binárias.
YoungJohn
1

Sim, mas deve ser o contrário: DFSé semelhante a PreOrder.
O termo PreOrderé mais relevante para árvores e analisadores binários .
Ele é usado para comparar com outras ordens de passagem de uma árvore binária: InOrder, PostOrdere PreOrder.
A classificação topológica é semelhante à passagem pós-ordem (empurre o nó na pilha depois de visitar todos os nós adjacentes).

user640554
fonte
Meus pensamentos são semelhantes a esta resposta. Mais especificamente, uma pré-encomenda é uma implementação específica da categoria pai do DFS. A travessia infantil de pré-encomenda é rigidamente esquerda e direita; enquanto que para DFS genérico (pai), a ordem de travessia dos filhos não está definida e pode ser qualquer ordem.
Jerred S.
-1

Para percorrer uma árvore binária na pré-encomenda, as seguintes operações são realizadas

  1. Visite a raiz
  2. Atravessar a subárvore esquerda
  3. Atravessar a subárvore direita

Ou seja, na imagem abaixo, o percurso de pré-encomenda seria 1,2,3,6,4,5,7,8,9,10,11,12

Na mesma imagem, 1,2,3,4,5,6,7,8,9,10,11,12 seria para DFS

Fonte DFS: http://datastructuresnotes.blogspot.in/2009/02/binary-tree-traversal-preorder-inorder.html

Origem da pré-encomenda: Wiki

DFS

Zedaiq
fonte
9
Esta não é uma árvore binária. É uma árvore, mas não binária.
Dilsh R
O que acontece quando "6" possui sub-nós?
Marjan Venema
Você está solicitando DFS ou pré-encomenda?
Zedaiq
@ManojR Entendi da fonte mencionada acima.
Zedaiq
a ordem dos pré-gráficos neste gráfico dá a mesma resposta
Charles Chow