Придумал вот такую реализацию дерева.
Итераторы пока не прикрутил сюда.
Попинайте plz кому не лень.

namespace tree {

    //---------------------------------------------------------------------------------
    struct  container_operation_core
    {
        template< typename TFacade, typename TData >
        static  bool    insert( TFacade& f, TData& d ) {
            return f.impl_insert( d );
        }

        template< typename TFacade >
        static bool    remove( TFacade& f, unsigned int idx ) {
            return f.impl_remove( idx );
        }

        template< typename TFacade >
        static void     remove_all( TFacade& f ) {
            return f.impl_remove_all();
        }

        template< typename TFacade, typename TData >
        static TData&  at( TFacade& f, unsigned int idx ) {
            return f.impl_at( idx );
        }

        template< typename TFacade >
        static unsigned int total( TFacade& f ) {
            return f.impl_total();
        }
    };
    //.................................................................................
    template< 
        typename TDerived
        , typename TData
    >
    struct  container
    {
        TDerived&   derived() { return *static_cast<TDerived*>(this); }
        const TDerived&   derived() const { return *static_cast<const TDerived*>(this); }

        bool    insert( TData& data ) {
            return container_operation_core::insert( this->derived(), data );
        }

        bool    remove( unsigned int idx ) {
            return container_operation_core::remove( this->derived(), idx );
        }

        void    remove_all() {
            container_operation_core::remove_all(  this->derived() );
        }

        TData&  operator[]( unsigned int idx ) {
            return container_operation_core::at<TDerived, TData>( this->derived(), idx );
        }

        unsigned int    total() const {
            return container_operation_core::total( this->derived() );
        }
    };
    //---------------------------------------------------------------------------------
    //.................................................................................
    //implementation 4 vector
    struct  use_std_vector {
        template< typename T > 
        struct subtype { 
            typedef std::vector<T> container;

            static bool    impl_insert( container& c, const T& data ) {
                c.push_back( data );
                return true;
            }
            static bool    impl_remove( container& c, unsigned int idx ) {
                if( idx > c.size() ) return false;
                c.erase( c.begin()+idx );
                return true;
            }
            static void    impl_remove_all( container& c ) {
                c.clear();
            }
            static T&    impl_at( container& c, unsigned int idx ) {
                return c[idx];
            }
            static unsigned  impl_total( const container& c ) {
                return c.size();
            }
        };
    };

    //---------------------------------------------------------------------------------
    //tree node
    template<
            typename TData
        ,   typename node_container
    >
    struct  tree_node : public container< tree_node<TData, node_container>, tree_node<TData, node_container> >
    {
        typedef TData   data_t;
        typedef tree_node<TData, node_container>    self_t;
        typedef typename node_container::subtype<self_t> subtype_t;
        typedef typename subtype_t::container  childs_container;

        tree_node()
            : m_pparent(NULL)
        {}

        tree_node( TData data ) 
            : m_data(data) 
        {}

    private:
        friend class    container_operation_core;

        bool    impl_insert( self_t& data ) {
            data.set_parent( this );
            return subtype_t::impl_insert( m_childs, data );
        }
        bool    impl_remove( unsigned int idx ) {
            return subtype_t::impl_remove( m_childs, idx );
        }
        void    impl_remove_all() {
            subtype_t::impl_remove_all( m_childs );
        }
        self_t&    impl_at( unsigned int idx ) {
            return subtype_t::impl_at( m_childs, idx );
        }
        unsigned  impl_total() const {
            return subtype_t::impl_total( m_childs );
        }

    private:
        void    set_parent( self_t* p ) { m_pparent = p; }

    private:
        self_t*             m_pparent;
        childs_container    m_childs;
        data_t              m_data;
    };

    //---------------------------------------------------------------------------------
    //basic tree
    template<
            typename TData
        ,   typename container = use_std_vector
    >
    struct basic_tree 
    {
        typedef tree_node<TData, container> node_t;

        node_t& root() { return m_root; }

    private:
        node_t  m_root;
    };
}

использование:

    typedef tree::basic_tree<int>   test_tree_t;

    test_tree_t tree;

    tree.root().remove_all();
    tree.root().insert( test_tree_t::node_t(0) );
    tree.root().insert( test_tree_t::node_t(1) );
    tree.root()[0].insert( test_tree_t::node_t(3) );
    tree.root()[0][0].insert( test_tree_t::node_t(4) );
    tree.root()[0][0][0].insert( test_tree_t::node_t(5) );
    tree.root()[0][0].remove( 0 );