Другие представления бинарных деревьев

Подходящий выбор представления дерева в первую очередь определяется видом операций, выполняемым над деревьями. В частности, можно использовать методы последовательного распределения памяти, отображающие связи на физическое размещение данных. Такой способ годится, когда требуется компактное представление дерева, и оно не будет подвергаться радикальным динамическим изменениям в процессе работы программы. Он заключается в том, что опускается поле Left или Right, а последовательное расположение узлов замещает опущенную связь. Структура узла имеет вид:

struct NODE{

<поля данных>;

NODE *Right;

bool HaveLeftSon;

};

Хранится только правая связь. Левый сын узла, если он есть, расположен в памяти сразу за данным. Поле HaveLeftSon имеет значение true, если узел имеет левого сына. Узлы в памяти хранятся в порядке прямого обхода. На рис. 26. изображено дерево и его представление в последовательной памяти. Угловая скобка справа внизу от узла означает отсутствие левого сына.

Возможно также последовательное размещение узлов дерева в концевом и обратном порядке.

Можно также предложить чисто последовательное размеще­ние узлов дерева в памяти, когда сыновья узла с адресом X имеют адреса 2 * X и 2*X+1. Память при этом расходуется крайне непрои­зводительно.

Рис. 26. Альтернативное представление бинарного дерева

Дата добавления: 2014-12-08