Примеры использования деревьев

Представление бинарного дерева

Представление корневого дерева

Способы представления деревьев

Поскольку любое дерево является графом, то его можно задавать любым из способов, перечисленных в п. "Способы представления графов". Однако существуют и специальные способы представления, предназначенные только для деревьев. Мы рассмотрим только два наиболее распространенных частных случая.

Этот способ подходит только для тех корневых деревьев, у которых точно известно максимальное количество потомков для любой вершины.

type ukazatel = ^tree; tree = record znachenie: integer; siblings: array[1..S] of ukazatel; end;

Разумеется, в общем случае значение переменной S (количество потомков) может достигать N-1 (N - количество всех вершин в дереве). Однако ясно, что в такой ситуации особого смысла в динамической древесной структуре нет: экономии памяти не получается. Гораздо лучше, если у всех вершин примерно одинаковое и заранее известное количество потомков.

Разновидностью описанного выше частного случая является бинарное корневое дерево: каждая его вершина имеет не более двух потомков:

type ukazatel = ^tree; tree = record znachenie: integer; left_sibling: ukazatel; right_sibling: ukazatel; end;

Здесь мы ограничимся только примерами использования бинарных корневых деревьев: именно такой вид графа чаще всего применяется в программировании.

Дата добавления: 2014-01-03