Представление бинарных деревьев на

Рис. 67. Представление бинарного дерева на статической памяти

Представление бинарных деревьев на статической

памяти

Если известен максимальный размер дерева (т.е. высота, а следовательно, и количество узлов, соответствующих полному дереву), то структуру дерева можно хранить в виде массива. При этом корень дерева будет храниться в элементе массива с индексом [1]. Для каждого узла с номером k его левый потомок будет хранится в элементе с индексом [2 * k], а правый - в элементе с индексом [2 * k + 1] (см. рис. 67).

Достоинством представления бинарных деревьев на статической памяти является простота доступа как от предка к потомку, так и от потомка к предку, а недостатком - то, что если дерево не является полным, в массиве появляется большое число пустых элементов. Ограниченный размер массива не позволяет включать в дерево новые узлы, т.е. дерево не может “расти”. Удаление узла из дерева и соответствующее изменение его структуры потребует модификации содержимого массива.

динамической памяти

Элемент хранения узла бинарного дерева состоит из одного или нескольких информационных полей и двух полей связи, указывающих соответственно на левое и правое поддеревья данного узла.

Type
PTree = ^ Tree;	{ тип – указатель на узел дерева }
Tree = record	{ тип – элемент хранения узла дерева}
info: char;	{ информационное поле }
left, right: PTree	{ ссылки на поддеревья }
End;
Var Root: PTree;	{ указатель на корень дерева }

Дерево задается указателем на его корень. Если дерево пусто, указатель на его корень равен NIL. Связанное представление бинарного дерева иллюстрирует рис. 68.