Как реализовать дерево на основе связного списка?

Question

[Axretit]

Нужно реализовать дерево на основе связного линейного списка. Насколько это возможно?

Comments

[Alexandroppolus]

Что значит дерево на основе списка? У бинарного дерева и двусвязного списка элементы по сути одинаковы - содержат значение и две ссылки. Из таких элементов можно составить дерево, но будет ли это "на основе списка"?
Вот на основе массива - запросто: для i-го элемента есть два чилда - [2i+1] и [2i+2].

[Axretit]

Alexandroppolus, Если бы я знал больше информации о том, что мне нужно сделать - я бы несомненно добавил ее. Получил задание сделать на основе списка, на вопрос "что значит на основе списка?" получил ответ: сделай как поймешь, а там посмотрим :)

Я вот и думаю, либо должен быть просто указатель на родителя и при реализации не использовать рекурсию, а пользоваться лишь указателями но - это же бред...
Либо создать связи так, чтобы можно было пройти по дерево в любом направлении и в итоге создать и не дерево, и не список, а "монстра"

Answer 1

[Wataru]

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

Возможно, вам надо хранить детей каждой вершины в виде связного списка (тогда у вас будет куча списков). Еще, популярный подход (фактически делающий то же самое) - это хранить в каждой вершине ссылку/указатель на первого ребенка и на следующего брата. Так все списки будут перемешаны в одну большую структуру. Но тут, правда, в отличии от связного списка, все равно есть 2 типа ссылок.

Comments

[Axretit]

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

[Wataru]

Axretit, Ну да, вы как дерево ни храните, оно останется деревом. Вершина Б так и будет ребенком А. Принципиально ничего не поменяется. Можно дальше уже думать, какой способ храния вам удобнее и быстрее для вашей задачи. Если дерево не меняется, то самый быстрый и удобный способ - хранить детей в виде массива в каждой вершине. Еще лучше все эти массивы объеденить в один и в вершине хранить только начало и конец ее куска. Если вы дерево постепенно собираете, можете добавлять или удалять вершины, вырезать поддеревья, то уже имеет смысл хранить детей в виде связных списков в каждой вершине. Объединить все в одну структуру может быть выгоднее из-за возможности ручного управления памятью.

Answer 2

[Василий Дёмин]

У каждого элемента списка может быть либо один последующий, либо ноль. Вероятно, вам нужно на указателях реализовать.

Если уж прямо нужно на списках, то можно нумеровать элементы списка и в каждом хранить потомков.
Как-то так:
список:

1. [2, 3]
   
2. [4, 5]
   
3. []
   

Answer 3

[res2001]

Дерево на основе связного списка это вообще первое что приходит в голову, когда думаешь, как реализовывать дерево. Правда это не обычный последовательный связный список, а иерархический.

Comments

[Axretit]

Нужна реализация на последовательном

[res2001]

Axretit, Можете использовать последовательный список так же как массив в комментарии Alexandroppolus https://qna.habr.com/q/1098806#clarification_1406260
Но, конечно, работать будет мягко говоря не быстро, т.к. список не поддерживает индексацию, поэтому придется каждый раз обходить список для достижения нужного узла.
Если это в учебных целях, то почему бы и нет, раз препод хочет.

[Axretit]

res2001, В том то и дело, что я ломаю голову над тем, что в данном случае просто пропадает сам смысл бинарного дерева. Получается просто конвертер который из бинарного дерева при помощи обхода все элементы в список записывает

[res2001]

Axretit, чтоб был просто конвертер вам нужно дерево, чтоб из него переносить элементы в список.
Да, смысла в подобном дереве не много, но в качестве учебной - вполне не плохая задача.
В целом подход такой же как в дереве на основе массива, нужен готовый список из минимального количества элементов, каждый элемент должен содержать признак пустой он или нет, получение элемента по индексу через обход элементов с начала. При разрастании дерева нужно добавлять сразу такое количество элементов, чтоб влазил весь следующий уровень дерева.
Кстати, какой ЯП планируете использовать?