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