Список рекомендуемой литературы
Создания, обработки, просмотра содержимого
бинарного дерева (на примере сбалансированного дерева)
Uses Crt; | ||||||||
Type | ||||||||
PTree = ^ Tree; | { тип – указатель на узел сбалансированного дерева } | |||||||
Tree = record | { тип – элемент хранения узла сбалансированного дерева } | |||||||
info: word; | ||||||||
left, right: PTree | ||||||||
end; | ||||||||
var f: PTree; cod,n: byte; sum: word; | ||||||||
Procedure Balance(var root: PTree; | { root – указатель на корень дерева, } | |||||||
n: byte); | { n – количество узлов в дереве } | |||||||
begin | ||||||||
if n = 0 then root:=nil | { если n = 0, построить пустое дерево } | |||||||
else begin | ||||||||
new(root); | { создать корень дерева } | |||||||
write(‘Значение информационного поля узла дерева = ‘); | ||||||||
readln(root^.info); | { заполнить информационное поле корня } | |||||||
Balance(root^.left, n div 2); | { построить левое поддерево} | |||||||
Balance(root^.right, n – n div 2 – 1) | { построить правое поддерево } | |||||||
end | ||||||||
end; | ||||||||
Procedure Print(root: PTree); | { просмотр информац. полей узлов дерева - } | |||||||
begin | { нисходящий обход } | |||||||
if root <> nil then begin | ||||||||
writeln(‘Информационное поле узла дерева = ‘, root^.info); | ||||||||
Print(root^.left); | { просмотреть левое поддерево } | |||||||
Print(root^.right); | { просмотреть правое поддерево } | |||||||
end; | ||||||||
end; | ||||||||
Procedure Work(root: PTree; var s: word); | { суммирование значений информ. } | |||||||
begin | { полей узлов дерева – смешанный обход } | |||||||
if root <> nil then begin | ||||||||
Work(root^.left); | { обработать левое поддерево } | |||||||
s:=s + root^.info; | { суммирование значений инф. полей узлов } | |||||||
Work(root^.right); | { обработать правое поддерево } | |||||||
end; | ||||||||
end; | ||||||||
Procedure Destroy(var root: PTree); | { разрушение дерева } | |||||||
begin | ||||||||
... | ||||||||
end; | ||||||||
Procedure Message; | { вспомогательная процедура } | |||||||
begin | ||||||||
writeln(‘Дерево пусто‘); write(‘Нажмите любую клавишу‘); readkey | ||||||||
end; | ||||||||
begin | ||||||||
f:=nil; | { первоначально дерево пусто } | |||||||
repeat Clrscr; | ||||||||
writeln(‘1-Создание 2-Просмотр 3–Обработка 4–Разрушение 5-Выход‘); | ||||||||
write(‘Код действия = ‘); readln(cod); | ||||||||
case cod of | ||||||||
1: begin | { создание сбалансированного дерева } | |||||||
write(‘Количество узлов в дереве = ‘); readln(n); | ||||||||
Balance(f,n); write(‘Нажмите любую клавишу‘); readkey | ||||||||
end; | ||||||||
2: begin | { просмотр дерева } | |||||||
if f=nil then Message | ||||||||
else begin | ||||||||
Print(f); write(‘Нажмите любую клавишу‘); readkey | ||||||||
end; | ||||||||
3: begin | { обработка дерева } | |||||||
if f=nil then Message | ||||||||
else begin | ||||||||
sum:=0; | { инициализация значения глобальной переменной } | |||||||
Work(f,sum); writeln(‘Сумма значений инф. полей = ‘, sum); | ||||||||
write(‘Нажмите любую клавишу‘); readkey | ||||||||
end; | ||||||||
4: begin | { разрушение дерева } | |||||||
if f=nil then Message | ||||||||
else begin | ||||||||
Destroy(f); writeln(‘Дерево разрушено‘); | ||||||||
write(‘Нажмите любую клавишу‘); readkey | ||||||||
end; | ||||||||
5: Destroy(f) | { выход } | |||||||
end; | ||||||||
until (cod = 5); Clrscr | ||||||||
end. | ||||||||
1. Н. Вирт. Алгоритмы + структуры данных = программы: Пер. с англ. -М.: Мир, 1985.
2. Н. Вирт. Алгоритмы и структуры данных: Пер. с англ. -М.: Мир, 1989.
3. Кнут Д. Искусство программирования для ЭВМ. Том 1: Пер. с англ. -М.: Мир. 1978.
4. Трамбле Ж., Соренсон П. Введение в структуры данных: Пер. с англ. -М.: Машиностроение. 1982.
5. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. Учебное пособие. –М.: Нолидж. 1997.
[ГНС1]вопрос
[ГНС2]