Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>Нужна она для представления иерархически организоанной информации (файлы на диске, XML, да что угодно!)
Вот теперь правильная формулировка.
ЗХ>Внимание, вопрос:
ЗХ>КТО КАКИЕ КЛАССЫ ИСПОЛЬЗУЕТ, когда сталкиваеться с такой структурой. Теоретически, такое бывает надо довольно часто.
Я лично предполагаю, что для каждой задачи делается своя структура данных, это совсем не сложно.

ЗХ>Струтура данных "дерево" нужна бывает довольно часто.
ЗХ>Внимание, вопрос: кто какую реализацию использует? такое ощущение, что все уже нашли свой идеал... (Впечатление такое оттого, что в "Исходниках" на деревья реагируют крайне слабенько)

Я когда то сам писал. Но по малолецтву.

Здравствуйте, Зверёк, Вы писали:

ЗХ> Струтура данных "дерево" нужна бывает довольно часто.
ЗХ> Внимание, вопрос: кто какую реализацию использует?

Реализация большая, а интерфейс более-менее такой:

template<class NodeT, class EdgeT>
class Tree : public TreeTraits<NodeT>::template EdgeTraits<EdgeT>::TreeBase
{
  typedef typename
    TreeTraits<NodeT>::template EdgeTraits<EdgeT>::TreeBase Base_;

public:

  // Construction
  // ============

  Tree();
  Tree(const Tree<NodeT, EdgeT>&);

public:

  // Types
  // =====

  typedef NodeT Node;
  typedef EdgeT Edge;

#if 0  // exposition only

  // Node != void
  // ------------

  typedef NodeIterator                  NodeIterator;
  typedef ConstNodeIterator             ConstNodeIterator;
  typedef ReverseNodeIterator           ReverseNodeIterator;
  typedef ConstReverseNodeIterator      ConstReverseNodeIterator;

  typedef AdjacencyIterator             AdjacencyIterator;
  typedef ConstAdjacencyIterator        ConstAdjacencyIterator;
  typedef ReverseAdjacencyIterator      ReverseAdjacencyIterator;
  typedef ConstReverseAdjacencyIterator ConstReverseAdjacencyIterator;

  typedef NodeDepthWalker               NodeDepthWalker;
  typedef ConstNodeDepthWalker          ConstNodeDepthWalker;

  // Edge != void
  // ------------

  typedef EdgeIterator                  EdgeIterator;
  typedef ConstEdgeIterator             ConstEdgeIterator;
  typedef ReverseEdgeIterator           ReverseEdgeIterator;
  typedef ConstReverseEdgeIterator      ConstReverseEdgeIterator;

  typedef EdgeDepthWalker               EdgeDepthWalker;
  typedef ConstEdgeDepthWalker          ConstEdgeDepthWalker;

public:

  // Attributes
  // ==========

  // True if graph has no nodes. Complexity: O(1).
  bool empty() const;

  // True if is equal to other tree. Complexity: O(N) * O(log N).
  bool equal(const TreeN<NodeT>&) const;

  // The number of nodes in the tree. Complexity: O(N).
  Size n_nodes() const;

  // The number of edges in the tree. Complexity: O(N).
  Size n_edges() const;

  // Node != void
  // ------------

  // True if node is local source, i.e. has no ingoing edges. Complexity: O(1).
  bool in_empty(ConstNodeIterator) const;

  // True if node is local sink, i.e. has no outgoing edges. Complexity: O(1).
  bool out_empty(ConstNodeIterator) const;

  // In-degree of the node. Complexity: O(1).
  Size in_degree(ConstNodeIterator) const;

  // Out-degree of the node. Complexity: O(N).
  Size out_degree(ConstNodeIterator) const;

  // Degree of the node. Complexity: O(N).
  Size degree(ConstNodeIterator) const;

  // First node. Complexity: O(1).
  NodeIterator      nodes_begin();
  ConstNodeIterator nodes_begin() const;

  // End of the nodes. Complexity: O(1).
  NodeIterator      nodes_end();
  ConstNodeIterator nodes_end() const;

  // Root of the tree. Complexity: O(1).
  NodeIterator      root();
  ConstNodeIterator root() const;

  // Parent of the node. Complexity: O(1).
  NodeIterator      parent(NodeIterator) const;
  ConstNodeIterator parent(ConstNodeIterator) const;

  // Determines whether two nodes are adjacent,
  // i.e. the tree has an edge(n1, n2). Complexity: O(1).
  bool adjacent(ConstNodeIterator n1, ConstNodeIterator n2) const;

  // Determines whether the descendant is reachable from ancestor,
  // i.e. there's a path of any length from ancestor to descendant.
  // Complexity: O(N) / O(log N).
  bool reachable(ConstNodeIterator ancestor,
                 ConstNodeIterator descendant) const;

  // First child of the node. Complexity: O(1).
  AdjacencyIterator      children_begin(NodeIterator) const;
  ConstAdjacencyIterator children_begin(ConstNodeIterator) const;

  // End of node's children. Complexity: O(1).
  AdjacencyIterator      children_end(NodeIterator) const;
  ConstAdjacencyIterator children_end(ConstNodeIterator) const;

  // If adjacent(parent, child) returns appropriate adjacency iterator
  // otherwise returns children_end(parent). Complexity: O(1).
  AdjacencyIterator      adjacency(NodeIterator parent, NodeIterator child) const;
  ConstAdjacencyIterator adjacency(ConstNodeIterator parent, ConstNodeIterator child) const;

public:

  // Operations
  // ==========

  // Erase all the nodes and edges. Complexity: O(N).
  void clear();

  // Node != void
  // ------------

  // Insert root node. If tree is not empy, its root
  // becomes child of new node. Complexity: O(1).
  NodeIterator insert(const NodeT&);

  // Insert root branch. If tree is not empy,
  // its root becomes child of new node. Complexity: O(N).
  NodeIterator insert(const TreeN<NodeT>&, ConstNodeIterator);

  // Insert node to parent. Complexity: O(1).
  NodeIterator insert(NodeIterator parent, const NodeT&);

  // Insert child to parent before pos. Complexity: O(1).
  NodeIterator insert(NodeIterator parent, AdjacencyIterator pos, const NodeT&);

  // Insert branch to parent. Complexity: O(N).
  NodeIterator insert(NodeIterator        parent,
                      const TreeN<NodeT>& tree,
                      ConstNodeIterator   node);

  // Insert branch to parent before pos. Complexity: O(N).
  NodeIterator insert(NodeIterator        parent,
                      AdjacencyIterator   pos,
                      const TreeN<NodeT>& tree,
                      ConstNodeIterator   node);

  // Insert range [begin, end) of branches to parent.
  // Complexity: O(N).
    void insert(NodeIterator            parent,
                const TreeN<NodeT>&     tree,
                ConstAdjacencyIterator  begin,
                ConstAdjacencyIterator  end);

  // Insert range [begin, end) of branches to parent before pos.
  // Complexity: O(N).
  void insert(NodeIterator            parent,
              NodeIterator            pos,
              const TreeN<NodeT>&     tree,
              ConstAdjacencyIterator  begin,
              ConstAdjacencyIterator  end);

  // Erase node and all incident edges, all its children are erased too.
  // Complexity: O(N).
  void erase(NodeIterator node);

  // Erase nodes range, all incident edges and children are erased too.
  // Complexity: O(N).
  void erase(AdjacencyIterator begin, AdjacencyIterator end);

  // Contract edge (n1, n2), i.e. remove edge and replace it's
  // source and terminal nodes with new one.
  // Complexity: O(1).
  NodeIterator contract(NodeIterator n1, NodeIterator n2, const NodeT&);

  // Subdivide edge (n1, n2), i.e. insert node n, insert two
  // edges (initial(e), n) and (n, terminal(e)), and remove original edge.
  // Complexity: O(1).
  NodeIterator subdivide(NodeIterator n1, NodeIterator n2, const NodeT&);

  // Take over another node's child. All iterators remain valid.
  // Complexity: O(1).
  void take_over(NodeIterator parent,
                 TreeN<NodeT>&, NodeIterator child);

  void take_over(NodeIterator parent, AdjacencyIterator pos,
                 TreeN<NodeT>&, NodeIterator child);

  // Take over another node's children. All iterators remain valid.
  // Complexity: O(N).
  void take_over(NodeIterator parent,
                 TreeN<NodeT>&, AdjacencyIterator begin, AdjacencyIterator end);

  void take_over(NodeIterator parent, AdjacencyIterator pos,
                 TreeN<NodeT>&, AdjacencyIterator begin, AdjacencyIterator end);

#endif // exposition only
};

// non-members
// ===========

template<class NodeT, class EdgeT>
bool operator ==(const Tree<NodeT, EdgeT>&, const Tree<NodeT, EdgeT>&);

template<class NodeT, class EdgeT>
bool operator !=(const Tree<NodeT, EdgeT>&, const Tree<NodeT, EdgeT>&);

> Начнем с начала.
>
> Существует структура данных, которая определяется таким образом:
> у каждого элемента 0..N потомков. Один корень.
> Если я еще не все перезабыл, то это, стало быть, ациклический направленный граф с одной корневой вершиной.
> Хорошо.
> Нужна она для представления иерархически организоанной информации (файлы на диске, XML, да что угодно!)
> Внимание, вопрос:
> КТО КАКИЕ КЛАССЫ ИСПОЛЬЗУЕТ, когда сталкиваеться с такой структурой. Теоретически, такое бывает надо довольно часто.
извини, но не вникал в вопрос, но чтобы не изобретать самокат, вот несколько ссылок уже на готовые деревья:
www.damtp.cam.ac.uk/user/kp229/tree/
www.codeproject.com/vcpp/stl/wrk.asp
www.lsp.ups-tlse.fr/Chafai/libtree.html
www.research.att.com/sw/tools/graphviz/
www-h.eng.cam.ac.uk/help/tpl/talks/C++graphs.html
www.cs.queensu.ca/home/dalamb/courses/235/slides/thread.html

надеюсь, что это поможет

Здравствуйте, Зверёк Харьковский, Вы писали:

ЗХ>в ней. никаких свер-возможностей не надо.
ЗХ>просто, есть классы, хранящиеся деревом (каталоги-подкаталоги, и все такое)
ЗХ>нужно

ЗХ>

ЗХ>1. возможность обойти дерево (итератор)
ЗХ>2. возможность обойти только данную ветку (итератор')
ЗХ>3. возможность добавить-удалить потомков к ветке.
ЗХ>

ЗХ>неужели никому такое не надо?

Дык несложно...

(Начал писать, и понял, что не столько несложно, сколько чертовски рутинно, если подходить грамотно.
Вот что я нарожал в приступе программизма — посмотрите, может что-то полезное найдёте может, не зря я это делал )

// стратегии контейнера
struct use_vector
{
  template<class T> struct uses { typedef std::vector<T> type; };
};
struct use_list
{
  template<class T> struct uses { typedef std::vector<T> type; };
};
template<size_t N>
struct use_array
{
  template<class T> struct uses { typedef boost::array<T,N> type; };
};
// и элемента: мы считаем, что в коллекции детей хранится нечто, подобное указателю
// но не обязательно являющееся моделью Указатель (T*, shared_ptr<T>), 

template<class T>
struct valueptr
{
  T value_;
  T* operator->() { return &value_; }
  T& operator*() { return value_; }
}

struct use_pointer
{
  template<class T> struct uses { typedef T* type; };

  struct make { template<class T> void operator()(T*& var) const { var = new T(); } };
  struct kill { template<class T> void operator()(T*& var) const { delete var; var = NULL; } };
};
struct use_value
{
  template<class T> struct uses { typedef T type; };

  struct make { template<class T> void operator()(T& var) const {} };
  struct kill { template<class T> void operator()(T*& var) const {} };
};
struct use_sharedptr
{
  template<class T> struct uses { typedef boost::shared_ptr<T> type; };

  struct make { template<class T> void operator()(boost::shared_ptr<T>& var) const { var = new T(); } };
  struct kill { template<class T> void operator()(boost::shared_ptr<T>& var) const { var = NULL; } };
};

// узел дерева - это...
template<class T,
   class container_policy=use_vector,
   class item_policy=use_pointer,
   > // заметьте: use_array несовместим с use_value
class treenode
{
public:
  typedef T item_type;
  typedef treenode<T,container_policy,item_policy> self_type;

  typedef item_policy<self_type>::type child_type;
  typedef container_policy<child_type>::type container_type;

private:
  self_type* parent_;
  container_type children_;

public:
  // далее буду опускать соответствующие константные методы

  self_type* parent() const { return parent_; }
  container_type& children() { return children_; }

  template<class It, class E> // E - это ±const self_type
  class iterator_base : iterator<iterator_traits<It>::iterator_category, E>
  {
    It it_;
  public:
    iterator_base() {}
    iterator_base(It it) : it_(it) {}

    E& operator*() const { return *item_policy::take(*it_); }
    E* operator->() const { return item_policy::take(*it_); }
  };

  typedef iterator_base<children_type::iterator, self_type> iterator;
  typedef iterator_base<children_type::const_iterator, self_type> const_iterator;

  iterator begin() { return children_.begin(); }
  iterator end() { return children_.end(); }

  // соответственно, reverse_iterator...

public:
  treenode() : parent_(NULL) {}
  treenode(size_t n) : parent_(NULL) { resize(n); }

private:
  void setparent(self_type* p) { parent_ = p; }

  friend struct setparent_there;
  struct setparent_there
  {
    self_type* p_;
    setparent_there(self_type* p) : p_(p) {}
    void operator()(self_type& t) const { t.setparent(p); }
  };

public:
  size_t size() const { return children_.size(); }
  void resize(size_t n)
  {
    size_t s = size();
    if(s < n) // сотрём лишнее
    {
      reverse_iterator i=rbegin(); advance(i,n-s);
      for_each(rbegin(),i, setparent_there(NULL));
      for_each(rbegin(),i, item_policy::kill());
    }
    children_.resize(n);
    if(s > n) // создадим новое
    {
      reverse_iterator i=rbegin(); advance(i,n-s);
      for_each(rbegin(),i, item_policy::make());
      for_each(rbegin(),i, setparent_there(this));
    }
  }
};

ЗХ>Струтура данных "дерево" нужна бывает довольно часто.
ЗХ>Внимание, вопрос: кто какую реализацию использует? такое ощущение, что все уже нашли свой идеал... (Впечатление такое оттого, что в "Исходниках" на деревья реагируют крайне слабенько)
Загляни в boost, там есть Boost Graph Library.

Переформулирую вопрос еще раз:
Я не столько просил подарить мне исходник дерева, сколько пытался понять:
насколько часто у людей возникает такой вопрос?
есть ли одно решение, которое удовлетворяет всех?
(почему, скажем, в бусте такого нет? неужто настолько никому не надо? только не надо про буст::граф, использовать его как простое дерево не слишком удобно)

да, и кстати, оцените уж и мой вариант (малость извращенческий ):
http://rsdn.ru/Forum/Message.aspx?mid=535054&only=1

Автор: Зверёк Харьковский
Дата: 11.02.04

Здравствуйте, Кодт, Вы писали:

К>Дык несложно...

лихо!
а обход всего дерева?

(а как тебе вот эдакий вариянт: http://rsdn.ru/Forum/Message.aspx?mid=535054&only=1

Автор: Зверёк Харьковский
Дата: 11.02.04

)

Здравствуйте, Зверёк Харьковский, Вы писали:

ЗХ>Я не столько просил подарить мне исходник дерева, сколько пытался понять:
ЗХ>насколько часто у людей возникает такой вопрос?

Я думал, думал... и не придумал, для чего мне может понадобится обобщённый вариант дерева.
В том случае, когда мне нужна была древовидная структура, я быстро сооружал её из подручных средств.

Здравствуйте, ArtDenis, Вы писали:

AD>Здравствуйте, Зверёк Харьковский, Вы писали:

ЗХ>>Я не столько просил подарить мне исходник дерева, сколько пытался понять:
ЗХ>>насколько часто у людей возникает такой вопрос?

AD>Я думал, думал... и не придумал, для чего мне может понадобится обобщённый вариант дерева.
AD>В том случае, когда мне нужна была древовидная структура, я быстро сооружал её из подручных средств.

я хитрее
посмотри тот вариант, который в моем предыдущем сообщении.
там хранит детей и за их добавление-удаление-сортировку отвечает клиент, а дерево — это тонкая оберька над ним — предоставляет только итераторы для обхода.

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>Здравствуйте, Зверёк, Вы писали:

ЗХ>> Струтура данных "дерево" нужна бывает довольно часто.
ЗХ>> Внимание, вопрос: кто какую реализацию использует?

ПК>Реализация большая, а интерфейс более-менее такой:
а реализацию? жалько?

Здравствуйте, Зверёк, Вы писали:

ПК>> Реализация большая, а интерфейс более-менее такой:

ЗХ> а реализацию? жалько?

Не жалко а муторно... Если после всех ранее вываленных в этом топике
деревьев все еще хочется чего-нибудь другого, можно, конечно, и попробовать
изолировать от остальных кусков библиотеки. Оно, действительно, надо?
В смысле, если кто-нибудь будет пользоваться, можно и выложить. Но, чё-то
гложут меня сомнения, что при наличии кучи аналогичных классов, кому-то нужен
еще один

Здравствуйте, Serginio1, Вы писали:

S> А все что ты пишешь это не деревья, а связные списки.

Точно-точно! Классика жанра: CONS-пара (car.cdr) в лиспе. Этого ваще достаточно.

Список (x1 x2 ... xn1 xn) представляется конс-деревом (x1 . (x2 . (... . (xn1 . (xn . NIL))...)))

Дерево представляется списком списков.

Однако, в конс-паре нет указателя на этаж выше. Поэтому итерируемое дерево на лиспе будет сделать сложно.
Впрочем, нет ничего невозможного. Итератор сам может содержать список — путь до текущего узла. Инкремент сводится к следующим действиям:
* если есть дети — добавить в путь индекс первого ребёнка
* если нет детей, но есть следующий сосед — заменить в пути последний индекс следующим
* пока нет больше соседей и путь не пуст — отбрасывать последний индекс

Здравствуйте, Зверёк Харьковский, Вы писали:

ЗХ>Переформулирую вопрос еще раз:
ЗХ>Я не столько просил подарить мне исходник дерева, сколько пытался понять:
ЗХ>насколько часто у людей возникает такой вопрос?

У нас (олимпиадники-программисты) часто.

ЗХ>есть ли одно решение, которое удовлетворяет всех?

Ага. Наш кодер помнит (уже на рефлексах) AVL и декартовы деревья, просто деревья реализуются
им по мере надобности одной рукой с завязанными глазами не приходя в сознаник.

ЗХ>(почему, скажем, в бусте такого нет? неужто настолько никому не надо? только не надо про буст::граф, использовать его как простое дерево не слишком удобно)

Я когда-то кидал в "Исходники" сырой вариант дерева. Его попинали немного и привели в пристойный вид.

Здравствуйте, Зверёк Харьковский, Вы писали:

ЗХ>внутреннее представление не сильно важно (на данном этапе), важно -- класс с интерфейсом дерева!

Да, кстати, а какой должен быть интерфейс класса, чтобы его можно было использовать для всего многообразия деревьев?

Здравствуйте, Зверёк Харьковский, Вы писали:

ЗХ>Струтура данных "дерево" нужна бывает довольно часто.

Я бы еще добавил: и разная.

Ну т.е. в модели файловой системы узлы уникально именованные.
И операции поиска-обхода сугубо специфические.
То же самое и с XML — имплементация должна быть своя.
Про HTML я вообще молчу. Там лес, лесополоса и посевы мака квадратно-гнездовым способом.
Дерево это как правило некий DOM, а на этом DOMе еще много чего висит.

Например в HTML итераторы есть такие char_visitor, word_visitor, paragraph_vistor, floaters_visitor, text_line_visitor и еще до чертиков всякой визиторской лабуды. А координаты? Вообще полный привет.

Т.е. дерево как конструкция (parent)(children)* это только одна из проекций.

Мне кстати пришлось от iteratora в чистом виде уходить.
Оперции типа move_next (++) move_prev(--) пришлось делегировать самим объектам DOM.
Сам термин "позиция итератора" в лесу, в дереве и на маковом поле оченно разные.

Вот.