2020-04-07
103
Для программной реализации бинарных деревьев чаще всего используют динамические структуры данных, в которых каждый узел управляется записью из 2-х адресных и требуемого числа информационных полей. Адресные поля узла предназначены для хранения адресов левого и правого потомков. При отсутствии левого или правого потомка соответствующим адресным полям узла можно присвоить нулевые значения (NULL). Адресные поля имеют тип указатель на узел бинарного дерева. Информационные поля узлов могут иметь произвольный тип. Они используются для хранения данных и ключей в узлах бинарного дерева. Диаграмма логической структуры узла бинарного дерева представлена на следующем рисунке.
|
Рис. 6. Логическая структура узла бинарного дерева
При создании нового узла бинарного дерева в динамической реализации, из кучи распределяется область памяти, объем которой необходим для хранения всех полей его логической структуры. Адрес области памяти, выделенной для нового узла, сохраняется в соответствующем (левом или правом) адресном поле предка.
|
|
|
Динамическое распределение узлов по адресным полям предков позволяет конструировать бинарные деревья с желаемой иерархической структурой информационных полей.
Например, на следующем рисунке приведена логическая структура динамической реализации семантического дерева грамматического разбора арифметического выражения: 7+6*4.
|
Рис. 7. Логическая структура бинарного дерева
