algorithm - preorden - ¿El recorrido de Pre-Order en un árbol binario es lo mismo que la búsqueda en profundidad primero?

recorrido de un arbol matematicas discretas

Question

Me parece que el recorrido previo al pedido y el DFS son los mismos que en los dos casos que atravesamos hasta el nodo de la hoja de manera profunda. ¿Podría alguien corregirme si me equivoco?

¡Gracias por adelantado!

Answer 1

No lo sera El pre-pedido tiene una forma estricta de visitar el nodo izquierdo y luego el nodo derecho. Pero para DFS puede ser cualquiera ya que no hay una moda estricta. Por lo tanto, existe más de un recorrido basado en lo que empujas en la pila.

Answer 2

Pre-order es un tipo de DFS.

Hay tres tipos de recorrido de profundidad primero: pedido anticipado, pedido y pedido posterior.

Echa un vistazo here para obtener más información.

Answer 3

Probablemente depende de la definición e implementación del algoritmo de profundidad primero. La clase DefaultMutableTreeNode del componente JTree de Java Swing tiene los siguientes métodos de enumeración utilizados para el recorrido del árbol:

• depthFirstEnumeration ()
• postorderEnumeration ()
• preorderEnumeration ()
• breadthFirstEnumeration ()

En la implementación de Java Swing, depthFirstEnumeration es la misma que postOrderEnumeration . Mis pruebas y la documentación oficial lo confirman.

Otros pueden definir qué significa primero la profundidad de manera diferente. Por ejemplo, un artículo en here establece que los recorridos pre-orden y post-orden son tipos específicos de un recorrido primero en profundidad. Esto significaría que el recorrido primero en profundidad no es un algoritmo de recorrido concreto.