Подходящий выбор представления дерева в первую очередь определяется видом операций, выполняемым над деревьями. В частности, можно использовать методы последовательного распределения памяти, отображающие связи на физическое размещение данных. Такой способ годится, когда требуется компактное представление дерева, и оно не будет подвергаться радикальным динамическим изменениям в процессе работы программы. Он заключается в том, что опускается поле Left или Right, а последовательное расположение узлов замещает опущенную связь. Структура узла имеет вид:
struct NODE{
<поля данных>;
NODE *Right;
bool HaveLeftSon;
};
Хранится только правая связь. Левый сын узла, если он есть, расположен в памяти сразу за данным. Поле HaveLeftSon имеет значение true, если узел имеет левого сына. Узлы в памяти хранятся в порядке прямого обхода. На рис. 26. изображено дерево и его представление в последовательной памяти. Угловая скобка справа внизу от узла означает отсутствие левого сына.
Возможно также последовательное размещение узлов дерева в концевом и обратном порядке.
Можно также предложить чисто последовательное размещение узлов дерева в памяти, когда сыновья узла с адресом X имеют адреса 2*Xи 2*X+1.Память при этом расходуется крайне непроизводительно.
Рис. 26. Альтернативное представление бинарного дерева
