Через что лучше реализовывать бинарное дерево: через список или динамический массив?

Question

[Chemodan228]

Через что лучше реализовывать бинарное дерево: через список или динамический массив?

Answer 1

[GavriKos]

Через структуры и указатели.

Comments

[Chemodan228]

Это же список?

[Кот Абсолютный]

Illia Nezhyhai, Ну, если уж подходить строго - это именно двусвязный линейный список. Классическая форма реализации бинарного дерева, кстати.

[Chemodan228]

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

[Кот Абсолютный]

Chemodan228, Надо - используйте, кто мешает? :)

[wisgest]

CityCat4:

двусвязный линейный список. Классическая форма реализации бинарного дерева

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

Поэтому, частью ответа на исходный вопрос: дерево через список реализовать никак нельзя. Что касается массива и указателей, то принципиальной разницы нет: можно хранить узлы дерева в выделенном под это массиве и в качестве указателей на другие узлы использовать их индексы и, наоборот, рассматривать всю память как один большой массив и указатели — как индексы элементов в нём.