Файл: Динамические структуры данных. Бинарные деревья.pdf

library binarytree;

uses

SysUtils,

Classes, Dialogs;

{$R *.res}

type

TInfo = Byte;

PItem = ^Item;

Item = record

Key: TInfo;

Left, Right: PItem;

end;

procedure InLeft (var P: PItem; X : TInfo); export;//добавление узла слева

var R : PItem;

begin

New(R);

R^.Key := X;

R^.Left := nil;

R^.Right := nil;

P^.Left := R;

end;

procedure InRight (var P: PItem; X : TInfo); export;//добавить узел справа

var R : PItem;

begin

New(R);

R^.Key := X;

R^.Left := nil;

R^.Right := nil;

P^.Right := R;

end;

procedure Tree_Add (P: PItem; X : TInfo); export;

var OK: Boolean;

begin

OK := false;

while not OK do begin

if X > P^.Key then //посмотреть направо

if P^.Right <> nil //правый узел не nil

then P := P^.Right //обход справа

else begin //правый узел – лист и надо добавить к нему элемент

InRight (P, X); //и конец

OK := true;

end

else //посмотреть налево

if P^.Left <> nil //левый узел не nil

then P := P^.Left //обход слева

else begin //левый узел -лист и надо добавить к нему элемент

InLeft(P, X); //и конец

OK := true

end;

end; //цикла while

end;

procedure Delete (var P: PItem; X: TInfo); export;

var Q: PItem;

procedure Del(var R: PItem);

//процедура удаляет узел, имеющий двух потомков, заменяя его на самый правый

//узел левого поддерева

begin

if R^.Right <> nil then //обойти дерево справа

Del(R^.Right)

else begin

//дошли до самого правого узла

//заменить этим узлом удаляемый

Q^.Key := R^.Key;

Q := R;

R := R^.Left;

end;

end; //Del

begin //Delete

if P <> nil then //искать удаляемый узел

if X < P^.Key then

Delete(P^.Left, X)

else

if X > P^.Key then

Delete(P^.Right, X) //искать в правом поддереве

else begin

//узел найден, надо его удалить

//сохранить ссылку на удаленный узел

Q := P;

if Q^.Right = nil then

//справа nil

//и ссылку на узел надо заменить ссылкой на этого потомка

P := Q^.Left

else

if Q^.Left = nil then

//слева nil

//и ссылку на узел надо заменить ссылкой на этого потомка

P := P^.Right

else //узел имеет двух потомков

Del(Q^.Left);

Dispose(Q);

end

else

MessageDlg('Такого элемента нет в дереве',mtError,[mbOK],0);

end;

exports InLeft,InRight,Tree_Add,Delete;

begin

end.

Листинг основной программы

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ComCtrls;

type

TInfo = Byte;

PItem = ^Item;

Item = record

Key: TInfo;

Left, Right: PItem;

end;

TTree = class

private

Root: PItem;

public

constructor Create;

procedure Add(Key: TInfo);

procedure Del(Key: TInfo);

procedure View;

procedure Exist(Key: TInfo);

end;

TForm1 = class(TForm)

GroupBox1: TGroupBox;

Edit1: TEdit;

Button2: TButton;

Button3: TButton;

Button5: TButton;

ListBox1: TListBox;

procedure FormCreate(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure Button5Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

Root: PItem;

Tree: TTree;

N: Byte;

err: boolean;

Key: TInfo;

procedure InLeft (var P: PItem; X : TInfo); external 'binarytree.dll'

procedure InRight (var P: PItem; X : TInfo); external 'binarytree.dll'

procedure Tree_Add (P: PItem; X : TInfo);external 'binarytree.dll'

procedure Delete (var P: PItem; X: TInfo); external 'binarytree.dll'

implementation

{$R *.dfm}

constructor TTree.Create;

begin

Root := nil;

end;

procedure TTree.Add(Key: TInfo);

procedure IniTree(var P: PItem; X: TInfo); //создание корня дерева

begin

New(P);

P^.Key :=X;

P^.Left := nil;

P^.Right := nil;

end;

begin

if Root = nil

then IniTree(Root, Key)

else Tree_Add(Root, Key);

end;

procedure TTree.Del(Key: TInfo);

begin

Delete(Root, Key);

end;

procedure TTree.View;

procedure PrintTree(R: PItem; L: Byte);

var i: Byte;

begin

if R <> nil then begin

PrintTree(R^.Right, L + 3);

for i := 1 to L do

Form1.ListBox1.Items[Form1.ListBox1.Count-1]:=Form1.ListBox1.Items[Form1.ListBox1.Count-1]+' ';

Form1.ListBox1.Items[Form1.ListBox1.Count-1]:=Form1.ListBox1.Items[Form1.ListBox1.Count-1]+inttostr(R^.Key);

Form1.ListBox1.Items.Add('');

PrintTree(R^.Left, L + 3);

end;

end;

begin

Form1.ListBox1.Items.Add('');

PrintTree (Root, 1);

end;

procedure TTree.Exist(Key: TInfo);

procedure Search(var P: PItem; X: TInfo);

begin

if P = nil then begin

MessageDlg('Not Found Element',mtError,[mbOK],0);

end else

if X > P^. Key then //ищется в правом поддереве

Search (P^. Right, X)

else

if X < P^. Key then

Search (P^. Left, X)

else

MessageDlg('Found Element', mtCustom,[mbOK],0);

end;

begin

Search(Root, Key);

end;

procedure InputKey(S: String; var Key: TInfo);

begin

WriteLn(S);

ReadLn(Key);

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

Tree := TTree.Create;

end;

procedure TForm1.Button2Click(Sender: TObject);

begin

Form1.ListBox1.Clear;

if Edit1.Text = '' then else

Key:=strtoint(Edit1.Text);

Tree.Add(Key);

Tree.View;

Edit1.Clear;

Edit1.SetFocus;

end;

procedure TForm1.Button3Click(Sender: TObject);

begin

Form1.ListBox1.Clear;

if Edit1.Text = '' then else

Key:=strtoint(Edit1.Text);

Tree.Del(Key);

Tree.View;

end;

procedure TForm1.Button5Click(Sender: TObject);

begin

err:=False;

try

Key:=strtoint(Edit1.Text);

err:=False;

except

err:=True;

ShowMessage('Значение узла не введено. Программа завершает работу');

Application.Terminate;

end;

Tree.Exist(Key);

end;

end.

1. Информатика: Уч. / В.А.Каймин - 6 изд. -М.: НИЦ ИНФРА-М, 2016 -285с. ↑

2. Информатика, автоматизированные информационные технологии и системы: Учебник / В.А. Гвоздева. - М.: ИД ФОРУМ: НИЦ ИНФРА-М, 2015. - 544 с. ↑

3. Базовые средства программирования/ В.Н. Шакин. - М.: Форум: НИЦ ИНФРА-М, 2015. - 304 с. ↑

4. Алгоритмы. Вводный курс/ Томас Х. Кормен М.: Вильямс, 2015. – 208с. ↑

5. Программирование на языке высокого уровня. Учебное пособие / Т.И. Немцова; Под ред. Л.Г. Гагариной. - М.: ФОРУМ: ИНФРА-М, 2015. - 496 с. ↑

6. Информатика: Уч. / В.А.Каймин - 6 изд. -М.: НИЦ ИНФРА-М, 2016 -285с. ↑

7. Стивенс Род - Алгоритмы. Теория и практическое применение – М.: ЭКСМО, 2016. – 544 с. ↑

8. Дискретная математика для программистов / Гэри Хаггард, Джон Шлипф, Сью Уайтсайдс – М.: Бином. Лаборатория знаний, 2017. – 632с. ↑

9. Иерархические структуры данных: бинарные деревья. Учебное пособие по дисциплине «Информатика» / А.В. Никитин, Т.Н. Ничушкина - М.: МГТУ имени Н.Э. Баумана, 2017. – 60 с. ↑

10. Структуры данных – деревья – [Электронный ресурс] – режим доступа: https://pro-prof.com/archives/682 (дата обращения: 05.12.2020) ↑

11. Кормен Томас Алгоритмы. Построение и анализ / Томас Кормен, Чарльз Лейзерсон, Рональд Риверст, Клиффорд Штайн – М.: Вильямс, 2016. – 1328с. ↑

12. Кормен Томас Алгоритмы. Построение и анализ / Томас Кормен, Чарльз Лейзерсон, Рональд Риверст, Клиффорд Штайн – М.: Вильямс, 2016. – 1328с. ↑

13. Стивенс Род - Алгоритмы. Теория и практическое применение – М.: ЭКСМО, 2016. – 544 с. ↑

14. Иерархические структуры данных: бинарные деревья. Учебное пособие по дисциплине «Информатика» / А.В. Никитин, Т.Н. Ничушкина - М.: МГТУ имени Н.Э. Баумана, 2017. – 60 с. ↑

15. Бинарные деревья [Электронный ресурс] – режим доступа: http://www.codenet.ru/progr/alg/ btree.php (дата обращения: 05.12.2020) ↑

16. Программирование на языке высокого уровня. Учебное пособие / Т.И. Немцова; Под ред. Л.Г. Гагариной. – М.: ФОРУМ: ИНФРА-М, 2015. – 496 с. ↑

17. Голицына О.Л. Языки программирования: Учебное пособие / О.Л. Голицына, Т.Л. Партыка, И.И. Попов. – 3-e изд., перераб. и доп. – М.: Форум: ИНФРА-М, 2015. – 400 с. ↑