Автор работы: Пользователь скрыл имя, 14 Декабря 2013 в 16:02, курсовая работа
Объектом разработки в курсовой работе является структура данных – бинарное дерево поиска.
Целью работы является изучение данной структуры, а затем разработка приложения на языке программирования Pascal с её реализацией .
В ходе курсовой работы был создана программа на языке Pascal,в которой были созданы бинарное дерево поиска и функции, позволяющий выполнять с ним основные операции (например, добавления, удаления и поиска).
ВВЕДЕНИЕ 2
1.Общие сведения о бинарных деревьях. 3
1.1.Операции над бинарными деревьями 5
Бинарное дерево должно реализовывать следующие операции: 5
1.2.Представление бинарных деревьев. 5
1.3.Применение. 7
1.4.Способы прохождения (или обхода) бинарного дерева. 7
2.Алгоритм поиска по бинарному дереву. 9
3.Разработка программы 11
3.1 Блок схемы 13
ЗАКЛЮЧЕНИЕ 16
СПИСОК ЛИТЕРАТУРЫ 17
AddToTree(Tree^.left,x) {если меньше корня то в левое поддерево }
else
AddToTree(Tree^.right,x); {если больше то в правое}
end;
Функция поиска по дереву
function Search(Tree:PNode;x:integer):
var
p:PNode; {вспомог переменнная }
begin
if Tree=nil then {если дерево пустое то}
begin
Search:=nil; {присваеваем функции результат нил}
exit; {и выходим }
end;
if x=Tree^.data then {если искомый элемент равен корню дерева то }
p:=Tree {запоминаем его адрес }
else {иначе}
if x < Tree^.data then {если вводимый элемент менньше корня то }
p:=Search(Tree^.left,x) {то ищем его в левом поддереве}
else {иначе }
p:=Search(Tree^.right,x); {ищем в правом поддереве }
Search:=p; {присваиваем переменной с именем функции результат работы}
end;
Процедура удаления дерева
procedure DeleteTree(var Tree1:PNode );
begin
if Tree1 <> nil then
begin
DeleteTree (Tree1^.LEFT);
DeleteTree (Tree1^.RIGHT);
Dispose(Tree1);
end;
end;
Основная программа
begin
Tree:=nil;
repeat {цикл для нашего меню}
Writeln('Выберете действие ');
Textcolor(2);
Writeln('Меню:');
Writeln('1) Создание дерева поиска');
Writeln('2) Поиск элемента в дереве');
Writeln('3) Вывод дерева');
Writeln('4) Выход');
writeln;
readln(ch); {ожидаем нажатия клавиши}
case ch of {выбираем клавишу}
'1': begin
writeln(' kolv elementov');
readln(n);
for i:=1 to n do
begin
writeln('Введите число');
readln(x);
AddToTree(Tree,x);
end;
end;
'2': begin
writeln('Элемент для поиска');
readln(x);
p1:=Search(Tree,x);
if p1 <> nil then
writeln('Найден')
else writeln('Такого элемента нет!');
end;
'3': begin
writeln('Само дерево');
Lkp(Tree);
writeln;
end;
end;
until ch='4';
DeleteTree(Tree);
end.
Основная программа
Процедура добавления элемента
Функция поиска по дереву
Процедура удаления дерева
В итоге проделанной работы , я познакомился с понятие бинарного дерева, его свойствами, представлением , применением и способами прохождения дерева. Так же, я разработал программу поиска по бинарному дереву и продемонстрировал ее на примере.
4. Левитин А.В. Алгоритмы: введение в разработку и анализ. : Пер. с англ. –М. : Издательский дом «Вильямс», 2006. – 576 с. :ил. – Парал. тит. англ.
uses crt;
type
PNode=^Node; {Указатель на узел}
Node=record {Тип запись в котором будет храниться информация}
data:integer;
left,right:PNode; {Ссылки на левого и правого сыновей}
end;
var
Tree,p1:PNode; {Tree адрес корня дерева, p1-вспомогательная переменная}
n,x,i:integer;
ch:char; {для работы меню}
{Процедура добавления элемента }
procedure AddToTree (var Tree:PNode;x:integer); {Входные параметры - адрес корня дерева и добавляем элемент }
begin
if Tree=nil then {Если дерево пустое то создаём его корень}
begin
New(Tree); {Выделяем память }
Tree^.data:=x; {Добавляем данные }
Tree^.left:=nil; {Зануляем указатели на левого }
Tree^.right:=nil; {и правого сыновей }
exit;
end;
if x < Tree^.data then {Доб к левому или правому поддереву это завсит от вводимого элемента}
AddToTree(Tree^.left,x) {если меньше корня то в левое поддерево }
else
AddToTree(Tree^.right,x); {если больше то в правое}
end;
{Функция поиска по дереву}
function Search(Tree:PNode;x:integer):
var
p:PNode; {вспомог. переменная }
begin
if Tree=nil then {если дерево пустое то}
begin
Search:=nil; {присваиваем функции результат нил}
exit; {и выходим }
end;
if x=Tree^.data then {если искомый элемент равен корню дерева то }
p:=Tree {запоминаем его адрес }
else {иначе}
if x < Tree^.data then {если вводимый элемент меньше корня то }
p:=Search(Tree^.left,x) {то ищем его в левом поддереве}
else {иначе }
p:=Search(Tree^.right,x); {ищем в правом поддереве }
Search:=p; {присваиваем переменной с именем функции результат работы}
end;
{Обход
дерева по принципу Левый-
procedure Lkp(Tree:PNode);
begin
if Tree=nil then {Если дерево пустое }
exit; {то выход }
Lkp(Tree^.left); {иначе начинаем обход с левого поддерева}
write(' ',Tree^.data); {выводим данные }
Lkp(Tree^.right); {обходим правое поддерево}
end;
{Процедура удаления дерева}
procedure DeleteTree(var Tree1:PNode );
begin
if Tree1 <> nil then
begin
DeleteTree (Tree1^.LEFT);
DeleteTree (Tree1^.RIGHT);
Dispose(Tree1);
end;
end;
{основная программа}
begin
Tree:=nil;
repeat {цикл для нашего меню}
Writeln('Выберете действие ');
Textcolor(2);
Writeln('Меню:');
Writeln('1) Создание дерева поиска');
Writeln('2) Поиск элемента в дереве');
Writeln('3) Вывод дерева');
Writeln('4) Выход');
writeln;
readln(ch); {ожидаем нажатия клавиши}
case ch of {выбираем клавишу}
'1': begin
writeln(' kolv elementov');
readln(n);
for i:=1 to n do
begin
writeln('Введите число');
readln(x);
AddToTree(Tree,x);
end;
end;
'2': begin
writeln('Элемент для поиска');
readln(x);
p1:=Search(Tree,x);
if p1 <> nil then
writeln('Найден')
else writeln('Такого элемента нет!');
end;
'3': begin
writeln('Само дерево');
Lkp(Tree);
writeln;
end;
end;
until ch='4';
DeleteTree(Tree);
end.