>>262
漏れは、各ノードに「親ノードへのポインタ」と「子ノードへのポインタのリスト」を持つようにした。
struct tree {
　　tree* parent;
　　std::list<tree*> children;
　　T value;
};
実際にはstructではなくclassで、各メンバはprivateにした上でアクセサを定義。
イテレータとして
1. 子ノードイテレータ
　typedef std::list<tree*> children_type;
　typedef typename children_type::iterator children_iterator;
2. preorder_iterator（begin()、end()で先頭・末尾の次を取得でき、全ノードを前置順走査する）
3. postorder_iterator（rbegin()、rend()で先頭・末尾の次を取得でき、全ノードを後置順走査する）
を用意。tree::iteratorにpreorder_iteratorをtypedefしておく。
子ノードの追加はoperator+, +=、削除はoperator-, -=

これにストリーム入出力つけて300行くらい。でもコード見たらboost::iterator_facade使ってた。