Конспект установочных лекций по комплексному курсу Информатика, Теория информации

       

Представление деревьев массивами


В машине дерево может быть представлено в виде списка. В этом представлении для хранения дерева требуется дополнительное место для указателей на поддеревья в вершинах. Однако дерево можно так же представить в виде массива, для чего следует расположить дерево в массиве по слоям.

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



Содержание раздела