12.2.1. Упорядоченные деревья. Поиск по дереву с включением

Упорядоченным называется дерево, у которого для каждого узла N значение левого дочернего узла меньше, чем значение в N, а значение правого дочернего узла больше значения в N. Если в дереве могут содержаться одинаковые значения, то программист сам должен определить, влево или вправо помещать значение, равное значению в родительском узле, то есть соответствующее строгое неравенство заменить на нестрогое.

Построение упорядоченного дерева начинается с корня. Первое из входящих значений и будет значением корня. Для каждого следующего значения производится, начиная с корня, сравнение со значением в очередном узле. Если оно меньше или равно значению в узле, то переходим в левое поддерево, иначе — в правое. Эти переходы и сравнения продолжаются до тех пор, пока не придем к ссылке, которая равна Nil. Тогда создается новый узел. Этот алгоритм, реализованный в виде рекурсивной процедуры, приведен в листинге 12. 2.

Листинг 12.2. Процедура вставки в упорядоченное дерево

procedure Insert(var t: TNode; i: TKey);

var p: TNode;

begin

if t=Nil then begin

new(t); // создание нового узла

with t^ do begin

key:=i; left:=Nil; right:=Nil // полей узла

end;

end

else

if i <= t^.key then Insert(t^.left,i) // переход к левому поддереву

else Insert(t^.right,i); // переход к правому поддереву

end;

Следует отметить, что в данной процедуре параметр t передается как параметр‑переменная, а не как параметр‑значение в процедурах листинга 12.1. Это существенно, поскольку в случае включения нового узла параметру‑переменной должно присваиваться новое значение — ссылка на включенный узел, старое значение параметра было равно Nil.

На рис. 12.2 приведена форма, содержащая следующие компоненты:

• компонент Edit, в котором вводятся значения для узлов дерева;

• компонент TgroupBox, объединяющий два компонента TradioButton, которые позволяют построить дерево выбранным способом;

• кнопка Нарисовать дерево, при нажатии на которую на форме рисуется дерево.

Построение упорядоченного дерева производится с помощью приведенной выше процедуры Insert. Рисование же дерева использует алгоритм обхода дерева Сверху вниз, поэтому рисование начинается с корня дерева, затем рисуются узлы ниже лежащих уровней. При рисовании узла запоминаются его координаты, которые используются как при рисовании ветвей текущего дерева, так и при повторном рисовании дерева, если менять мышкой положение его узлов на форме. Основные процедуры приведены в листинге 12.3.

Листинг 12.3. Рисование дерева

type TKey=integer;

TNode=^PNode;

PNode=record

key : TKey;

xN,yN: integer; // координаты узла на канве

left, right: TNode;

end;

const diametr = 25; // диаметр рисуемого узла

Geom = 1.5; // геометрический параметр для наклона ветвей

var

x1,y1: integer; // координаты узла дерева

step: integer; // расстояние между уровнями дерева

first: Boolean; // первый раз рисуется дерево или нет

Drawing: Boolean; // разрешается ли рисование дерева

PMin: TNode; // перемещаемый мышкой узел

var t,p,r, Tree: TNode;

i: TKey;

s: String;

procedure TForm1.DrawNode(x1,y1: integer; s: String);

// рисование узла дерева, s - информационная часть узла

var len,xPlus: integer;

begin

len:=Length(s);

xPlus:=len*3;

with Form1.canvas do begin

brush.Style:=bsSolid;

Brush.Color:=clBtnFace;

MoveTo(x1,y1);

Ellipse(x1,y1,x1+diametr,y1+diametr);

TextOut(x1+diametr div 2-xPlus ,y1+diametr div 5,s);

end;

end;

procedure TForm1.DrawBranch(x1,y1: integer; lr: Boolean; LnBr: TPoint);

var h,l: integer;

begin

if first then begin

h:=step;

with Form1.canvas do begin

brush.Style:=bsSolid;

Brush.Color:=clBlack;

MoveTo(x1,y1);

if lr then LineTo(x1-h,y1+round(Geom*h))

else LineTo(x1+h,y1+round(Geom*h));

end

end

else begin // повторное рисование

with Form1.canvas do begin

brush.Style:=bsSolid;

Brush.Color:=clBlack;

MoveTo(x1,y1);

if lr then begin

h:= LnBr.x; l:= LnBr.y+diametr div 2;

LineTo(h,l)

end

else begin

h:= LnBr.x+diametr; l:= LnBr.y+diametr div 2;

LineTo(h,l);

end

end

end; // if first

end;

procedure TForm1.DrawTree(t: TNode; x1,y1: integer);

var lb : TPoint;

StrKey : String;

begin

if first then begin

if t<>nil then begin

StrKey:=IntToStr(t^.key);

Form1.DrawNode(x1,y1,StrKey);

t.xN:=x1; t.yN:=y1; // запомнить координаты узла

Sleep(500); // медленно рисуем первый раз

if t.left<>nil then begin

Form1.DrawBranch(x1,y1+diametr div 2,true,lb)

end;

if t.right<>nil then begin

Form1.DrawBranch(x1+diametr,y1+diametr div 2,false,lb)

end;

DrawTree(t^.left,x1-step,y1+round(Geom*step));

DrawTree(t^.right,x1+step,y1+round(Geom*step));

end;

end

else begin // повторное рисование

if t<>nil then begin

StrKey:=IntToStr(t^.key);

Form1.DrawNode(x1,y1,StrKey);

if t.left<>nil then begin

lb.x:=t.left.xN; lb.y:=t.left.yN;

Form1.DrawBranch(x1,y1+diametr div 2,true,lb)

end;

if t.right<>nil then begin

lb.x:=t.right.xN; lb.y:=t.right.yN;

Form1.DrawBranch(x1+diametr,y1+diametr div 2,false,lb)

end;

if t^.left<> nil then

DrawTree(t^.left,t.left.xN,t.left.yN);

if t^.right<> nil then

DrawTree(t^.right,t.right.xN,t.right.yN);

end;

end;

end;

procedure TForm1.BtnPrintClick(Sender: TObject);

begin

// рисование дерева

with canvas do begin

Brush.Style:=bsSolid;

Brush.Color:=clBtnFace;

FillRect(Rect(0,0,Width,Height));

end;

x1:=Width div 2 - diametr; y1:=150; step:=30;

first:=true;

DrawTree(Tree, x1, y1 div 2);

first:= false;

end;

В процессе рисования один узел может наложиться на другой. Поэтому программа предусматривает перемещение узла мышкой. Соответствующие процедуры приведены в листинге 12.4.

Листинг 12.4. Перемещение мышкой узла дерева

procedure TForm1.FormMouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

var Min,r: real;

procedure MinSearch(t: TNode);

begin

if t<>NIL then begin

r:=sqr(t.xN-x)+sqr(t.yN-y);

if r<=Min then begin

Min:=r; PMin:=t;

end;

MinSearch(t.left);

MinSearch(t.right);

end;

end; // MinSearch

begin

Canvas.MoveTo(x,y);

Min:= sqr(Width)+sqr(Height);

PMin:=Tree;

MinSearch(Tree);

Drawing:=True;

end;

procedure TForm1.FormMouseMove(Sender: TObject; Shift: TShiftState; X,

Y: Integer);

begin

if Drawing then begin

with canvas do begin

Brush.Style:=bsSolid;

Brush.Color:=clBtnFace;

FillRect(Rect(0,0,Width,Height));

end;

PMin.xN:=x-round(diametr div 2); PMin.yN:=y-round(diametr div 2);

DrawTree(Tree,Tree.xN,Tree.yN);

end;

end;

procedure TForm1.FormMouseUp(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

begin

Drawing:=false;

end;

При нажатии на левую клавишу мышки (процедура FormMouseDown) сначала нужно определить координаты узла, который будет перемещаться. Это делается с помощью процедуры MinSearch, которая представляет собой процедуру обхода дерева и ищет узел, расстояние от которого до указателя мышки минимально. В завершение работы процедура FormMouseDown поднимает флажок разрешения перемещения узла, устанавливая глобальную переменную Drawing = true.

Движение мышки с нажатой левой клавишей (процедура FormMouseMove) очищает форму и рисует дерево заново. При повторном рисовании дерева используются координаты узлов на канве: как те, что были запомнены при первом рисовании, так и те, что изменились при перемещении узла (узлов) мышкой. Рисование ветвей при повторном изображении дерева тоже меняется. Первичное и повторное рисование определяется булевской переменной first в процедурах DrawBranch и DrawTree.