用C++（使用迭代器）建模任意树

Question

我正在寻找一种方法来建模一个具有任意数量子节点的树。

这个答案建议使用Boost Graph Library来完成这个任务: 什么是好的、稳定的C++树实现? 我需要执行的主要操作是遍历函数（前序、子节点、叶子）和其子树。我还需要从子节点向上收集数据的功能。

BGL是否是正确的选择，如何实现简单树的前序遍历？在文档中，我只能找到有关常规图形的信息。

编辑：我也知道tree.hh库，但它的许可证似乎不适合所有人。

- fuji

---

几年前有一个标准提案，提出了一个完整的STL风格的树库（被拒绝的原因主要是它太大了，而且不基于一个众所周知的库）。你仍然可以找到该提案作者的实现。也许它能满足你的需求。 - Morwenn

该库特别包含一个nary_tree，以及用于先序、后序和中序遍历的迭代器和算法。此外，它还提供了“游标”，以在迭代模型中提供更大的灵活性。值得注意的是，尽管其名称如此，但它并不是Boost的一部分（不确定是否被拒绝或从未提出）。它根据Boost许可证发布，因此无论您想做什么都不应该有许可问题。 - Morwenn

Answer 1

我对这棵树进行了改进。现在，顶点迭代器和边迭代器都被包装在门面中。如果我做出更大的改变，我会发布它们的。我之前为一个小项目使用过tree.hh，但并不是很喜欢它。我将用这个替换它，看看还需要什么。

#include<iostream>
#include <string>
#include <boost/shared_ptr.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/graph/graphviz.hpp>

#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/graph_utility.hpp>

// ..............................................
template< typename Tree >
void write_graphviz( std::ostream& os, Tree tree )
{
    os << "digraph G {\n";
    for( auto it : tree )
        os << it << "[label=\"" << tree[ it ] << "\"];\n";
    for( auto it : tree.get_edges( ) )
        os << it.m_source << "->" << it.m_target << ";\n";
    os << "}\n";
}

// ..............................................
template< typename Tree >
const typename boost::graph_traits< Tree >::vertex_descriptor get_vertex( Tree& tree, const typename Tree::out_edge_iterator& iter ) { return iter->m_target; }

template< typename Tree >
const typename boost::graph_traits< Tree >::vertex_descriptor get_vertex( Tree& tree, const typename Tree::vertex_iterator& iter ) { return *iter; }

// ..............................................
template< typename Tree, typename IteratorType >
class tree_iter_type
    : public boost::iterator_facade<
        tree_iter_type< typename Tree, typename IteratorType >
        ,typename Tree::vertex_property_type
        ,boost::forward_traversal_tag
    >
{
public:
    typedef typename tree_iter_type< typename Tree, typename IteratorType > other_type;
    typedef typename boost::graph_traits< Tree >::vertex_descriptor iterator_value_type;
    typedef typename boost::graph_traits< Tree >::edge_descriptor eiterator_value_type;
    typedef typename Tree::vertex_property_type value_type;
private:
    friend class boost::iterator_core_access;
    value_type& dereference( ) const { return tree[ get_vertex( tree, iter ) ]; }
    void increment( ) { ++iter; }
    bool equal( other_type const& other ) const { return iter == other.iter; }
public:
    tree_iter_type( Tree& tree, IteratorType iter ) : tree( tree ), iter( iter ) { }

    //https://dev59.com/aV0Z5IYBdhLWcg3wnBVS
    other_type& operator=( other_type const& a ){ tree= a.tree, iter= a.iter; return *this; };
    iterator_value_type vertex( ) { return get_vertex( tree, iter ); }
    //how to make this work? It blows things up....
    //iterator_value_type operator ( ) { return get_vertex( tree, iter ); }

private:
    Tree& tree;
    IteratorType iter;
};

// ..............................................
template< typename Tree, typename IterType > //proxy container
class tree_pair_type
{
public:
    typedef typename boost::graph_traits< Tree >::vertex_descriptor vertex_t;
    typedef std::pair< IterType, IterType > iterator_pair_t;
    tree_pair_type( iterator_pair_t pair ) :pair( pair ){ }
    IterType begin( ) { return pair.first; }
    IterType end( ) { return pair.second; }
private:
    iterator_pair_t pair;
};

// ..............................................
template< typename ValueType >
class BGTree
{
public:
    typedef boost::adjacency_list<
        boost::mapS,
        boost::vecS,
        boost::bidirectionalS,
        ValueType >
        tree_t;
    typedef typename ValueType value_type;
    typedef typename boost::graph_traits< tree_t >::vertex_descriptor vertex_t;
    typedef typename boost::graph_traits< tree_t >::edge_descriptor edge_t;

    typedef typename tree_t::vertex_iterator vertex_iterator;
    typedef typename tree_t::edge_iterator edge_iterator;
    typedef typename tree_t::out_edge_iterator out_edge_iterator;

    typedef typename tree_iter_type< tree_t, typename tree_t::out_edge_iterator > out_tree_iterator;
    typedef typename tree_iter_type< tree_t, typename tree_t::vertex_iterator > vertex_tree_iterator;

    typedef tree_pair_type< tree_t, edge_iterator > pair_type;
    typedef tree_pair_type< tree_t, out_tree_iterator > out_pair_type;
    typedef tree_pair_type< tree_t, vertex_tree_iterator > vertex_pair_type;

    //get children
    auto make_out_iterator( vertex_t pos ) { return out_tree_iterator( tree, boost::out_edges( pos, tree ).first ); }
    auto make_out_iterator_end( vertex_t pos ) { return out_tree_iterator( tree, boost::out_edges( pos, tree ).second ); }
    //get sub tree
    auto make_range_iterator( vertex_t pos ) { return vertex_tree_iterator( tree, begin( ) ); }
    auto make_range_iterator_end( vertex_t pos ) { return vertex_tree_iterator( tree, end( ) ); }

public:
    BGTree( const ValueType& root )
        :root( boost::add_vertex( root, tree ) ) {  }

    vertex_t get_root( ) const { return root; }
    vertex_t add_child( const ValueType& item, vertex_t where ) {
        auto temp= boost::add_vertex( item, tree );
        boost::add_edge( where, temp, tree );
        return temp;
    }
    vertex_t get_parent( vertex_t from ) const { return boost::in_edges( from, tree ).first->m_source; }
    auto get_bundle( ) { return boost::get( vertex_bundle, tree ); }
    //vertext set, not by value
    vertex_iterator begin( ) { return boost::vertices( tree ).first; }
    vertex_iterator end( ) { return boost::vertices( tree ).second; }
    ValueType& operator [ ] ( vertex_t at ) { return tree[ at ]; }
    //by index, not by value
    auto get_edges( ) { return pair_type( boost::edges( tree ) ); }

    auto get_children( vertex_t pos= 0 ) {
        return out_pair_type( std::make_pair(
                make_out_iterator( pos ), make_out_iterator_end( pos ) ) );
    }
    auto breadth_first( vertex_t pos= 0 ) {
        return vertex_pair_type( std::make_pair(
            make_range_iterator( pos ), make_range_iterator_end( pos ) ) );
    }
    auto get_vertex_children( vertex_t pos ) { return out_pair_type( boost::out_edges( pos, tree ) ); }
    auto get_boost_graph_tree( ) { return tree; }

private:
    tree_t tree;
    vertex_t root;
};

// .....................................................................................
// .....................................................................................
int main( )
{
    //build tree to match the images in documentation
    //https://en.wikipedia.org/wiki/Tree_traversal
    typedef BGTree< char > char_tree_t;

    char_tree_t tree( 'F' );
    auto last= tree.get_root( );
    last= tree.add_child( 'B' , last );
    tree.add_child( 'A' , last );
    last= tree.add_child( 'D' , last );
    tree.add_child( 'C' , last );
    tree.add_child( 'E' , last );
    last= tree.get_root( );
    last= tree.add_child( 'G' , last );
    last= tree.add_child( 'I' , last );
    last= tree.add_child( 'H' , last );

    // visualization
    std::ofstream os( "./graph.dot" );
    ::write_graphviz( os, tree );

    std::cout << "Pre-order: F, B, A, D, C, E, G, I, H\n";
    for( auto& i : tree.breadth_first( ) )
        std::cout << i << " ";
    std::cout << "\n\n";

    std::cout << "Children of root: B, G\n";
    for( auto& i : tree.get_children( ) )
        std::cout << i << " ";
    std::cout << "\n\n";

    auto it= std::find_if(
        tree.breadth_first( ).begin( ), tree.breadth_first( ).end( ),
        [ ] ( const char& test ) { return test == 'B'; } );
    std::cout << "should be 'B', find_if: " << *it << "\n\n";

    std::cout << "children of 'B' from iterator: A D\n";
    //as it has a referance to tree, could be it.get_children( )?
    for( auto& item : tree.get_children( it.vertex( ) ) )
        std::cout << item << " ";
    std::cout << "\n\n";

    return 0;
}

- lakeweb

---

嗨 @fuji，我已经进行了一些改进，这可能会使它变得实用。从这里开始，添加所需的功能应该很容易。再次感谢。 - lakeweb

Answer 2

Boost图形库是一款强大的库。但对于您而言，在您的情况下，它是一个过于复杂的工具。您只有少量简单操作。您不需要像搜索路径、图的分区等复杂的图形算法。此外，在您的情况下，主要数据结构只是树（不是一般的图！）。在这种情况下，您可以尝试使用以下代码：

#include <iostream>
#include <list>
#include <functional>
#include <memory>

//  TODO: (dev) T should not be pointer type, in such case you will get    memory leak!
//  Wrap it with unique_ptr, or create other specialization, or keep key in unique_ptr
template <typename T>
class Node
{
public:
typedef T key_type;
typedef std::list<Node<T>*> nodes_type;

Node(key_type key) :
    m_key(key)
{
}

template <typename Func>
void process_preorder(Func f) const
{
    f(m_key);
    for (nodes_type::const_iterator loc = m_nodes.begin(); loc != m_nodes.end(); ++loc)
        (*loc)->process_preorder(f);
}

template <typename Func>
void process_children(Func f) const
{
    for (nodes_type::const_iterator loc = m_nodes.begin(); loc != m_nodes.end(); ++loc)
        f((*loc)->m_key);
}

template <typename Func>
void process_leafs(Func f) const
{
    if (m_nodes.empty())
        f(m_key);
    for (nodes_type::const_iterator loc = m_nodes.begin(); loc != m_nodes.end(); ++loc)
        (*loc)->process_leafs(f);
}

Node<T>& add_child(key_type key)
{
    Node<T>* new_node = new Node(key);
    m_nodes.push_back(new_node);
    return *new_node;
}
~Node()
{
    std::cout << "Deletion node with key: " << m_key << std::endl;
    //  Children deletion
    while (!m_nodes.empty())
    {
        delete m_nodes.back();
        m_nodes.pop_back();
    }
}
private:
key_type m_key;
nodes_type m_nodes;
};

int main()
{
{
    typedef Node<int> node_type;
    std::unique_ptr<node_type> n = std::make_unique<node_type>(0);
    {
        for (int i = 1; i <= 3; ++i)
        {
            node_type& current_child = n->add_child(i);
            for (int j = 1; j <= 3; ++j)
                current_child.add_child(i * 10 + j);
        }
    }
    std::function<void(node_type::key_type)> printer = [](const node_type::key_type key) {std::cout << key << std::endl;};
    std::cout << "Printing via preorder" << std::endl;
    n->process_preorder(printer);
    std::cout << "Printing children of node with key: " << std::endl;
    n->process_children(printer);
    std::cout << "Printing leafs" << std::endl;
    n->process_leafs(printer);
}
int i = 0;
std::cin >> i;
return 0;
}

- Alex Aparin

---

我知道，用这种方式实现树是一项容易的任务。另一方面，编写一个尽可能与STL兼容（迭代器）的树并不容易。我希望BGL能够帮助完成这个任务。 - fuji