Форум программистов, компьютерный форум CyberForum.ru

Деревья - C++

Восстановить пароль Регистрация
 
Mike_J
0 / 0 / 0
Регистрация: 09.02.2010
Сообщений: 3
09.02.2010, 17:13     Деревья #1
Ребята!очень нужна помощь!Никак не могу догнать как решить задачки:

1) Определить какие поддеревья являются пирамидами
2) Найти поддерево, не включающее ни одной из заданной вершин
3) Найти поддеревья,структура которых совпадает с заданной...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.02.2010, 17:13     Деревья
Посмотрите здесь:

деревья на С++ C++
деревья C++
C++ деревья
C++ Деревья
Б+ деревья C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
JKeeJ1e30
12 / 12 / 0
Регистрация: 04.02.2010
Сообщений: 45
09.02.2010, 17:40     Деревья #2
2) очень просто. берешь корень, его детей, относительно каждого из детей смотришь сколько у каждого из детей ненужных вершин. Если у какого-то ребенка этих вершин меньше, чем у этого ребенка его детей(ну то есть по отношению к первой вершине-внуков)-значит, будет такой внук у которого в след поколениях не будет ненужных вершин. Если такого ребенка нет-идешь по внукам и то же самое. Операций-не больше n^3(n-колво вершин)
3) опять же идешь сверху вниз и в один массив помечаешь на каком уровне располагается вершина, в другой-количество ее детей, и в третий-самих детей пишешь. Потом считаешь сколько уровней должно быть в поддереве, ну и дальше-дело техники-найти на нужном уровне такую вершину, которая будет корнем такого поддерева. Тут если не ошибаюсь можно и за n^2
Mike_J
0 / 0 / 0
Регистрация: 09.02.2010
Сообщений: 3
09.02.2010, 17:52  [ТС]     Деревья #3
всё равно не очень понимаю,эта тема - глухой лес длоя меня...Ты не мог бы привести листинг?Если,конечно,не трудно...Заранее премного благодарен!
JKeeJ1e30
12 / 12 / 0
Регистрация: 04.02.2010
Сообщений: 45
09.02.2010, 18:29     Деревья #4
Короче
1) Что отличает дерево от обычного графа:
дерево всегда можно нарисовать так, чтобы была ветвящаяся структура(отсюда и название) которая исходит ровно из одной вершины(представь палки, воткнутые в одну точку. Это будет простейшим деревом, у которой все вершины будут "сыновьями" этой точки(вершинами будут концы палок). Теперь на вершины этих палок насади другие, это уже будет более сложная структура, но так же называющаяся деревом. Помни просто что каждый конец палок-это вершина. Вкурил?). Дальше буду обьяснять именно на примере простой структуры.
2) корень(или отец, или старший предок)-это та вершина дерева, с которой вся структура начинается(собственно, та точка в земле, в которой все палки зарыты).
3) сыновья-для отца(для точки, из которой торчат все палки)-это, собственно, все остальные вершины.

Че еще непонятно?

Добавлено через 4 минуты
а да забыл. Уровень вершины-это сколько вершин нужно пройти от отца до данной вершины. Для простейшего дерева(все, кроме отца, являются сыновьями) для всех вершин(кроме, разумеется, отца) уровень равен еденице
Mike_J
0 / 0 / 0
Регистрация: 09.02.2010
Сообщений: 3
09.02.2010, 18:30  [ТС]     Деревья #5
спасибо!Попробую что-нибудь сотворить
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
10.02.2010, 07:51     Деревья #6
Mike_J, рекурсию юзь.
apple1988
0 / 0 / 0
Регистрация: 29.03.2011
Сообщений: 24
04.04.2011, 12:46     Деревья #7
Объясните, пожалуйста, как хранить деревья...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2011, 16:31     Деревья
Еще ссылки по теме:

C++ Деревья
C++ Деревья
деревья C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
04.04.2011, 16:31     Деревья #8
Например, как поле-значение узла и массив указателей на потомков.
Yandex
Объявления
04.04.2011, 16:31     Деревья
Ответ Создать тему
Опции темы

Текущее время: 10:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru