¿Tiene sentido implementar iteradores para contenedores que no tienen un final obvio? árboles?

Question

Estoy escribiendo una plantilla de árbol de búsqueda binaria por dos razones: aprender C ++ y aprender los algoritmos y estructuras de datos más comunes.
Entonces, aquí está la pregunta: mientras yo quiera implementar iteradores, me parece que no hay una definición estricta de dónde termina el árbol. ¿Cuáles son tus sugerencias? ¿Cómo hago esto?

Answer 1

Para los árboles, existen estándares para atravesar el árbol, es decir, enumerar los nodos: Preorder transversal, inorder transversal y postorder transversal. En lugar de describir todo esto aquí, lo redireccionaré a http://en.wikipedia.org/wiki/Tree_traversal . La mayoría de los conceptos se aplican a árboles binarios, pero puede ampliar la idea a árboles arbitrarios agregando más casos: Efectivamente, maneje un nodo y luego recupere, retire, maneje un nodo, maneje todos los hijos y luego recurra a cada uno ... etc. No hay una categorización canónica de este enfoque que yo sepa.

Answer 2

Debe escribir algo claro al escribir un iterador: un iterador para una estructura de datos proporciona acceso a una colección como una secuencia lineal de elementos. Ciertas colecciones, como matrices, listas y colas, son naturalmente compatibles con ser tratadas como una secuencia lineal. Otros tipos de colecciones (árboles, diccionarios, gráficos) no tienen necesariamente una interpretación simple como una lista lineal. De hecho, las interpretaciones múltiples son generalmente válidas.

Lo que realmente debe hacer al escribir un iterador para una colección como un árbol es abordar las siguientes inquietudes:

1. ¿Dónde comienza la iteración de la colección (root? leaves?)
2. ¿Cómo avanza la iteración al siguiente elemento (infijo? ¿postfix? ¿sufijo? ¿ancho?)
3. ¿Cuándo termina la iteración (deja? ¿raíz? ¿nodo final?)

Lo que elija, debe tener muy claro cómo nombra (y documenta) su iterador para que sea obvio cómo visitará y emitirá nodos.

Es posible que deba escribir varios iteradores para los diferentes tipos de traverals que pretende apoyar. Hay algunos artículos buenos aquí que discuten

Si por "estricto" quiere decir: una sola definición que abarca todo, tiene razón, no hay una.

Pero 'end' para árboles está muy bien definido, aunque depende del método de recorrido que elija.

• Si realiza un recorrido transversal (o simétrico), el elemento más a la derecha sería end .
• en preorden (o profundidad primero), el elemento más a la derecha sería end , etc.
• en el orden posterior, el elemento raíz sería end , etc.

Los métodos recorrido de árboles más comunes.

Su definición de un iterador es ligeramente incorrecta. Los iteradores no van de inicio a terminar , ni de frente a atrás . En su lugar, van a través de a todos los miembros de esa estructura.

Si solicita una iteración sobre una estructura ordenada, es decir, una matriz, una lista enlazada, etc., (generalmente) obtendrá a sus miembros devueltos en orden.

Para los elementos desordenados, por ejemplo, un conjunto, los obtendrá en el orden que el conjunto-iterador quiera entregarles, pero los obtendrá todos y uno a la vez, tal como lo haría con un iterador de matrices.

En cuanto a los árboles, otras personas ya han mencionado: tienen nociones bien definidas de orden total, solo tienes que elegir una :)

Depende de lo que quiera hacer con el árbol, tal vez sería bueno tener, por ejemplo, iteradores de búsqueda en profundidad o búsqueda en profundidad (o ambos).

Si tiene alguna forma particular de recorrer el árbol, en efecto tiene un principio y un final. No es tan obvio como las relaciones lineales en listas y conjuntos, pero está ahí si quieres imponerle un orden.

Tiene sentido especialmente en casos como este, porque les brinda a los usuarios de su clase una forma de recorrer fácilmente todos los elementos de diferentes maneras según lo requiera la situación. Sin ellos, los usuarios necesitan escribir formas complicadas, generalmente recursivas. En comparación con, por ejemplo, vectores donde los iteradores escriben más que cuando se usa para (i = 0; i     

Pienso en iterador de una manera más abstracta. No veo en el patrón del iterador nada que realmente diga que hay un principio o un final. Entonces, ¿por qué estar limitado a esa visión? Podemos imaginar iterador que solo se preocupa por el siguiente elemento, eso es todo. Quiero decir, me he enfrentado a situaciones (especialmente en el procesamiento en masa) en las que desde el principio no sabemos la extensión de la colección, no sabemos si algún día terminará o no tenemos todas sus Elementos cargados en la memoria, y no nos importa. Solo nos importa conseguir el siguiente elemento. En una de esas implementaciones, el siguiente nodo se crea justo después de llamar al siguiente método de elementos. Podemos abrir nuestras mentes y pensar en colecciones infinitas (al final, una colección es un tipo de conjunto matemático) como las colecciones de todos los números, la colección de todos los números aleatorios. No es necesario que tenga todos los elementos en la memoria (eso es obvio para las colecciones infinitas). Por supuesto, estos no son ejemplos prácticos, pero mi mensaje es que un usuario de un iterador no tiene que confiar en la estructura o extensión real de una colección. Solo dame el siguiente (si lo tienes).

Answer 3

Si por "estricto" quiere decir: una sola definición que abarca todo, tiene razón, no hay una.

Pero 'end' para árboles está muy bien definido, aunque depende del método de recorrido que elija.

• Si realiza un recorrido transversal (o simétrico), el elemento más a la derecha sería end .
• en preorden (o profundidad primero), el elemento más a la derecha sería end , etc.
• en el orden posterior, el elemento raíz sería end , etc.

Los métodos recorrido de árboles más comunes.

Answer 4

Su definición de un iterador es ligeramente incorrecta. Los iteradores no van de inicio a terminar , ni de frente a atrás . En su lugar, van a través de a todos los miembros de esa estructura.

Si solicita una iteración sobre una estructura ordenada, es decir, una matriz, una lista enlazada, etc., (generalmente) obtendrá a sus miembros devueltos en orden.

Para los elementos desordenados, por ejemplo, un conjunto, los obtendrá en el orden que el conjunto-iterador quiera entregarles, pero los obtendrá todos y uno a la vez, tal como lo haría con un iterador de matrices.

En cuanto a los árboles, otras personas ya han mencionado: tienen nociones bien definidas de orden total, solo tienes que elegir una :)

Answer 5

Depende de lo que quiera hacer con el árbol, tal vez sería bueno tener, por ejemplo, iteradores de búsqueda en profundidad o búsqueda en profundidad (o ambos).

Si tiene alguna forma particular de recorrer el árbol, en efecto tiene un principio y un final. No es tan obvio como las relaciones lineales en listas y conjuntos, pero está ahí si quieres imponerle un orden.

Answer 6

Tiene sentido especialmente en casos como este, porque les brinda a los usuarios de su clase una forma de recorrer fácilmente todos los elementos de diferentes maneras según lo requiera la situación. Sin ellos, los usuarios necesitan escribir formas complicadas, generalmente recursivas. En comparación con, por ejemplo, vectores donde los iteradores escriben más que cuando se usa para (i = 0; i     

Answer 7

Pienso en iterador de una manera más abstracta. No veo en el patrón del iterador nada que realmente diga que hay un principio o un final. Entonces, ¿por qué estar limitado a esa visión? Podemos imaginar iterador que solo se preocupa por el siguiente elemento, eso es todo. Quiero decir, me he enfrentado a situaciones (especialmente en el procesamiento en masa) en las que desde el principio no sabemos la extensión de la colección, no sabemos si algún día terminará o no tenemos todas sus Elementos cargados en la memoria, y no nos importa. Solo nos importa conseguir el siguiente elemento. En una de esas implementaciones, el siguiente nodo se crea justo después de llamar al siguiente método de elementos. Podemos abrir nuestras mentes y pensar en colecciones infinitas (al final, una colección es un tipo de conjunto matemático) como las colecciones de todos los números, la colección de todos los números aleatorios. No es necesario que tenga todos los elementos en la memoria (eso es obvio para las colecciones infinitas). Por supuesto, estos no son ejemplos prácticos, pero mi mensaje es que un usuario de un iterador no tiene que confiar en la estructura o extensión real de una colección. Solo dame el siguiente (si lo tienes).