Если степени узлов дерева различны, то метод полных узлов приводит к напрас-
ному расходованию большого количества памяти. Для построения дерева, изобра-
женного на рис. 6.5, с помощью этого метода каждому узлу требуется присвоить по
шесть указателей на дочерние узлы, хотя только в одном из них используются все
шесть. Для представления этого дерева пона-
добится 72 указателя на дочерние узлы, из ко-
торых в действительности будут работать все-
го 11.
Некоторые программы позволяют добав-
лять и удалять узлы, изменяя степень узлов
в процессе своего выполнения. В этом случае
метод полных узлов не подходит. Такие дина-
мически изменяющиеся деревья можно пред-
ставить, поместив все дочерние узлы в списки.
Существует несколько способов для построе-
ния списков дочерних узлов. Рис. 6.5. Дерево с узлами различных степеней
Один из них - организовать в классе узла
общедоступный массив дочерних узлов с изме-
няемым размером, как показано в следующем фрагменте кода. Чтобы управлять дочерними узлами, можно использовать методы работы со списками на основе массива.
type
PNAryNodeArray = ^ТNАгуNodeArray;
TNAryNode = class(TObject)
private
public
NumChildren : Integer;
Children : PNAryNodeArray;
..
end;
Альтернативный подход заключается в том, чтобы хранить указатели на до-
черние узлы в связанных списках. Каждый узел содержит указатель на первого
потомка, а также на следующего потомка на том же уровне дерева. Эти связи обра-
зуют связанный список дочерних узлов, поэтому я назвал эту методику представ-
лением связанных потомков (linked sibling).
Опубликовал Kest
October 21 2009 08:30:00 ·
0 Комментариев ·
7441 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
