C++, implementando un iterador personalizado para árboles binarios (largo)

Question

Por favor se agradable, esta es mi primera pregunta. = P

Básicamente como un proyecto de verano He estado revisando la lista de estructuras de datos en el wikipedia page y tratando de implementarlas. Tomé un curso de C++ el semestre pasado y me pareció muy divertido, como proyecto final implementé un Binomial Heap; también fue muy divertido. Tal vez soy nerd, pero me encantan las estructuras de datos.

De todos modos, suficiente historia. El proyecto va bien, estoy comenzando con Binary Trees. Para ir mucho más lejos, necesito crear iteradores para atravesar los árboles. Ya he decidido crear dos tipos de iteradores para cada método transversal (iterador regular e iterador constante), simplemente no tengo idea de cómo hacer esto. He oído hablar de heredar de las cosas del iterador de stl, o incluso de usar boosts iterator_facade (que parece una buena opción)

Ni siquiera he intentado escribir el código del iterador porque no sé por dónde empezar, pero tengo mi código actual en github. Puede verificarlo here.

En caso de que se oponga a github, voy a pegar las definiciones de clases relevantes. La implementación de estas funciones realmente no sería de ninguna ayuda, pero si las necesita por alguna razón, hágamelo saber. Además, la clase de nodo tiene un puntero principal para fines de iteración.

#ifndef __TREES_HXX 
#define __TREES_HXX 
#include <cstdlib> // For NULL 
#include <algorithm> // for std::max 

// Node class definition. These nodes are to be used for any 
// tree where the structure is 
// node 
//  /\ 
// left right 
// /\ /\ 
// 
// etc., basically two children. 
template <typename T> 
class Node 
{ 
    public: 
    T data_; 
    Node<T>* left_; 
    Node<T>* right_; 
    Node<T>* parent_; // Needed for iterators 

    explicit Node(T const&); 
    Node(Node<T> const&); 
}; 

template <typename T> 
class BinaryTree 
{ 
    protected: 
    typedef Node<T>* node_t; 
    size_t tree_size; 

    public: 
    typedef T value_type; 

    explicit BinaryTree(); 
    explicit BinaryTree(T const&); 
    ~BinaryTree(); 

    virtual node_t insert(node_t&, T) = 0; 
    virtual T& lookup(node_t const&, T const&) const = 0; 
    inline virtual size_t size() const; 
    inline virtual size_t depth(node_t const&) const; 
    inline bool empty() const; 
    inline void clear(node_t); 

    node_t root; 
}; 

Esta es la extensión básica del árbol binario de nuestra clase abstracta, básicamente será (será) una BST. Para ver un ejemplo de por qué necesito iteradores, mire la definición de la función de búsqueda. Debería devolver un iterador al nodo donde se encuentran las cosas.

/* Implementation of our Binary Tree is in 
* this file. The node class is in Trees.hxx 
* because it's intended to be a general class. 
*/ 

#ifndef __BINARY_TREE_HXX 
#define __BINARY_TREE_HXX 

#include "Trees.hxx" 


template <typename T> 
class BiTree : public BinaryTree<T> 
{ 
    private: 
    typedef typename BinaryTree<T>::node_t node_t; 

    public: 
    typedef typename BinaryTree<T>::value_type value_type; 

    BiTree() : BinaryTree<T>() 
    { 
    } 

    BiTree(T const& data) : BinaryTree<T>(data) 
    { 
    } 

    node_t insert(node_t&, T); 
    T& lookup(node_t const&, T const&) const; // Note: This should return an iterator to the node where the stuff is found 
}; 

Creo que es eso, gracias por su tiempo! Si necesita información adicional, hágamelo saber.

Answer 1

1. Grasa Iteradores vs Iteradores magras

Hay dos maneras posibles para poner en práctica el recorrido de un árbol. Usted puede:

• tienen nodos que simplemente apunta a sus "niños", e iteradores que mantienen una pila (por lo tanto, iteradores grasa)
• tienen nodos que tienen un puntero padre (como la suya), e iteradores que son sólo punteros a un nodo dado (iteradores magras)

Es un diseño disyuntiva, los ejecutores STL por lo general van de la manera magra porque iteradores (en el STL) se supone que es barato para dupdo.

2.Los iteradores fáciles vs Desde iteradores scratch

También hay varias formas de implementar iteradores:

• From Scratch: lo hace todo por su cuenta, lo que incluye la definición de typedef, todas las sobrecargas de operadores etc ...
• Fácil : utiliza Boost.Iterator de implementar como poco código como sea posible por sí mismo

básicamente cuento heredando de std::iterator como una situación "desde cero", ya que proporciona un mero 5 typedef ...

si elegir uno u otro realmente depende de su situación:

• Para aprender propósito, recomendaría ir al "desde cero" camino un par de veces
• con fines de producción , Recomendaría usar el método "From Scratch" (heredar de Boost no ahorra mucho, pero complica los depuradores de sesión/memoria de depuración, al menos con gdb, porque gdb expone las clases base)
• Para una prueba rápida, lo haría recomiendo ir a la manera "Fácil"

Tenga en cuenta que puede que se encuentre en una situación extraña en la que su iterador no se puede construir sobre Boost.Iterator, en cuyo caso no tendrá más remedio que construirlo usted mismo.

3. Const y iteradores no const

Esto es, quizás, el punto principal.

Aunque sólo sea por esto, es digno de mirar Boost.Iterator, porque exponen la técnica para implementar uno iterador (con plantilla) que cubrirá ambos casos.

Mira la sección deTutorial en el Ejemplo Iterator Adaptor:

template <class Value> 
class node_iter 
    : public boost::iterator_adaptor< 
     node_iter<Value>    // Derived 
     , Value*       // Base 
     , boost::use_default    // Value 
     , boost::forward_traversal_tag // CategoryOrTraversal 
    > 
{ 
private: 
    struct enabler {}; // a private type avoids misuse 

public: 
    node_iter() 
     : node_iter::iterator_adaptor_(0) {} 

    explicit node_iter(Value* p) 
     : node_iter::iterator_adaptor_(p) {} 

    /// !!! Highlight !!! 
    template <class OtherValue> 
    node_iter(
     node_iter<OtherValue> const& other 
     , typename boost::enable_if< 
      boost::is_convertible<OtherValue*,Value*> 
      , enabler 
     >::type = enabler() 
    ) 
     : node_iter::iterator_adaptor_(other.base()) {} 

private: 
    friend class boost::iterator_core_access; 
    void increment() { this->base_reference() = this->base()->next(); } 
}; 

La tercera constructor es el punto clave para conseguir un par de const y const iteradores no con la conversión automática de const a la no const sin la conversión inversa es posible.

lo que haga, volver a utilizar el mismo truco: crear plantillas de un BaseIterator en Value, y la proporcionan los dos typedefs: typedef BaseIterator<Value> iterator y typedef BaseIterator<Value const> const_iterator.

Answer 2

Una forma de implementar esto es tener una pila en su iterador que realice un seguimiento de los nodos principales. Cada vez que llegue a un nodo, es que no es una hoja, introdúzcalo en la pila y continúe con el siguiente nodo en el orden de búsqueda. Una vez que tocas una hoja, trátala, luego regresa al nodo en la parte superior de la pila. Repite ad nausium hasta que hayas visitado todo.