Лабораторная работа №17. Работа с бинарными деревьями поиска
ЦЕЛЬ РАБОТЫ: Познакомиться с основами программирования бинарных деревьев поиска, способами просмотра дерева, функциями добавления элемента в бинарное дерево поиска и удаления элементов из бинарного дерева поиска.
ПОДГОТОВКА К РАБОТЕ:
Рассмотреть виды деревьев.
Изучить методы построения и назначение бинарных деревьев поиска.
Рассмотреть дерево-формулу.
Ознакомиться с методами прохода бинарных деревьев..
ЗАДАНИЕ: Разработать приложение добавления элементов в бинарное дерево поиска, удаления элементов, просмотра дерева сверху вниз (Корень-Левый-Правый) и определения максимальной глубины дерева. Приложение для работы с деревом приведено на рисунке 17.1.
Компоненты приложения приведены в таблице 17.1.
Последовательность действий:
В блоке Type после объявления класса создайте структуру – «элемент бинарного дерева» и указатель на элемент дерева:
PTree=^Tree;
Tree=Record
data:Integer;
Left,Right:Ptree;
end;
В области глобальных переменных объявите переменную – указатель на корень дерева:
var
Form1: TForm1;
Root:PTree;
Implementation
…………………………
Таблица 17.1 Компоненты приложения
Компонент |
Класс |
Описание |
1 |
2 |
3 |
Label1 |
TLabel |
Метка «Элемент дерева» |
Label2 |
TLabel |
Метка «Просмотр дерева сверху вниз» |
Label3 |
TLabel |
Метка для вывода максимальной глубины дерева. В начальный момент данное поле - пустое |
Edit1 |
TEdit |
Окно ввода очередного элемента дерева |
Memo1 |
TMemo |
Многострочное поле вывода дерева сверху вниз |
Button1 |
TButton |
Командная кнопка «Вставить» |
Button2 |
TButton |
Командная кнопка «Удалить» |
Button3 |
TButton |
Командная кнопка «Вывод дерева» |
Button4 |
TButton |
Командная кнопка «Определение максимальной глубины дерева». У данной кнопки свойство WordWrap должно иметь значение True для того, чтобы можно было вывести название кнопки в несколько строк. |
В блок implementation вставьте рекурсивную процедуру добавления элемента в бинарное дерево поиска:
// рекурсивная процедура добавления элемента в двоичное дерево
Procedure Ins_Tree(Var t:PTree;x:Integer);{*x - значение вставляемого элемента.*}
Begin
// Если нашли пустую ветвь, то вставляем новый элемент
If t=Nil Then
Begin
New(t) ;
With t^ Do
Begin
left:=Nil;
right:=Nil;
data:=x;
End;
End
Else
// если вставляемый элемент меньше или равен значения
// очередного узла, то ищем пустую ветвь в левой части дерева
// (рекурсивный вызов этой же процедуры)
If x<=t^.data Then Ins_Tree(t^.left,x)
// если вставляемый элемент больше значения очередного узла, то
// ищем пустую ветвь в правой части дерева
// (рекурсивный вызов этой же процедуры)
Else Ins_Tree(t.right,x);
End;
В блок implementation вставьте рекурсивную процедуру удаления элемента из бинарного дерева поиска. Удаление происходит следующим образом:
Если удаляемый узел имеет одного потомка, то в поле ссылки родителя удаляемого элемента записывается ссылка на единственного потомка удаляемого элемента;
Если у удаляемого элемента два потомка, для сохранения структуры бинарного дерева поиска на место удаляемого элемента записывается или самый правый элемент левого поддерева, или самый левый элемент правого поддерева.
В приведенной процедуре производится удаление самого правого элемента левого поддерева.
//Рекурсивная процедура удаления элемента из дерева
Procedure Del_Tree(Var t:PTree; x:Integer);
Var q:PTree;
// Вспомогательная процедура поиска самого правого элемента в дереве
Procedure Del(Var w:PTree);
Begin
If w^.right<>Nil Then Del (w^.right)
Else
Begin
q:=w; {*3aпоминаем адрес для того, чтобы освободить место в "куче" *}
t^.data:=w^.data;
w:=w^.left;
End;
End;
Begin
If t<>Nil Then
If x<t^.data Then Del_Tree(t^.left,x)
Else
If x>t^.data Then Del_Tree(t^.right,x)
Else
Begin
q:=t;
If t^.right=Nil Then t:=t^.left // Правого поддерева нет
Else If t^.left=Nil Then t:=t^.right; // Левого поддерева нет
Else Del (t^.left) // Находим самый правый элемент в левом
// поддереве
Dispose (q);
End;
End;
В блок implementation вставьте рекурсивную процедуру вывода дерева сверху вниз:
// рекурсивная процедура вывода дерева
Procedure Print_Tree (t:PTree);
Begin
If t<>Nil Then
Begin
Form1.Memo1.Lines.Add(IntToStr(t^.data));
Print_Tree(t^.left);
Print_Tree (t^. right) ;
End;
End;
В блок implementation вставьте рекурсивную функцию определения максимальной глубины дерева MaxDeepOfTree. Данная функция использует вспомогательную функцию Max, которая сравнивает и возвращает максимальную глубину двух ветвей выбранной вершины.
//Определение максимальной глубины дерева
Function Max(temp1, temp2 : integer):integer;
begin
if temp1>temp2 then max:=temp1
else max:=temp2;
end;
Function MaxDeepOfTree(t:PTree):integer;
begin
if t=nil then MaxDeepOfTree:=-1
else
MaxDeepOfTree:=Max(MaxDeepOfTree(t^.left), MaxDeepOfTree(t^.right))+1;
end;
Для события OnActivate компонента Form1 напишите следующий программный код:
procedure TForm1.FormActivate(Sender: TObject);
begin
// В начальный момент дерево пустое и указатель корня дерева
// равен nil
Root:=nil;
end;
Для события OnClick кнопки Button1 (вставить) напишите следующий программный код:
procedure TForm1.Button1Click(Sender: TObject);
begin
// Поиск ведется начиная с корня дерева
Ins_Tree(root,StrToInt(Edit1.Text));
end;
Для события OnClick кнопки Button2 (удалить) напишите следующий программный код:
procedure TForm1.Button2Click(Sender: TObject);
begin
// Поиск удаляемого элемента ведется, начиная с корня дерева
Del_Tree(root,StrToInt(Edit1.Text));
end;
Для события OnClick кнопки Button3 (вывод дерева) напишите следующий программный код:
procedure TForm1.Button3Click(Sender: TObject);
begin
Print_Tree(Root);
end;
Для события OnClick кнопки Button4 (определение максимальной глубины дерева) напишите следующий программный код:
procedure TForm1.Button4Click(Sender: TObject);
Var m:Integer;
begin
m:=MaxdeepOfTree(Root);
Label3.Caption:=IntToStr(m);
end;
Откомпилируйте приложение и проверьте его работу.