2014-02-24
637
Список рекомендуемой литературы
Создания, обработки, просмотра содержимого
бинарного дерева (на примере сбалансированного дерева)
| 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]
