Идея такая, нужно дерево с неизвестным количеством классов потомков.
То есть у меня дерево, размеры которого нужно менять и количество потомков каждого потомка тоже, по желанию.

Ну у меня идея сделать полем дерева список, а дальше что, в общем, у кого какие едеи, поделитесь.

Читай:Двоичное дерево

например так:



Это сообщение отредактировал(а) korian - 11.3.2008, 17:32

korian, стандартные контейнеры не предназначены для наследования,
Каждый узел бинарного дерева может содержать произвольное количество потомков, несмотря на то, что указателя всего 2... просто у дерева рекурсивная природа, и потомки определенного узла, находятся в различных отношениях друг с другом, они упорядочены.То-есть мы можем взять любой узел и определить как он соотносится с каждым из своих потомков.  А если сделать список, то это уже сложно будет внятно использовать... смысла такая структура не имеет  


Это сообщение отредактировал(а) Lazin - 12.3.2008, 08:44

а я бы всё-таки делал контейнер (список, вектор или ещё что-либо, в зависимости от параметров задачи) потомков в каждом узле
с помощью бинарного дерева, конечно, можно реализовать любое другое, только это не означает, что нужно

P.S.
начать стоит с того, чтобы подумать, как было бы удобно работать с этим деревом, например, написать несколько фрагментов кода, как будто дерево уже реализовано, оттуда и плясать

Это сообщение отредактировал(а) maxim1000 - 11.3.2008, 18:14

это где такое написано?

то что я предложил, является деревом с произвольным количеством child'ов и любой глубины.

короче, что-то я, наверно, не понял задачу и до сих пор не понимаю.


Это сообщение отредактировал(а) korian - 11.3.2008, 19:08

Я обычно делаю так. Действительно беру за основу контейнер типа vector. Создаю свою структуру добавляю членом - контейнер, объявляю другие необходимые структуры, которые также могут содержать контейнеры и через new выделяю указатели, которые и пихаю в контейнеры. Потом пробегаюсь по контейнерам и вызываю delete на указатели структур. Поэтому удобно вынести это в класс, удаление добавить в деструктор. А в конструкторе можно формировать само дерево.

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

Tree t; - корень дерева
t.push_back(Tree()); - добавляем дочерний узел
t.begin()...t.end() - дочернии узлы узла t;
t.data - данные, соответствующие узлу t;
(*(*t.begin()).begin()) - дочерний узел дочернего узла узла t;
и не надо самому заморачиваться с выделением/удалением памяти.

что еще надо?

Это сообщение отредактировал(а) korian - 11.3.2008, 22:05

хранить вектор из просто узлов, а не указателей чревато большими накладными расходами:
если у нас есть большое дерево, и мы хотим добавить где-то на верхнем уровне ещё один узел, операция push_back время от времени будет приводить к перевыделению памяти и копированию всех элементов
если дерево большое, безобидная операция может сильно затянуться
ну а если не хочется помнить об освобождении памяти, можно использовать умные указатели...

Добавлено через 7 минут и 44 секунды
касательно наследования от вектора:
у него нет виртуального деструктора
это значит, что возможна такая ситуация:
A наследуется от std::vector
где-то создаётся объект класса A
потом куда-то передаётся по указателю на std::vector
потом к нему кто-то применяет delete
из-за отсутствия виртуального деструктора у вектора, деструктор A и его полей не будет вызван, что может вызвать проблемы

тут, конечно, никто не предполагает, что объекты будут уничтожаться через указатель на вектор, но в большинстве более-менее долго разрабатываемых программ появится ситуация, когда это покажется удобным

чаще всего если можно сделать композицией или наследованием, лучше делать композицией - проще получается...

решаеться заменой vector на list


ну это просто необходимо помнить
или проще класс Tree обернуть в что-то подобное умного указателя, и не давать создавать/уничтажать объект пользователям, чтобы не возникали проблемы с этим.


Это сообщение отредактировал(а) korian - 11.3.2008, 23:55

Если честно, я с контейнерами не знакома.
Вот щас почитаю, конечно. Если можно, разьясните мне преимущества контейнера в данном случае.
korian, вы все верно поняли, мне дейсвительно это и нужно:



Если вам не очень трудно, дайте мне побольше пояснений как это будет работать, я с контейнерами не работала.
Простите за беспокойство   

там ошибка была и заменим vector на list



только в том, что класс дерево создается 5-ю строчками.


переписывать хелп по контейнерам нету желания
поищите, думаю на форуме много примеров использования <list>
основное, как использовать это дерево я писал выше.
по конкретным функциям могу ответить...

Это сообщение отредактировал(а) korian - 12.3.2008, 04:02

стандартные контейнеры не предназначены для наследования еще и по тому что у них нет protected членов, то-есть наследуя от вектора или списка мы по сравнению с композицией ничего не выигрываем, а только добавляем зависимость, так-как теперь код работающий с Tree зависит от интерфейса контейнера, что не есть гуд... вообще наследованием увлекаться не стоит
подробно это описано у Мейерса...
хранить в контейнере лучше все-таки указатели, желательно умные)), так-как элементы контейнера не обязательно будут простыми структурами, возможно узлом дерева будет что-то имеющее таблицу виртуальных функций))

теперь о деревьях...

      5
    /   \
  2     7
  /\    /\
 1 4 6  9

вот упорядоченное бинарное дерево.. теперь вопрос, а как может быть упорядочено дерево с более чем 2-мя потомками.. объясните мне))

единственное применение, на мой взгляд, это всякие иерархические структуры данных, элементы которых находятся в отношениях родитель - потомок, например GUI библиотеки... там элемент управления(кнопка например) может принадлежать другому элементу управления и при удалении родителя должен быть удален и потомок. Или например DOM представление XML документа...

Зачем героически преодолевать собственные грабли, если их можно банально не разбрасывать?

потому что написание дерева с нуля, содержит на много больше граблей, включая и эти (или похожие).


Это сообщение отредактировал(а) korian - 12.3.2008, 16:28

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

тогда уж проще использовать просто list<T>, который будет сортироваться за то-же время что и твое дерево
к тому-же узел дерева у которого есть итераторы, методы insert, push_back и тд. выглядит не как узел дерева, а как список(он и есть список)

вот вставила в прогу кусок с листом, ошибки...

Compiling...
Tree.cpp
1>d:\toncitos\tree\tree\metreestruct.h(11) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
1>        d:\toncitos\tree\tree\metreestruct.h(19) : see reference to class template instantiation 'Tree_C<T>' being compiled
1>d:\toncitos\tree\tree\metreestruct.h(11) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
1>        d:\toncitos\tree\tree\tree.cpp(111) : see reference to class template instantiation 'Tree_C<T>' being compiled
1>        with
1>        [
1>            T=int
1>        ]
1>Generating Code...
1>Compiling...
1>TreeView.cpp
1>Generating Code...
1>Compiling...
1>AddNewChild.cpp
1>MainFrm.cpp
1>TreeDlg.cpp
1>TreeDoc.cpp
1>Generating Code...
1>Compiling...
1>MeTreeStruct.cpp
1>d:\toncitos\tree\tree\metreestruct.h(11) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
1>        d:\toncitos\tree\tree\metreestruct.h(19) : see reference to class template instantiation 'Tree_C<T>' being compiled

Это сообщение отредактировал(а) tonchitos - 12.3.2008, 23:38

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

обратите, пожайлуста, внимание:
template <class T>
class Tree : public std::list<Tree<T> >

Tree<int> t;
можна написать как:
list<list<list<list.....<list<int> > >......> t; //(возможно бесконечное число вложений. хотя так его описать нельзя, т.к. к каждому листу еще надо присоединить int data)

извените конечно, но узел он и есть список.
можна конечно делать такое дерево (узел содержит 3 списка).
struct node
{
    node* next;
    node* firstChild;
    node* parent;
}

но если устраивает такое (что у меня вообщем то и есть):
struct
{
    node* firstChild;
}
т.е. единственно, узел не знает о родителе и соседних клетках, а в большинстве случаев в этом нету необходимости (обход дерева идет с корня).
а если все же надо передвигаться по дереву снизу вверх, можна добавить в класс Tree инфу о родителе.


это дерево может работать с любыми данными


дайте листинг кода и номер строки на которой ошибка.

Это сообщение отредактировал(а) korian - 12.3.2008, 18:12

ошибка тут

operator < (const Tree_C<T> & node) {return data < node.data};

код? у мя проект большой.... только если весь проект.
Тк в этом файле ниче кроме этого контейнера.


Я так и не пойму как это ботает, ну разьясните плиз.

примерчик еще хочу

operator < (const Tree_C<T> & node) {return data < node.data};
тут ; не там стоит
operator < (const Tree_C<T> & node) {return data < node.data;}

листинг я имел ввиду, листинг класса Tree
и строку как объявлен объект класса.

не помогло...

создание бинарного дерева, по типу, как это делалось тут: http://forum.vingrad.ru/forum/topic-200066.html



Добавлено через 2 минуты и 20 секунд
дайте вот это:
листинг я имел ввиду, листинг класса Tree
и строку как объявлен объект класса.
что за компилятор
и вообще, ICQ есть? а то сейчас это все растянется на кучу страниц.

понял в чем ошибка, плюс нашел еще одну, из-за которой сортировка не могла работать.

на работе мне предложили так:



тут с ошибками...

чем этот вариант лучше или хуже?

Добавлено @ 23:33
korian, ваш вариант загружается таки теперь   

Это сообщение отредактировал(а) tonchitos - 12.3.2008, 23:34

лучше, тем что названия функций имеют осмысленные названия.
а хуже тем, что используеться vector (про это раньше писалось, чем плохо), и в данном варианте жесткая привазка к нему.
все остальное, можна сказать, один к одному 

мне сказали что лист не имеет ф-ии childs.size(); в отличие от вектора.
  

size у листа есть, у него нету доступа к елементам по индексу

ясно...

и еще, я понимаю, что надоела уже наверно.

Но как лучше сохранить в файл это дерево?
  

Ситуация А) мы создаём дерево и наследуем его от list'а, это приводит к нарушению инкапсуляции так как теперь дерево может запросто быть преобразовано в list, там где это не надо.

Ситуация Б) мы создаём дерево и не наследуем его от list'а, это не приводит к нарушению инкапсуляции так как теперь дерево не может запросто быть преобразовано в list, там где это не надо.

Инкапсуляцию вижу, грабли  не обнаружены. 


Грабли вижу, инкапсуляция не обнаружена. Меня как пользователя дерева не колышет что есть у листа а что нет. Если у него нет доступа к i-ому элементу, это его личные проблемы. меня как пользователя дерева они вообще не должны  волновать.


Не надо вводить человека в заблуждение. PImpl сюда прикручивается в несколько пинков, а с ним клиентский код ВООБЩЕ не будет зависеть от листов/векторов/деков.   В случае с наследованием от листа/вектора/дека сделать код не зависимым от базового типа НЕВОЗМОЖНО в принципе. Поэтому про жесткую привязку --- это относится к наследованию нежели к композиции.

Mayk, то есть вы за тот пример который мне на работе предложили?

Да, мы за него. Он значительно лучше наследования. И он не зависит от вектора в том смысле, что когда ты работаешь с деревом, ты всегда можешь 
использовать GetChild(), а не соображать "а реализован ли operator[] у вектора или позавчера мы заменили vector на list и поэтому наш tree[4] сегодня валится с дымом и едким запахом"

Это сообщение отредактировал(а) Mayk - 13.3.2008, 10:39

на тот случай, если под аргументами против вектора понимаются мои слова, то поясню конкретнее:
дело не в том, вектор или список или ещё что-то
дело в том, что хранится в контейнере
если что-то запихиваешь в вектор, нужно быть готовым к копированию этого объекта
и если дерево будет большим, это может привести к неожиданным и непонятным оверхедам

так что при условии использования вектора я бы посоветовал хранить в нём указатели (обычные или умные - другой вопрос), чтобы избежать ненужного копирования больших объёмов данных

Это сообщение отредактировал(а) maxim1000 - 13.3.2008, 12:58

перегружаю оператор =.
почему то ошибка.

не пойму где:





Это сообщение отредактировал(а) tonchitos - 13.3.2008, 14:01

оператор присваивания обычно выглядит так:

и вот здесь:

нужно написать вот так

если не заменить vector<Node> на vector<Node*> как сказал maxim1000, то делать оператор присваивания большого смысла нет --- компилятор и сам напишет.

вот пример, но он сохраняет банально текст.

Это сообщение отредактировал(а) tonchitos - 13.3.2008, 16:49

ответьте уже кто нить!

плиз   

Прочитав лекцию Mayk, хочу согласиться с тем, что включение контейнера в класс намного лучше наследования.
В свое оправдание могу лишь сказать, что на тот момент, я не рассматривал такой вариант. (вариант предложен не был, а мой моск до этого чета не дошел    ).
В варианте с наследованием, все проблемы можна решить, но по сравнению с вариантом композиции, это действительно будет "героическое преодоление собственных граблей".
По поводу жесткой привязки, я имел ввиду то, что данная реализация, а именно доступ к элементу по индексу, привязывает к вектору. Если уходить от вектора к листу из-за перевыделения памяти, то получаем увеличенное время для доступа к элементу.


в каком виде его сохранить то надо?

мне тут один человек предложил следующий вариант: