Я пытаюсь написать программу, которая первоначально получит число узлов, которые будут заданы в следующих строках, и желаемую высоту всего создаваемого двоичного дерева, с 2D-координатами этих узлов в следующих строках.,
Затем он попытается построить приемлемое полное двоичное дерево с теми двумерными координатами, в которых не допускается пересечение двух ребер.(Пример ниже).
Если такое дерево существует, оно должно возвращать номер позиции каждого узла в таком дереве (где 1 является корнем, а все остальные узлы нумеруются постепенно сверху вниз ислева направо) в том же порядке, в котором узлы пришли на вход, а узлы, которые не используются в дереве, должны быть пронумерованы 0. Если такого дерева вообще не существует, оно должно вывести: «Нет полного двоичного файладерево здесь!
Я пробовал деревья дальности и деревья kd безрезультатно, так как у меня возникают трудности с попыткой обернуть голову, как проверить, можно ли построить дерево под любым углом, например, когда оно спускается внизось X или Y, или любая другая линия в этом отношении.Я был бы признателен за любой подход, который вы могли бы предложить.
Пример ввода:
9 2
(100,300)
(200,300)
(500,301)
(200,200)
(300,201)
(400,203)
(500,206)
(300,101)
(402,100)
Соответствующий вывод:
4, 1, 0, 2, 0, 3, 6, 5, 7
Для наглядного представления о том, что я имею в виду, выможете взглянуть на это изображение:
Заранее благодарим за всю вашу помощь.