我已经对此树进行了改进。顶点迭代器和边缘迭代器现在都包装在外观中。如果我做出更多重大更改,我会发布它们。我曾经使用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) { }
//http://stackoverflow.com/questions/31264984/c-compiler-error-c2280-attempting-to-reference-a-deleted-function-in-visual
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;
}
对于完整的STL风格树库,有一个[标准提案](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3700.html)几年前(它被拒绝了,主要是因为它很大,并不是基于一个知名的图书馆)。您仍然可以通过提案的作者找到[实施](https://github.com/grafikrobot/boost-tree)。也许它会满足你的需求。 – Morwenn
该库特别包含一个'nary_tree'以及迭代器和算法,用于预定序列,后序序列和中序遍历。此外,它还提供了*游标*以在迭代模型中提供更多的灵活性。它还糟糕地注意到,尽管它的名字,它不是提升的一部分(不知道它是否被拒绝或从未提出过)。它是在Boost许可证下发布的,所以你不应该有许可问题,不管你想用它做什么。 – Morwenn