Implementación de un iterador sobre árbol binario (o arbitrario) usando C++ 11

Question

Me gustaría crear un iterador sobre el árbol binario para poder usar el bucle for basado en rango. Entiendo que debería implementar primero la función begin() y end().

Begin debería apuntar probablemente a la raíz. De acuerdo con la especificación, sin embargo, la función end() devuelve "el elemento que sigue al último elemento válido". ¿Qué elemento (nodo) es eso? ¿No sería ilegal señalar algún lugar "inválido"?

La otra cosa es el operador ++. ¿Cuál es la mejor manera de devolver el elemento "siguiente" en el árbol? Solo necesito algunos consejos para comenzar con esta programación.

---

Quiero agradecer/ampliar mi pregunta *. ¿Qué pasaría si quisiera iterar sobre un árbol con una aridad arbitraria? Deje que cada nodo tenga un vector de elementos secundarios y permita que begin() señale la raíz "real". Probablemente tendría que implementar una cola (para amplitud primero) dentro de la clase de iterador para almacenar el unique_ptr en nodos, ¿verdad? Entonces, cuando la cola esté vacía, sabré que he pasado todos los nodos y, por lo tanto, debería devolver TreeIterator (nullptr) cuando se llame a oprator ++(). ¿Tiene sentido? Lo quiero tan simple como sea posible y solo reenvío la iteración.

* ¿O debería crear un nuevo hilo?

Answer 1

Donde su begin() debe apuntar depende mucho del orden en el que desea atravesar su árbol. Usar la raíz puede ser sensato, por ejemplo, para una primera caminata de ancho del árbol. El end() no se sienta realmente en un nodo de árbol: se accede a esta posición e indica que se ha alcanzado el final de la secuencia. Si esto indica algo relacionado con el árbol, en cierto modo, depende del tipo de iteración que desee admitir: al admitir solo la iteración directa, puede simplemente indicar el final. Cuando también admite la iteración bidireccional, necesita saber cómo encontrar el nodo justo antes del final.

En cualquier caso, el lugar señalado no es realmente accedido y necesita un indicador adecuado. Para una iteración hacia adelante, solo el iterador end() podría simplemente devolver un iterador que apunte a nulo y cuando se mueva desde el último nodo también establezca el puntero del iterador como nulo: igualdad al comparar los dos punteros produciría true, lo que indica que ha alcanzado el fin. Cuando desee admitir una iteración bidireccional, necesitará algún tipo de registro de enlace que pueda usarse para navegar al nodo anterior pero que no necesite almacenar un valor.

Los contenedores asociados ordenados (std::map<K, V>, std:set<V>, etc.) se implementan internamente como algún tipo de árbol (por ejemplo, un árbol rojo/negro). El iterador begin() comienza con el nodo situado más a la izquierda y el iterador end() hace referencia a la posición después del nodo situado más a la derecha.El operator++() simplemente busca el siguiente nodo a la derecha de la corriente:

• si el iterador se sienta en un nodo sin un nodo hijo derecho, que camina a lo largo de la cadena de los padres hasta que encuentra uno de los padres de llegar a su hijo a través de la rama izquierda del árbol
• si se encuentra en un nodo con un nodo secundario derecho, camina hacia el elemento secundario y luego hacia abajo en la secuencia de elementos secundarios izquierdos de este elemento secundario (si corresponde) para encontrar el elemento secundario izquierdo en el árbol secundario derecho .

Obviamente, si no recorre su árbol de izquierda a derecha sino, por ejemplo, de arriba a abajo, necesitará un algoritmo diferente. El enfoque más fácil para mí es dibujar un árbol en un pedazo de papel y ver cómo llegar al siguiente nodo.

Si no ha implementado una estructura de datos usando sus propios iteradores, recomiendo probar cosas en una estructura de datos secuencial simple, por ejemplo, una lista: allí es bastante obvio cómo llegar al siguiente nodo y cuándo fin se alcanza. Una vez que el principio de iteración general es claro, crear un árbol es solo una cuestión de obtener la navegación correcta.

Answer 2

Un iterador para un árbol va a ser algo más que un puntero, aunque es probable que contenga un puntero:

struct TreeIterator { 
    TreeIterator(TreeNode *node_ptr) : node_ptr(node_ptr) { } 
    TreeIterator &operator++(); 
    TreeIterator operator++(int); 
    bool operator==(const TreeIterator &) const; 

    private: 
    TreeNode *node_ptr; 
}; 

TreeIterator begin(const Tree &tree) { ... } 
TreeIterator end(const Tree &tree) { ... } 

Usted puede hacer su extremo() devuelto por una función algo especial, como TreeIterator(nullptr)

Lo que indica su iterador de inicio dependerá del tipo de recorrido que desee. Si está haciendo un recorrido transversal en amplitud, entonces comenzar desde la raíz tiene sentido.

Answer 3

Mire la implementación SGI de RBTree (esta es la base para los contenedores std::set/ ...).

http://www.sgi.com/tech/stl/stl_tree.h

Usted verá que begin() es el nodo más a la izquierda.

Usted verá ese fin() es un especial de "vacío" nodo de cabecera que es la raíz súper - me refiero a una raíz real (preestablecido sólo si el árbol no está vacío) es su nodo hijo.

operator ++ es ir a la derecha del niño y luego encontrar este nodo hijo más a la izquierda. Si dicho elemento secundario no existe, vamos al elemento primario izquierdo del nodo primario más a la derecha. Como en este ejemplo (líneas rojas son movimiento de salto, extremos azules cuáles son los pasos que se indican de iteración):

El código copiado de SGI:

void _M_increment() 
    { 
    if (_M_node->_M_right != 0) { 
     _M_node = _M_node->_M_right; 
     while (_M_node->_M_left != 0) 
     _M_node = _M_node->_M_left; 
    } 
    else { 
     _Base_ptr __y = _M_node->_M_parent; 
     while (_M_node == __y->_M_right) { 
     _M_node = __y; 
     __y = __y->_M_parent; 
     } 
     if (_M_node->_M_right != __y) 
     _M_node = __y; 
    } 
    } 

Cuando un árbol está vacío - begin() está a la izquierda del encabezado - por lo que es el encabezado en sí - end() también es encabezado - entonces begin() == end(). Recuerde: su esquema de iteración debe coincidir con esta condición begin() == end() para árboles vacíos.

Este parece ser un esquema de iteración muy inteligente.

Por supuesto, puede definir su propio esquema, pero la lección aprendida es tener un nodo especial para el propósito end().