Next:5.12
Система дорог
Up:5
Выбор представления данных
Previous:5.10
Граф
Другой подход к реализации корневого дерева D связан с его представлением с помощью бинарного дерева. Бинарное дерево, реализующее корневое дерево D, имеет то же множество вершин, что и D . В нем вершина q является левым сыном вершины p тогда и только тогда, когда q -- первый сын вершины p в D, и является правым сыном вершины p тогда и только тогда, когда q -- брат вершины p в исходном дереве D.
Абстрактный тип: ДЕРЕВО, ВЕРШИНА. Набор операций:
ПервПоддерево (ДЕРЕВО): ДЕРЕВО;
СледПоддерево (ДЕРЕВО): ДЕРЕВО;
НадДерево (ДЕРЕВО): ВЕРШИНА;
Корень (ДЕРЕВО): ВЕРШИНА;
К приведенному списку функций абстрактного типа ВЕРШИНА можно добавить еще набор операций для создания новых деревьев
НовоеТривиальное (ВЕРШИНА): ДЕРЕВО;
НовоеПустое: ДЕРЕВО;
а также операции, позволяющие перестраивать старые деревья:
ЗаменитьПоддерево(ДЕРЕВО,ДЕРЕВО);
ДобавитьПоддерево(ДЕРЕВО,ДЕРЕВО);
ВставитьПослеПоддерева(ДЕРЕВО,ДЕРЕВО);
Первая из операций в дереве, поддеревом которого является первое дерево, заменяет указанное поддерево на второе дерево. Вторая операция к дереву, указанному первым, подключает второе дерево в качестве первого поддерева его корня, а третья операция к дереву, поддеревом которого является первое дерево, добавляет второе дерево таким образом, что оно становится поддеревом корня дерева, следующим за указанным поддеревом.
Для реализации такого абстрактного типа данных на языке Паскаль можно рекомендовать следующий конкретный тип и набор функций:
record {public, ref} УЗЕЛ;
var {public} Верш:ВЕРШИНА; Отец,Сын,Брат:УЗЕЛ;
end УЗЕЛ;
type ДЕРЕВО = УЗЕЛ;
procedure ПервПоддерево (D:ДЕРЕВО):ДЕРЕВО;
begin ПервДерево:=
D . Сын; end;
procedure СледПоддерево (D: ДЕРЕВО): ДЕРЕВО;
begin СледДерево:=
D . Брат; end;
procedure НадДерево (D:ДЕРЕВО):ДЕРЕВО;
begin НадДерево:=
D . Отец end;
procedure Корень (D:ДЕРЕВО):ВЕРШИНА;
begin Корень:=D .
Верш end;
Next:5.12
Система дорог
Up:5
Выбор представления данных
Previous:5.10
Граф