Tree

#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <queue>
#include <algorithm>
#include <boost/ptr_container/ptr_vector.hpp>
#include <boost/ptr_container/serialize_ptr_vector.hpp>
#include <boost/archive/text_oarchive.hpp>
#include <boost/archive/text_iarchive.hpp>

template <typename T>
struct Tree
{
    Tree(): Data(), Childs() {};
    Tree(const T& rhs): Data(rhs), Childs() {}
    Tree(T&& rhs): Data(rhs), Childs() {}

    void addChild(const Tree<T>& rhs)
    {
        this->Childs.push_back(new Tree<T>(rhs));
    }

    void addChild(Tree<T>&& rhs)
    {
        this->Childs.push_back(new Tree<T>(rhs));
    }
    /*
    template <typename Fn>
    void Traversal(Fn fn, unsigned depth=0)
    {
        fn(Data, depth);
        std::for_each(Childs.begin(), Childs.end(), boost::bind(&Tree::Traversal<Fn>, _1, fn, depth+1));
    }
    */
    template <typename Fn>
    void DFS(Fn fn)
    {
        std::stack<std::pair<std::pair<boost::ptr_vector<Tree>::iterator, boost::ptr_vector<Tree>::iterator>, unsigned> > s;
        fn(Data, 0);
        s.push(std::make_pair(std::make_pair(Childs.begin(), Childs.end()), 1));
        while (true)
        {
            if (s.top().first.first != s.top().first.second)
            {
                fn(s.top().first.first->Data, s.top().second);
                s.push(std::make_pair(std::make_pair(s.top().first.first->Childs.begin(), s.top().first.first->Childs.end()), s.top().second+1));
            }
            else
            {
                s.pop();
                if (s.empty())
                    break;
                ++s.top().first.first;
            }
        }
    }

    template <typename Fn>
    void BFS(Fn fn)
    {
        std::queue<std::pair<std::pair<boost::ptr_vector<Tree>::iterator, boost::ptr_vector<Tree>::iterator>, unsigned> > q;
        fn(Data, 0);
        q.push(std::make_pair(std::make_pair(Childs.begin(), Childs.end()), 1));
        do
        {
            for (boost::ptr_vector<Tree>::iterator it=q.front().first.first; it!=q.front().first.second; ++it)
            {
                fn(it->Data, q.front().second);
                q.push(std::make_pair(std::make_pair(it->Childs.begin(), it->Childs.end()), q.front().second+1));
            }
        }
        while (q.pop(), !q.empty());
    }

    template <typename Archive>
    void serialize(Archive& ar, const unsigned version)
    {
        ar & Data & Childs;
    }

    T Data;
    boost::ptr_vector<Tree> Childs;
};

void print(const std::string& str, unsigned depth)
{
    while (depth--)
        std::cout << '\t';
    std::cout << str << std::endl;
}

int main()
{
    typedef Tree<std::string> str_Tree;

    str_Tree root("Root");
    {
        str_Tree node1("Node 1");
        node1.addChild(str_Tree("Leaf 1"));
        node1.addChild(str_Tree("Leaf 2"));
        node1.addChild(str_Tree("Leaf 3"));
        root.addChild(std::move(node1));
    }
    root.addChild(str_Tree("Leaf 4"));
    {
        str_Tree node2("Node 2");
        node2.addChild(str_Tree("Leaf 5"));
        node2.addChild(str_Tree("Leaf 6"));
        {
            str_Tree node21("Node 2_1");
            node21.addChild(str_Tree("Leaf 7"));
            node21.addChild(str_Tree("Leaf 8"));
            node2.addChild(std::move(node21));
        }
        node2.addChild(str_Tree("Leaf 9"));
        root.addChild(std::move(node2));
    }
    root.addChild(str_Tree("Leaf 10"));

    root.DFS(print);
    root.BFS(print);
    return 0;
}