Представление сильноветвящихся деревьев
Произвольные деревья могут быть сильноветвящимися. Причем число потомков различных узлов не ограничено и заранее не известно. Тем не менее, для представления таких деревьев достаточно иметь элементы, аналогичные элементам списковой структуры бинарного дерева.
Элемент такой структуры содержит минимум три поля: значение узла, указатель на начало списка потомков узла, указатель на следующий элемент в списке потомков текущего уровня. Также как и для бинарного дерева необходимо хранить указатель на корень дерева.
При этом дерево представлено в виде структуры, связывающей списки потомков различных вершин. Такой способ представления вполне пригоден и для бинарных деревьев. Представление деревьев с произвольной структурой в виде массивов может быть основано на матричных способах представления графов.
Рассмотрим использование сильноветвящихся деревьев для представления иерархической структуры каталогов файловой системы. Во многих файловых системах структура каталогов и файлов, как правило, представляет одно или несколько сильноветвящихся деревьев. В файловой системе корень дерева соответствует логическому диску. Листья дерева соответствуют файлам и пустым каталогам, а узлы с ненулевой степенью – непустым каталогам.
Для представления такой структуры используем расширение спискового представления сильноветвящихся деревьев (рис. 7.26). Способы представления деревьев, рассмотренные ранее, являются предельно экономичными, но не очень удобными для перемещения по дереву в разных направлениях. Именно такая задача встает при просмотре структуры каталогов. Необходимо осуществлять навигацию – перемещаться из текущего каталога в каталог верхнего или нижнего уровня, или от файла к файлу в пределах одного каталога.
Списки потомков можно сделать двунаправленными. Для этого необходимо ввести указатель на предыдущий узел last, а для упрощения перемещения по дереву от листьев к корню потребуется указатель на предок текущего узла up. Общими с традиционными способами представления являются указатели на список потомков узла down и следующий узел next.
Рис. 7.26. Представление сильноветвящихся деревьев в виде списков.
Контрольные вопросы
1. Приведите определение понятию граф. Разновидности, свойства и назначение графов.
2. Способы физического и логического представления графов.
3. Бинарные деревья. Представления и способы обхода.
4. Применения бинарных деревьев.
5. Сильноветвящиеся деревья. Представления и области применения.
Дата добавления: 2021-12-14; просмотров: 352;