¿Es el recorrido de preorden igual que la búsqueda en profundidad?

13

Me parece que el recorrido previo al pedido y el DFS son los mismos que en ambos casos, atravesamos desde la raíz hasta la rama izquierda y de regreso a la raíz y luego a la rama derecha de forma recursiva. ¿Podría alguien corregirme si estoy equivocado?

¡Gracias por adelantado!

algorithms trees binary-tree graph-traversal Srikanth Kandalam
fuente

Respuestas:

10

el recorrido previo al pedido es un recorrido, visita todos los nodos en un árbol binario

La primera búsqueda en profundidad es una búsqueda, va alrededor de un gráfico arbitrario buscando un determinado nodo (que funciona mejor en un gráfico no cíclico (también conocido como árbol) es irrelevante)

esto solo es una diferencia lo suficientemente grande como para llamarlos nombres de diferencia

monstruo de trinquete
fuente
1
+1, pero me gustaría agregar que los recorridos previos y posteriores al pedido son solo casos especiales de la estrategia DFS más general.
Frank
1
¿El recorrido de preorden no significa simplemente procesar nodos antes que sus hijos? ¿Dónde dice que los nodos forman un árbol binario, o incluso un árbol?
Kilian Foth
@KilianFoth Esperaría que la implicación de un nodo que tenga hijos (en oposición a los vecinos) implique una estructura de árbol, ya que sugiere una jerarquía de nodos. La parte superior de la jerarquía es la raíz del árbol. Pero me imagino que el recorrido previo al pedido y el recorrido posterior al pedido tienen sentido en cualquier árbol, incluso en aquellos que no son binarios.
YoungJohn
1

Sí, pero debería ser al revés: DFSes similar a PreOrder.
El término PreOrderes más relevante para árboles binarios y analizadores.
Se utiliza para comparar con otros órdenes de recorrido de un árbol binario: InOrder, PostOrdery PreOrder.
La ordenación topológica es similar al recorrido de orden posterior (empuje el nodo a la pila después de visitar todos los nodos adyacentes).

usuario640554
fuente
Mis pensamientos son similares a esta respuesta. Más específicamente, un pedido anticipado es una implementación específica de la categoría principal de DFS. El recorrido del niño de preorden está rígidamente a la izquierda y luego a la derecha; mientras que para el DFS genérico (padre), el orden transversal de los niños no está definido y podría ser cualquier orden.
Jerred S.
-1

Para atravesar un árbol binario en Preorder, se llevan a cabo las siguientes operaciones

  1. Visita la raíz
  2. Atravesar el subárbol izquierdo
  3. Atravesar el subárbol derecho

Es decir, en la imagen a continuación, el recorrido de preorden sería, 1,2,3,6,4,5,7,8,9,10,11,12

En la misma imagen 1,2,3,4,5,6,7,8,9,10,11,12 serían para DFS

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

Fuente de pedido anticipado: Wiki

DFS

Zedaiq
fuente
99
Este no es un árbol binario. Es un árbol, pero no binario.
Manoj R
¿Qué sucede cuando "6" tiene subnodos?
Marjan Venema
¿Está solicitando DFS o pedido anticipado?
Zedaiq
@ManojR Lo obtuve de la fuente mencionada anteriormente.
Zedaiq
preordenar en este gráfico da la misma respuesta
Charles Chow