Деревья как структуры данных

Как обычно, структуры данных мы ассоциируем с некоторым семейством функций: fÎI®T, где I – некоторое множество “индексов” (указателей или ключей) со следующими основными операциями: выборка, поиск, вычисление значения по ключу, поиск ключа по значению (вычисление обратной функции), сохранение значения по ключу (переопределение функции в заданной точке), создание нового ключа (расширение области определения), удаление ключа (сужение области определения). Реализация всех этих операций связана с некоторым порядком перечисления ключей.

Дерево как структуру данных естественно рассматривать как функцию на путях, «словах».

Пример. Декодирование текста, записанного азбукой Морзе.

Центральная проблема: найти по коду Морзе его значение (букву в латинском алфавите).

Как хранить таблицу соответствий кодов и букв?

F={0,1}^*®Last[‘a’..’z’]

…………….

®1 1 1 ® ‘s’

®0 0 0 ® ‘o’

…………….

0 1

0 1 1

0 1

Упражнение. 1) Завершить задачу декодирования.

2) Выяснить, сколько раз встречается каждое слово в тексте. Результатом должно быть [‘a’..’z’]^*®Cardinal

3) Что за функция «дерево выражений»?

В применении к деревьям эта задача формулируется как задача обхода дерева в некотором или заданном порядке. Рассмотрим задачу на примере задачи поиска.

procedure Poisk(root:pNode;x:tInfo;var key:pNode;var found:boolean);

begin

found:=false;

pt:=root;

push(stack,root);

while not found and {не кончились вершины} do

begin

pop(stack,pt);

if pt^.info=x then

begin

found:=true;

key:=pt;

end

else {перейти к следующему}

end;

if pt^.left<>nil then

begin

if pt^.right<>nil then push(stack,pt^.right);

pt:=pt^.left;

end

else if pt^.right<>nil then pt:=pt^.right;

end;

end; {Завести стек и хранить в нём ссылки на ещё не пройденные вершины дерева, то есть правые ссылки пройденных на данном пути вершин}

Очевидно, порядок обхода – знакомый лексикографический порядок.

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