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

Построение сильноветвящегося дерева потомков человека - C++

Восстановить пароль Регистрация
 
CursorXP
0 / 0 / 0
Регистрация: 10.07.2014
Сообщений: 7
10.07.2014, 14:30     Построение сильноветвящегося дерева потомков человека #1
Всех приветствую.
Сам текст задания:
Нужно построить дерево потомков человека. Дерево является сильноветвящимся. Каждый узел содержит информацию о человеке (фамилия, имя, отчество, пол, количество детей) и ссылку на множество его потомков. Информация вводится с клавиатуры или текстового файла. Необходимо определить, сколько потомков каждого пола было у родоначальника династии. Для заданного человека (из данной династии) вычислить количество его детей, внуков и правнуков.

В общем, нужна помощь именно в в функции добавления узлов сильноветвящегося дерева, так как я до этого занимался только бинарными. Примерный алгоритм такой: создаём первый узел, запоминаем количество его потомков. Создаём первого потомка, также запоминаем количество его потомков, и так пока у созданного узла будет 0 потомков. Затем на как-то надо подниматься на уровень выше и создавать братьев. Ну, далее понятно.
Вот как это реализовать в коде я не представляю. Именно функцию добавление узла, а остальные дела с поисками, я думаю, разберусь.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
10.07.2014, 14:45     Построение сильноветвящегося дерева потомков человека #2
в чем проблема то? вместо одного значения узла, храните вектор значений.
когда добавляете нового потомка (у него обязательно должен быть родитель), ищите родителя, и добавляйте к родителю этого потомка.
CursorXP
0 / 0 / 0
Регистрация: 10.07.2014
Сообщений: 7
10.07.2014, 16:14  [ТС]     Построение сильноветвящегося дерева потомков человека #3
Kukurudza, Я не очень понял, что вы имеете в виду. Смотрите.
Построение сильноветвящегося дерева потомков человека
Цифры - количество детей.
Вот спустился я до Олега и вижу, что детей 0, но у Федора 2-е детей, значит у Олега есть брат, но как это поймёт программа?
И дальше, когда я дошёл до Павла, как мне вернуться к Федору? Ведь никаких указателей на родителей у детей нет.
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
10.07.2014, 16:19     Построение сильноветвящегося дерева потомков человека #4
а с какого это перепуга в данном дереве у олега 0, когда у него есть сын денис? или это внебрачный сын?
зачем от павла возвращаться к федору?
AlexVRud
413 / 142 / 36
Регистрация: 04.07.2014
Сообщений: 413
10.07.2014, 16:47     Построение сильноветвящегося дерева потомков человека #5
Первое, что бросается в глаза
Цитата Сообщение от CursorXP Посмотреть сообщение
фамилия, имя, отчество, пол, количество детей
не являются уникальным набором, нужно вводить, например, id.

Всех ссылки на все добавленные объекты людей храни в одном std::map от id, это позволит быстро находить родителей, и хранить лес, а не только дерево.

В каждом узле храни std::vector ссылок на детей (его размер и будет количеством детей).

Для решения задачи количества потомков по полу используй стандартный алгоритм рекурсивного обхода дерева.
CursorXP
0 / 0 / 0
Регистрация: 10.07.2014
Сообщений: 7
10.07.2014, 17:00  [ТС]     Построение сильноветвящегося дерева потомков человека #6
Kukurudza, Это не сын, а брат. Всё что на одном уровне - братья.
AlexVRud, ну да, ФИО могут повторяться, но ид в задании не сказано, а значит мне нельзя его использовать. Про вектор, то есть у каждого сделать несколько указателей на своих детей?
AlexVRud
413 / 142 / 36
Регистрация: 04.07.2014
Сообщений: 413
10.07.2014, 17:03     Построение сильноветвящегося дерева потомков человека #7
Ну да, храни вектор ссылок
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
10.07.2014, 18:01     Построение сильноветвящегося дерева потомков человека #8
Цитата Сообщение от CursorXP Посмотреть сообщение
Kukurudza, Это не сын, а брат.
Че? вы сами понимаете что там нарисовано?
Цитата Сообщение от CursorXP Посмотреть сообщение
Всё что на одном уровне - братья.
а то я не знал
CursorXP
0 / 0 / 0
Регистрация: 10.07.2014
Сообщений: 7
10.07.2014, 19:48  [ТС]     Построение сильноветвящегося дерева потомков человека #9
Kukurudza,
Че? вы сами понимаете что там нарисовано?
Конечно, ведь я это рисовал.
Все братья на одной высоте.

AlexVRud,
Ну да, храни вектор ссылок
А, так я же не знаю заранее сколько будет детей.
zer0mail
2187 / 1870 / 187
Регистрация: 03.07.2012
Сообщений: 6,656
Записей в блоге: 1
10.07.2014, 22:29     Построение сильноветвящегося дерева потомков человека #10
Используй бинарное дерево. Левый подузел - старший сын, правый подузел - брат. Пояснение: левая стрелка указывает вниз, правая - вправо :)
AlexVRud
413 / 142 / 36
Регистрация: 04.07.2014
Сообщений: 413
11.07.2014, 00:56     Построение сильноветвящегося дерева потомков человека #11
Цитата Сообщение от CursorXP Посмотреть сообщение
А, так я же не знаю заранее сколько будет детей.
А std::vector на то и рассчитан, у него есть метод push_back
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
11.07.2014, 06:21     Построение сильноветвящегося дерева потомков человека #12
zer0mail, CursorXP, то ли вы какую-то фигню говорите, то ли я чего-то невкуриваю.
C++
1
2
3
4
struct node {
    std::vector<node*> children_;
    std::string my_name_;
};
хотим добавить нового? замечательно. у этого нового обязательно должно быть имя родителя и собственно свое имя. идем в корень дерева (надеюсь очевидно, что указатель на корень всегда должен быть доступен?), рекурсивно обходим все узлы, в поисках родителя. если находим родителя, пушаем в вектор родителя еще одного сына (надеюсь очевидно, что именно того, которого хотим добавить?), если такого родителя нет, то извиняйте, вы не наш родственник, в нашем дереве вам не бывать и наследство вы не получите.
Миниатюры
Построение сильноветвящегося дерева потомков человека  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.07.2014, 06:29     Построение сильноветвящегося дерева потомков человека
Еще ссылки по теме:

Построение бинарного дерева C++
Построение В*-дерева C++
Рекурсивное построение дерева C++

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

Или воспользуйтесь поиском по форуму:
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
11.07.2014, 06:29     Построение сильноветвящегося дерева потомков человека #13
В приведенном примере (на картиночке):
корень дерева, пусть его зовут

Виктор. Это родоначальник династии. У него три потомка (два сына и дочь): Валерий, Андрей, Екатерина.
У Валерия два потомка (сын и дочь): Марина и Александр.
У Марины два потомка (два сына): Петька и Женька оба раздолбаи.

У Андрея один потомок (дочь): Мария.

У Екатерины три потомка (три дочки (все три красавицы)): Татьяна, Ольга и Юлия.
У Татьяны один потомок (тоже дочка): Анастасия.
Yandex
Объявления
11.07.2014, 06:29     Построение сильноветвящегося дерева потомков человека
Ответ Создать тему
Опции темы

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