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

@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 обязательно что-то должно быть, я бы просто на сишных указателях написал. Далее заполняете (конструируете) ваше дерево по данным из файла. И наконец, выводите его на печать в показанном виде, рекурсивно проходя его.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

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

	Из сыновей, для каждого из которых известен отец, составить бинарное дерево 07.11.2014, 17:34. Показов 1334. Ответов 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,991 Записей в блоге: 32
	09.11.2014, 20:29
	Выбираете любой понравившийся формат данных, позволяющий хранить деревья - в STL обязательно что-то должно быть, я бы просто на сишных указателях написал. Далее заполняете (конструируете) ваше дерево по данным из файла. И наконец, выводите его на печать в показанном виде, рекурсивно проходя его. 0