Программирование на языке С. Наместников С.М. - 29 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

29
Теоретические сведения
Связные списки не охватывают весь спектр возможных представлений
данных. Например, с их помощью сложно описать иерархические структуры
подобные каталогам и файлам или хранения информации генеалогического
древа. Для этого лучше подходит модель известная как бинарные деревья.
Графически бинарные деревья можно изобразить как последовательность
объектов, каждый из которых может быть
связан с двумя последующими
(рис. 5).
Корень дерева
left right
Левая вершина
left right
Правая вершина
left right
Лист дерева
left right
Правая вершина
left right
Левая вершина
left right
Лист дерева
left right
N
ULL
N
ULL
N
ULL … … …
N
ULL
N
ULL
Рис. 5. Графическая интерпретация бинарного дерева
Каждый объект бинарного дерева имеет два указателя: на «левый» и
«правый» вершины. Самый верхний уровень называется корнем дерева. Если
указатели объекта left и right равны NULL, то он называет листом дерева.
При описании структуры каталогов с помощью бинарного дерева можно
воспользоваться следующим правилом. Переход по «левым» указателям
будет
означать список файлов, а переход по «правым» – список каталогов. Например,
для описания простой структуры (рис. 6), бинарное дерево будет иметь вид,
представленный на рис. 7.
Корень дерева
left right
Файл 1
left right
Каталог 1
left right
Файл 2
left right
Файл 11
left right
Каталог 2
left right
N
ULL
N
ULL
N
ULL
N
ULL
Файл 12
left right
N
ULL
N
ULL
N
ULL
Файл 21
left right
N
ULL
N
ULL
Рис. 6. Структура каталогов Рис. 7. Структура бинарного дерева
Корень
Каталог 1
Каталог 2
Файл 11
Файл 12
Файл 21
Файл 1
Файл 2

Страницы