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

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

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

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



Это сообщение отредактировал(а) 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