Как построить бинарное дерево с помощью списка смежности?

Question

[Вячеслав Осипов]

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

Answer 1

[Сергей Горностаев]

Обходом естественно.

Comments

[Вячеслав Осипов]

Можно поподробнее

[Сергей Горностаев]

Вячеслав Осипов, а какие вам подробности нужны? Алгоритм обхода?

[Вячеслав Осипов]

Каким именно образом дерево будет строиться с помощью обхода

[Сергей Горностаев]

Вячеслав Осипов, дерево - это частный случай ациклического графа. Выберите удобную вам структуру для дерева. Так как граф неориентированный, просто берите произвольную вершину и начинайте обход, складывая вершины в выбранную структуру. В конце обхода в этой структуре будет дерево. Правда, не обязательно сбалансированное.

[longclaps]

студент-математик Вячеслав Осипов, в заголовке вопроса упомянуто бинарное дерево, дальше это слово не упоминается. Да еще и

Вопрос с проверкой( является ли граф деревом) решен

Так оно у тебя бинарное?
И да, где код?

[Вячеслав Осипов]

longclaps, 1) Да , оно бинарное. 2) Зачем он тут?

Answer 2

[SerJook]

Я так понимаю, на входе у вас массив, содержащий списки соседей(индексы) для каждой вершины графа.

Берите любую вершину, у которой кол-во соседей меньше либо равно двум, и назначаете ее корнем.
Для любой вершины корнем левого поддерева будет первый сосед в списке (если есть), который не совпадает с родительским. Рекурсивно строите левое поддерево.
Корнем правого поддерева будет второй сосед в списке (если есть), который не совпадает с родительским.
Рекурсивно строите правое поддерево.

В итоге получите несортированное несбалансированное бинарное дерево