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

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

памяти

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

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

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