Графы в Языке Паскаль


Лекция №11.4: Графы и деревья
Июнь 13, 2016 – 13:22
34 Изучение графов на языке
Дерево двоичного поиска

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

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

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

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

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;

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

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

Дерево двоичного поиска

Дерево двоичного поиска для множества чисел S — это размеченное бинарное дерево, каждой вершине которого сопоставлено число из множества S, причём все пометки удовлетворяют следующим условиям:

  1. существует ровно одна вершина, помеченная любым числом из множества S;
  2. все пометки левого поддерева строго меньше, чем пометка текущей вершины;
  3. все пометки правого поддерева строго больше, чем пометка текущей вершины.

Если выражаться простым языком, то структура дерева двоичного поиска подчиняется простому правилу: «если больше — направо, если меньше — налево».

Например, для набора чисел 7, 3, 5, 2, 8, 1, 6, 10, 9, 4, 11 получится такое дерево (см. ).

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

Source: pascal.net.ru
Похожие публикации