Вот эта тема навеяла мысль создать контейнер для хранения данных в виде дерева. Вот я и набросал, если так можно сказать, односвязное дерево. Это значит, что движение возможно лишь от корня и от первого элемента, но не в обратных порядках.

Итак, описание
tree<T> Tree; - создаёт контейнер дерева, который хранит элементы типа T
tree<T>::iterator i; - объявляем итератор (на самом деле над ним надо работать, он не функционирует пока как итератор)
Tree.addChild(T x); - добаляет новый элемент в корень дерева
Tree[0].addChild(T x); - добаляет новое детё первому элементу в корне дерева
Tree[0].addNext(T x); - раздвинуть элементы и впихнуть после Tree[0] новый элемент
i->push_back(T x); - Добавить элемент в конец, на том же уровне, что и итератор i. Не совсем традиционно, будем думать.
Новигация
i->getNext(); - Если i - это итератор, то оператор вернёт следующий элемент, того же уровня, или ноль если последний. Оператор ++ пока не работает
i->getChild(); - Ну, а это детё, или ноль, если детей нет

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

Вот файл определения контейнера:
tree.h

Код

template <class T> class tree_item; template <class T> class tree { private: tree_item<T>* root; public: tree() { root = 0; } ~tree() { delete root; } typedef tree_item<T>* iterator; typedef tree_item<T>& reference; iterator addChild(const T a) {  if(root == 0)  {   root = new tree_item<T>(a);   return root;  }  else   return root->push_back(a); } reference operator[](unsigned i) {  tree_item<T> *item = root;  while(i--)   item = item->getNext();  return *item; } }; template <class T> class tree_item { private: tree_item *nextItem, *childItem; T data; public: tree_item(const T a) { nextItem = 0; childItem = 0; data = a; }                //Деструктор интересный получился. Мне нравится.                ~tree_item() {  if(childItem) delete childItem;  if(nextItem) delete nextItem; }                    tree_item& operator=(const T x) { data = x; return *this; } operator T() { return data; } tree_item& operator[](unsigned i) {  tree_item *item = childItem;  while(i--)   item = item->nextItem;  return *item; } tree_item* addNext(const T a) {  tree_item* item = new tree_item(a);  item->nextItem = nextItem;  nextItem = item; } tree_item* push_back(const T a) {  tree_item *last = this;  while(last->nextItem)   last = last->nextItem;  last->nextItem = new tree_item(a);  return last->nextItem; } tree_item* addChild(const T a) {  if(childItem == 0)  {   childItem = new tree_item(a);   return childItem;  }  else   return childItem->push_back(a); } inline tree_item* getNext() { return nextItem; } inline tree_item* getChild() { return childItem; } };

Вот пример использования

Код

#include <iostream.h> #include <string> #include "tree.h" using namespace std; void print(tree<string>::iterator i); void main() { tree<string> Tree; // Заполняем дерево (взял из книги по AutoCAD оглавление, рядом лежала) Tree.addChild("1. О системе AutoCAD 2002 в целом"); Tree[0].addChild("1.1 Назначение системы"); Tree[0].addChild("1.2 Требования к вычислительной среде"); Tree[0].addChild("1.3 Установка системы"); Tree[0][2].addChild("1.3.1 Для программиста"); Tree.addChild("2. Элементы интерфейса"); Tree[1].addChild("2.1 Строка меню"); Tree[1][0].addChild("2.1.1 Меню File"); //Вывод на консоль print(&Tree[0]); } void print(tree<string>::iterator i) { while(i) {  cout << string(*i).c_str() << endl;  if(i->getChild())   print(i->getChild());  i = i->getNext(); } }

Вот. Надо класс итератора ещё написать, удаление реализовать. Потом можно будет контейнер двусвязный сделать и т.д.

RAN, я бы сначала поискал в Сети примерчики, может народ уже давно это реализовал. Но суть моего поста не в этом. А в том, что в STL уже реализовано дерево для "внутреннего потребления", т.е. для нужд других классов STL.

(Раньше здесь был БОЛЬШОЙ кусок кода из STL )

Это сообщение отредактировал(а) mr.DUDA - 7.9.2003, 11:37

ЗЫ, в STL от Хьюлетт Паккарда файлец называется "Xtree", в StlPort - это пара "_tree.h" и "_tree.c". Сбалансированное двоичное дерево (красный и черный "цвета" и прочее).

ЗЫ(2), это всё не ради выпендрёжа, просто реализацию произвольного дерева можно делать не с нуля, а взять куски STL'овского сорца. Особенно помочь это может в геморе с итераторами и пр.

ЗЫ(3), своего варианта пока что не придумал...

Ну, ладно. Только ты так больше не делай. Тебе надо было просто написать, что это уже реализовано. Что сам ты пока не разобрался в том, как пользоваться, но вот файлы в STL. Я и все кому интересно вглянули бы туда. А так ты опубликовал ни о чём не говорящие выдержки из кода. Я думаю, начинающих программистов ты уже перепугал и они в эту тему не зайдут .

Цитата

я бы сначала поискал в Сети примерчики, может народ уже давно это реализовал

Вот, нашёл. А можно было самим реализовать . Может лучше бы было .