Из сыновей, для каждого из которых известен отец, составить бинарное дерево

@Hanja · Регистрация: 27.10.2014

Студворк — интернет-сервис помощи студентам

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

Список:
main -
a main
p a
s p
t p
c main
b main
x b
y x
z y
w y
q a

Должно выйти вот так:

main
-a
--p
---s
---t
--q
-b
--x
---y
----z
----w
-c

Не понимаю, как это можно сделать при помощи бинарного дерева. Ведь тут у некоторых отцов больше 2х потомков

@КамазПодарков · 07.11.2014, 19:14

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

@Hanja · 07.11.2014, 19:29 **[ТС]**

Сообщение от КамазПодарков

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

Нет, я знаю, как будет выглядеть структура такого дерева (ну бинарного), но не знаю, как его реализовать на уровне языка.
принцип такой:

Переход на уровень вниз заменяем на переход по левой ветви, а переход по одному уровню - по правой

@КамазПодарков · 07.11.2014, 19:33

Hanja, задачу уточните, тогда. Вдруг вообще можно ребра нарисовать никак не связанными с начальными

@Hanja · 07.11.2014, 19:35 **[ТС]**

Сообщение от КамазПодарков

Hanja, задачу уточните, тогда. Вдруг вообще можно ребра нарисовать никак не связанными с начальными

Трассировка программы, не содержащей рекурсивных
вызовов и повторяющихся имен процедур, распечатана в виде
списка выполняемых процедур. Процедура попадает в список, если
к ней произошло обращение из вызывающей процедуры либо возврат
управления из вызванной ей процедуры. Структура программы
такова, что каждая вызываемая процедура вложена в вызывающую
ее процедуру. Начало и окончание программы должны быть в
головной процедуре. Построить и выдать дерево
вызовов процедур.

@КамазПодарков · 07.11.2014, 19:46

А в чем вопрос? Надо создать небинарное дерево, а потом написать алгоритм, про который вы говорите, получить бинарное.

@Hanja · 07.11.2014, 19:47 **[ТС]**

Сообщение от КамазПодарков

А в чем вопрос? Надо создать небинарное дерево, а потом написать алгоритм, про который вы говорите, получить бинарное.

ну тогда я совершенно не понимаю, как это сделать.

@КамазПодарков · 07.11.2014, 21:21

В списке же вершины по порядку идут?
Я бы делал так:
Деревья вообще реализовывать не надо.
1) Считываете все вершины кладете в map пары вида (х, х) для каждой вершины.
http://www.cplusplus.com/reference/map/map/
map - это множество пар, используется для задания отображения.
2) Проходите по списку, обрабатываете каждый элемент следующим образом:
если идет вершина a с родителем b, то в ответ записываете вершину a с родителем map[b], при этом в самом mape меняете пару (b, x) на (b,a).
В итоге у вас получится список вершин с родителями для модифицированного дерева. В каком виде его надо выводить - решайте сами.

Добавлено через 5 минут
Основная идея вот в чем: у вас сначала идет
a main, значит родителем a в ответе будет main
Но когда вы доходите до следующего потомка main'a вам его уже надо к a пристыковывать. То есть map показывает к кому надо пристыковывать. Может слегка глючный алгоритм я предложил, проверьте.

@TheCalligrapher · 07.11.2014, 21:24

Сообщение от Hanja

Не понимаю, как это можно сделать при помощи бинарного дерева. Ведь тут у некоторых отцов больше 2х потомков

Любое корневое дерево однозначным образом представимо в виде бинарного дерева через следующую элементарную трансформацию:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
отец --+----+----+
  |    |    |    |
  v    v    v    v
сын1 сын2 сын3 сын4
  |
  v
внук1
 
отец 
  | 
  |
  v  
сын1 --> сын2 --> сын3 --> сын4
  |
  |
  v
внук1

@Hanja · 07.11.2014, 23:27 **[ТС]**

Сообщение от TheCalligrapher

Любое корневое дерево однозначным образом представимо в виде бинарного дерева через следующую элементарную трансформацию:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
отец --+----+----+
  |    |    |    |
  v    v    v    v
сын1 сын2 сын3 сын4
  |
  v
внук1
 
отец 
  | 
  |
  v  
сын1 --> сын2 --> сын3 --> сын4
  |
  |
  v
внук1

Об этом я сказал выше, приложив картинку. Все равно спасибо. Но мне именно и нужна помощь с функциями для такого дерева

@КамазПодарков · 07.11.2014, 23:29

Hanja, с ним потом что-то надо сделать или просто вывести?

@Hanja · 08.11.2014, 00:04 **[ТС]**

Сообщение от КамазПодарков

Hanja, с ним потом что-то надо сделать или просто вывести?

просто вывести

@КамазПодарков · 08.11.2014, 00:15

Hanja, Ну тогда мое описание алгоритма должно помочь.
Заводите два std::list'а (входные данные и ответ), std::map, читаете, что это такое и с чем их едят, реализуете простые операции с ними, придумываете, как вывести ответ и все)

@Hanja · 09.11.2014, 20:22 **[ТС]**

Есть список отцов, для каждого отца перечислены все сыновья. Как по этим данным составить дерево? Прошу, помогите

Т.е:
0: 1,6,7
1: 2,5
2: 3,4
3: -
4: -
5: -
6: -
7: 8
8: 9
8: 10,11

Должно получится:

0
*1
**2
***3
***4
**5
*6
*7
**8
***9
****10
****11

Очень нужна помощь, в голову ничего не идет... С деревьями работаю впервые

@_Ivana · 09.11.2014, 20:29

Выбираете любой понравившийся формат данных, позволяющий хранить деревья - в STL обязательно что-то должно быть, я бы просто на сишных указателях написал. Далее заполняете (конструируете) ваше дерево по данным из файла. И наконец, выводите его на печать в показанном виде, рекурсивно проходя его.

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@Hanja 0 / 0 / 0 Регистрация: 27.10.2014 Сообщений: 18

	Из сыновей, для каждого из которых известен отец, составить бинарное дерево 07.11.2014, 17:34. Показов 1302. Ответов 14 Метки нет (Все метки) Очень нужна помощь со следующей задачей: Необходимо из сыновей, для каждого из которых известен отец, составить бинарное дерево. Список: main - a main p a s p t p c main b main x b y x z y w y q a Должно выйти вот так: main -a --p ---s ---t --q -b --x ---y ----z ----w -c Не понимаю, как это можно сделать при помощи бинарного дерева. Ведь тут у некоторых отцов больше 2х потомков 0

@КамазПодарков 5 / 3 / 1 Регистрация: 06.11.2014 Сообщений: 33
	07.11.2014, 19:14
	Ну бинарное вроде и не составишь, надо, думаю, поругаться в ответ. 0

@КамазПодарков 5 / 3 / 1 Регистрация: 06.11.2014 Сообщений: 33
	07.11.2014, 19:33
	Hanja, задачу уточните, тогда. Вдруг вообще можно ребра нарисовать никак не связанными с начальными 0

@КамазПодарков 5 / 3 / 1 Регистрация: 06.11.2014 Сообщений: 33
	07.11.2014, 19:46
	А в чем вопрос? Надо создать небинарное дерево, а потом написать алгоритм, про который вы говорите, получить бинарное. 0

@КамазПодарков 5 / 3 / 1 Регистрация: 06.11.2014 Сообщений: 33
	07.11.2014, 21:21
	В списке же вершины по порядку идут? Я бы делал так: Деревья вообще реализовывать не надо. 1) Считываете все вершины кладете в map пары вида (х, х) для каждой вершины. http://www.cplusplus.com/reference/map/map/ map - это множество пар, используется для задания отображения. 2) Проходите по списку, обрабатываете каждый элемент следующим образом: если идет вершина a с родителем b, то в ответ записываете вершину a с родителем map[b], при этом в самом mape меняете пару (b, x) на (b,a). В итоге у вас получится список вершин с родителями для модифицированного дерева. В каком виде его надо выводить - решайте сами. Добавлено через 5 минут Основная идея вот в чем: у вас сначала идет a main, значит родителем a в ответе будет main Но когда вы доходите до следующего потомка main'a вам его уже надо к a пристыковывать. То есть map показывает к кому надо пристыковывать. Может слегка глючный алгоритм я предложил, проверьте. 0

@КамазПодарков 5 / 3 / 1 Регистрация: 06.11.2014 Сообщений: 33
	07.11.2014, 23:29
	Hanja, с ним потом что-то надо сделать или просто вывести? 0

@КамазПодарков 5 / 3 / 1 Регистрация: 06.11.2014 Сообщений: 33
	08.11.2014, 00:15
	Hanja, Ну тогда мое описание алгоритма должно помочь. Заводите два std::list'а (входные данные и ответ), std::map, читаете, что это такое и с чем их едят, реализуете простые операции с ними, придумываете, как вывести ответ и все) 0

@Hanja 0 / 0 / 0 Регистрация: 27.10.2014 Сообщений: 18
	09.11.2014, 20:22 [ТС]
	Есть список отцов, для каждого отца перечислены все сыновья. Как по этим данным составить дерево? Прошу, помогите Т.е: 0: 1,6,7 1: 2,5 2: 3,4 3: - 4: - 5: - 6: - 7: 8 8: 9 8: 10,11 Должно получится: 0 1 2 3 4 5 6 7 8 9 10 **11 Очень нужна помощь, в голову ничего не идет... С деревьями работаю впервые 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,988 Записей в блоге: 32
	09.11.2014, 20:29
	Выбираете любой понравившийся формат данных, позволяющий хранить деревья - в STL обязательно что-то должно быть, я бы просто на сишных указателях написал. Далее заполняете (конструируете) ваше дерево по данным из файла. И наконец, выводите его на печать в показанном виде, рекурсивно проходя его. 0