16.4. Работа с деревьями
Дерево – это иерархическая информационная структура, состоящая из узлов, в каждом из которых может быть несколько указателей на дочерние узлы следующего по иерархии уровня.
Прародитель всех узлов называется корнем дерева. Узлы, не имеющие дочерних узлов, называются листьями. Промежуточные узлы называются ветвями. Степень дерева – максимальный порядок его узлов. Глубина дерева – это максимальная глубина его узлов.
Древовидное размещение списка данных (abcdefgkl) можно изобразить, например, следующим образом:
Рис.16.3. Структура дерева
Дерево, представленное выше, имеет степень 3 (троичное), глубину 4, корневой узел а.
Для работы, например, с двоичным деревом можно определить следующие типы:
а
b
c
f
e
d
g
l
k
Корневой узел (корень)
Узлы второго уровня
d, e, g, k, l – листья
Type Tpz=^Tz; // Указатель на запись
Tz=Record // Запись узла дерева
Inf:string; // Информационная часть узла дерева
Kl:integer; // Уникальный ключ узла дерева
P1,P2:Tpz; // Указатели на дочерние узлы дерева
End;
Для работы с деревьями в основном используют рекурсивные процедуры – процедуры, которые вызывают сами себя. Они позволяют проходить по всему дереву только по одному вызову таких процедур.
Прежде чем переходить к рассмотрению примера работы с деревьями, дадим описание некоторых свойств компонента TTreeView и класса TTreeNode, которые будут использованы в примере.
Компонент TTreeView предназначен для отображения ветвящихся иерархических структур в виде горизонтальных деревьев, например каталогов файловой системы дисков. Основным свойством этого компонента является Items, которое представляет собой массив элементов типа TTreeNode, каждый из которых описывает один узел дерева. Всего в Items – count узлов. Рассмотрим некоторые методы класса TTreeNodes:
Function AddFirst(Node:TTreeNode; const S:String):TTreeNode; – этот метод создает первый дочерний узел у узла Node. Если Node=Nil, то создается корневой узел. S – это строка содержания узла. Функция возвращает указатель на созданный узел;
Function AddChild(Node:TTreeNode; const S:String):TTreeNode; – эта функция добавляет очередной дочерний узел к узлу Node;
Procedure Clear; – этот метод очищает список узлов, описанных в свойстве Items;
Function DisplayRect(TextOnly: Boolean): TRect; – позволяет получить прямоугольник на канве компонента TTreeView, в котором описан текст узла TTreeNode, если аргумент TextOnly равен «True», иначе весь прямоугольник узла.
В качестве примера рассмотрим проект, который создает дерево, отображает его в компоненте TTreeView, находит узел по ключу и может очистить дерево. На форме будут располагаться: Button1 – для создания дерева, Button2 – для удаления дерева, Button3 – для поиска узла по ключу и TTreeView – для графического отображения дерева:
unit U1; // Текст модуля
interface
// подключаемые модули
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids, ComCtrls;
Type // Класс формы
TForm1 = class(TForm)
Button1: TButton;
TreeView1: TTreeView;
Button2: TButton;
Button3: TButton;
procedure Button1Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
Type Tpz=^Tz; // Тип указателя на запись
Tz=Record // Определение типа записи узла дерева
Inf:string; // Информационная часть узла
kl:integer; // Ключ узла дерева
pl,pr:tpz; // Указатели на исходящие ветви узла дерева
end;
var Form1: TForm1;
Proot:Tpz; // Указатель на корень дерева
Level:integer; // Уровень узла дерева
Kluch:integer; // Ключ узла дерева
skluch:string; // Строка ключа узла дерева при поиске
sitem:string; // Строка информационной части узла при поиске
implementation
{$R *.dfm}
// Рекурсивная процедура создания и отображения дерева в TreeView
Procedure CreateTree(var p,ppar:Tpz);
// p – Указатель на текущий узел дерева
// ppar – Указатель на родительский узел дерева
var pt1:Tpz; // Временный указатель на узел дерева
Begin with form1 do Begin
inc(level);
// При входе в процедуру увеличиваем уровень узла
if p=nil then Begin
// Если p=nil, то можно создать новый узел
// С помощью типового диалога решаем, создавать ли узел дерева
case messagedlg(’Создать новый элемент дерева уровня’
+’ ’+inttostr(level)+’ с ключом ’+inttostr(Kluch+1),
mtConfirmation,[mbok,mbno],0) of
mrok:Begin // Создаем новый узел
new(pt1); // Выделяем узлу память
// С помощью типового диалога вводим информацию в узел
pt1^.Inf:=inputbox('Ввод инф. части дерева',
'Введите текст элемента дерева','');
inc(kluch); // Увеличиваем номер узла на единицу
pt1^.kl:=kluch; // Запоминаем этот номер, как ключ
pt1^.pl:=nil;
// Записываем nil для дочернего левого узла
pt1^.pr:=nil;
// Записываем nil для дочернего правого узла
// Если kluch=1, т.е. это – корень дерева, то используем метод
// AddFirst для отображения этого узла, иначе – метод AddChild
if kluch=1 then Treeview1.Items.AddFirst(nil,Pt1^.inf+
’ ’+inttostr(kluch))
else Treeview1.Items.Addchild(treeview1.Items[ppar^.kl-1],
Pt1^.inf+’ ’+inttostr(kluch));
Treeview1.FullExpand;
// Раскрываем все дерево
createtree(pt1.pl,pt1); // Создаем левую ветвь дерева
createtree(pt1.pr,pt1); // Создаем правую ветвь дерева
p:=pt1;
// Программа будет возвращать указатель на новый узел дереваend;
mrno:Begin // В случае ответа «нет», ничего не делаем
end;
end;
end;
dec(level);
// При выходе из подпрограммы уменьшаем текущий уровень узла дерева
end;
end;
// Обработчик нажатия кнопки "Создать дерево"
procedure TForm1.Button1Click(Sender: TObject);
begin
createtree(proot,proot);
end;
// Отработчик события создания формы
procedure TForm1.FormCreate(Sender: TObject);
begin
Proot:=nil; // Указатель на корень дерева полагаем равным константе nil
Level:=0; // Текущий уровень узла дерева зануляем
Kluch:=0; // Текущий номер узла дерева зануляем
end;
// Процедура освобождения памяти для дерева
Procedure DeleteTree(var p:Tpz);
// Здесь P – указатель на удаляемую ветвь дереваBegin
If p=nil then exit;
if ((p^.pl=nil)and(p^.pr=nil))then Begin
// Если у узла нет дочерних узлов, то его можно удалить
Dispose(p);
p:=nil;
exit;
end;
// Если у узла есть дочерние узлы, то следует сначала их удалить
// с помощью программы DeleteTree
if p^.pl<>nil then deleteTree(p^.pl);
if p^.pr<>nil then deleteTree(p^.pr);
end;
// Обработчик нажания кнопки «Удалить дерево»
procedure TForm1.Button2Click(Sender: TObject);
begin
// Удаляем дерево с корневого узла
DeleteTree(proot);
proot:=nil;
level:=0;
kluch:=0;
// Очищаем компонент TreeView
TreeView1.Items.Clear;
end;
// Процедура поиска в дереве узла с заданным ключом
Procedure SeekTree(var p:Tpz;s:string);
// Здесь P – указатель на узел дерева
// S – искомый ключ узла дерева
var i:integer;
Begin
if p=nil then exit;
if s=inttostr(p^.kl) then Begin
skluch:=s;
sitem:=p^.inf;
end;
if p^.pr<>nil then seektree(p^.pr,s);
if p^.pl<>nil then seektree(p^.pl,s);
end;
// Обработчик нажатия кнопки "Поиск узла"
procedure TForm1.Button3Click(Sender: TObject);
var s:String;
rect1:Trect; // Прямоугольник для узла дерева
Color1:Tcolor; // Цвет шрифта узла дерева
begin
skluch:='';
sitem:='';
s:=Inputbox('Поиск узла',
'Введите ключ искомого узла','');
if length(s)>0 then Begin
SeekTree(Proot,s); // Ищем узел с ключом s
if length(skluch)>0 then with treeview1 do Begin
// Отметим красным цветом найденный узел
for i:=0 to items.count-1 do Begin
if pos(s,items[i].text)>0 then Begin
rect1:=items[i].DisplayRect(true);
color1:=canvas.font.color;
canvas.font.Color:=clred;
canvas.FillRect(rect1);
canvas.
TextOut(rect1.Left,rect1.Top,items[i].text);
canvas.Font.Color:=color1;
break;
end;
end
Showmessage('Найден узел с ключом '
+skluch+' и полем inf='+sitem)
else Showmessage('Узла с ключом '+skluch+
' нет в дереве!');
end;
end;
end.
- Программирование в среде Delphi
- Программирование в среде Delphi
- 1. История развития вычислительной техники, системы счисления и единицы информации.................................................7
- 2. Структура персонального компьютера и операционные системы.........................................................................13
- 3. Основы алгоритмизации и работа в delphi..........................18
- 4. Базовые элементы delphi...................................................................26
- 5. Стандартные функции и подпрограммы................................30
- 6. Операторы delphi......................................................................................33
- 7. Операторы циклов....................................................................................35
- 18. Выделение памяти под объект и прародитель всех классов – tobject..........................................................................................84
- 19. Обработка исключительных ситуаций................................87
- 20. Основные классы и общие свойства компонентов...93
- 26. Технология com.....................................................................................129
- 1. История развития вычислительной техники, системы счисления и единицы информации
- 1.1. История развития вычислительной техники
- 1.2. Системы счисления
- 1.3. Единицы информации
- 2. Структура персонального компьютера и операционные системы
- 2.1. Структура персонального компьютера.
- 2.2. Операционные системы
- 3. Основы алгоритмизации и работа в delphi
- 3.1. Основы программирования
- 3.2. Программирование в среде Delphi
- 4. Базовые элементы delphi
- 4.1. Алфавит среды Delphi
- 4.2. Константы
- 4.3. Переменные
- 4.4. Основные типы переменных
- 4.5. Операции над переменными и константами
- 5. Стандартные функции и подпрограммы
- 5.1. Математические функции
- 5.2. Функции преобразования
- 5.3. Дополнительные системные подпрограммы и функции
- 6. Операторы delphi
- 6.1. Оператор присваивания
- 6.2. Оператор безусловной передачи управления
- 6.3. Условный оператор if
- 6.4. Оператор разветвления Case
- 6.5. Составной оператор
- 7. Операторы циклов
- 7.1. Оператор цикла For
- 7.2. Оператор цикла Repeat
- 7.3. Оператор цикла While
- 8. Работа с массивами
- 9. Работа со строками
- 9.1. Процедуры работы со строками
- 9.2. Функции работы со строками
- 10. Работа с записями
- 11. Процедуры и функции
- 12. Модуль unit
- 13. Работа со множествами
- 14. Работа с файлами
- 14.1. Текстовые файлы
- 14.2. Типированные файлы
- 14.3. Нетипированные файлы
- 15. Работа с файлами и каталогами
- 16. Динамические переменные и структуры данных
- 16.1. Динамические переменные
- 16.2. Работа со стеком
- 16.3. Работа со списками или очередями
- 16.4. Работа с деревьями
- 17. Основы объектно–ориентированного программирования
- 17.1. Объекты и классы
- 17.2. Области видимости класса
- 17.3. Свойства (Property) и инкапсуляция
- 17.4. Методы, наследование и полиморфизм
- 17.5. События (Events)
- 18. Выделение памяти под объект и прародитель всех классов – tobject
- 18.1. Выделение памяти под объект
- 18.2. Описание класса tObject
- 18.3. Операторы приведения типов классов
- 19. Обработка исключительных ситуаций
- 19.1. Два вида оператора Try
- 19.2. Программное создание исключительной ситуации
- 19.3. Основные исключительные ситуации
- 20. Основные классы и общие свойства компонентов
- 20.1. Класс tList
- 20.2. Класс tStrings
- 20.3. Общие свойства компонентов
- 21. Графические возможности delphi
- 21.1. Класс Tcanvas
- 21.2. Классы тGгарhic и тРicture
- 21.3. Классы tFont, tPen и tBrush
- 21.4. Работа с изображениями
- 22. Визуальные компоненты delphi
- 22.1. Компонент tBitBtn
- 22.2. Компоненты tDrawGrid и tStringGrid
- 22.3. Компонент tPageControl
- 22.4. Компонент tTimer
- 22.5. Компонент tGauge
- 22.6. Компонент tСolorGrid
- 23. Стандартные диалоговые окна и типовые диалоги
- 23.1. Стандартные диалоговые окна
- 23.2. Типовые диалоги
- 24. Форма, приложение и глобальные объекты
- 24.1. Форма и ее свойства
- 24.2. Объект Application
- 24.3. Глобальные объекты
- Объект ClipBoard
- Объект Screen
- Объект Printer
- 25. Межпрограммное взаимодействие
- 25.1. Обмен сообщениями
- 25.2. Динамический обмен данными
- 25.3. Совместное использование общей памяти
- 25.4. Каналы
- 25.5. Сокеты
- 26. Технология com
- 26.1. Интерфейс
- 27. Технология автоматизации
- 27.1. Основы ole Automation
- 27.2. Примеры использования серверов автоматизации
- 27.3. Компоненты ActiveX
- 28. Динамические библиотеки
- 28.1. Создание dll
- 28.2. Использование dll
- 28.3. Пример написания dll
- 29. Работа с базами данных
- 29.1. Основные определения
- 29.2. Взаимодействие приложения на Delphi с базами данных
- 29.3. Компоненты взаимодействия с базами данных
- If adoTable1.Locate(’fio,stag’,varArrayOf([’Иванов’,’10’]),[])Then …;
- 29.4. Работа с локальной базой данных
- 30. Основы языка sql
- 30.1. Составные части sql
- 30.2. Команда select
- 30.3. Пример использования запросов в Delphi
- 31. Создание собственных компонентов
- 32. Работа с реестром
- 33. Перспективы программирования в delphi
- Литература
- 220013, Минск, п.Бровки, 6