Матрица статей        Список статей        Всячина        Контакты       

Двоичные деревья


Двоичное дерево

Ярким примером конструктивного фрактала является двоичное дерево. Оно строится по следующему принципу: на каждом уровне вертикальная линия разделяется на две с показателем уменьшения , Такие разветвленные фракталы называются дендритами (в переводе с греческого «dendron» — дерево). Что бросается в глаза, при рассмотрении фрактала-дендрита, то это самоподобность: каждая ветвь в отдельности представляет собой все дерево в целом. А самоподобие является одним из основных свойств фракталов.

Разбиение какого-либо множества на группы из двух элементов или комбинирование в группы из двух элементов, характерно для двоичной системы счисления. Это разбиение часто применяется на практике, например, при спортивных командных соревнований. Команды разбиваются попарно, в паре определяется победитель, оставшиеся команды снова разбиваются, итак далее, пока не останется команда-победитель. Таким образом мы получили перевернутое двоичное дерево. Двоичное дерево является, одним из самых простых примеров семейства фракталов, в котором структура системы счисления представлена геометрически. Можно также построить троичное, четвертичное и т. д. деревья.

Приведём программу построения двоичного дерева, представленного на рисунке.

program DD;
uses Graph, CRT;
const
  min = 1;
var
 gd, gm : Integer;

procedure Draw(x, y, l : Integer);
begin
  if KeyPressed then 
    exit;
  If l > min then
  begin
    l := l div 2;
    line(x, y, x, y - l);
    line(x, y - l, x - l, y - l);
    line(x, y - l, x + l, y - l);
    Draw(x - l, y - l, l);
    Draw(x + l, y - l, l);
  end;
end;

begin
   gd := Detect;
   InitGraph(gd, gm, '');
   Draw(320, 460, 300);
   ReadKey;
   CloseGraph;
end.

Существуют и другие представления двоичного дерева, это H-дерево и V-дерево.

H-дерево строится следующим образом: берем единичный отрезок, и на первом шаге два более коротких отрезка помещаем перпендикулярно концам первоначального так, чтобы образовалась буква H. И так до бесконечности.

На рисунке показано 9 шагов построения, с показателем уменьшения . Программа использует рекурсивный алгоритм построения.


H-дерево

program Hfract;
uses Graph,CRT;
procedure Fractal(x, y, l: Integer);
begin
  if KeyPressed then
    Exit;
  if  l > 4 then
  begin
    l := l div 2;
    Line(x, y, x+l, y);
    Line(x, y, x-l, y);
    Line(x + l, y, x + l, y - l div 2);
    Line(x + l, y, x + l, y + l div 2);
    Line(x - l, y, x - l, y - l div 2);
    Line(x - l, y, x - l, y + l div 2);
    Fractal(x + l, y - l div 2, l);
    Fractal(x + l, y + l div 2, l);
    Fractal(x - l, y - l div 2, l);
    Fractal(x - l, y + l div 2, l);
  end;
end;
var
  gd, gm: Integer;
begin
  gd := detect;
  InitGraph(gd, gm, 'c:\bp\bgi');
  SetColor(15);
  Fractal(320,240,256);
  ReadKey;
  CloseGraph;
end.

Для построения V-дерева используется фрагмент вида буквы V. Принцип построения виден из рисунка.


V-дерево

program Vderevo;
uses Graph, CRT;
const
  min = 3;
var
  gd, gm : Integer;

procedure LineTo1(x, y : Integer; l, u : Real);
begin
  Line(x, y, Round(x + l * cos(u)), Round(y - l * sin(u)));
end;

procedure Draw(x, y : Integer; l : Real);
begin
  if KeyPressed then 
    exit;
  if l > min then
  begin
    l := l * 0.5;
    LineTo1(x, y, l, pi / 4);
    LineTo1(x, y, l, 3 * pi / 4);
    Draw(Round(x - l * cos(pi/4)), 
      Round(y- l * sin(pi/4)), l);
    Draw(Round(x + l * cos(pi/4)), 
      Round(y- l * sin(pi/4)), l);
  end;
end;

begin
  gd := Detect;
  InitGraph(gd, gm, 'c:\bp\bgi');
  Draw(320, 380, 400);
  ReadKey;
  CloseGraph;
end.

Дерево Пифагора также является двоичным деревом.

По аналогии можно построить троичное дерево и так далее.


Троичное дерево

program DTr;

uses Graph, CRT;

const
  max = 5;

var
  gd, gm : Integer;

procedure LineTo1(x, y, l, u : Real);
begin
   Line(Round(x), Round(y), Round(x + l * cos(u)), Round(y - l * sin(u)));
end;

procedure Draw(x, y : Integer; l, u : Real);
begin
  if KeyPressed then 
    exit;
  if l > max then 
    begin
        l := l * 0.37;
  Lineto1(x, y, l, u);
  x := round(x + l * cos(u));
  y := round(y - l * sin(u));
  Draw(x, y, l + l / 3, u + 4 * pi/3);
  Draw(x, y, l + l / 3, u - 4 * pi/3);
  Draw(x, y, l + l / 3, u);
   end;
end;

begin
   gd := Detect;
   InitGraph(gd, gm, '');
   Draw(320, 240, 300, pi/2);
   Draw(320, 240, 300, pi/2 + 4 * pi/3);
   Draw(320, 240, 300, pi/2 - 4 * pi/3);
   ReadKey;
   CloseGraph;
end.

Фрактал из прямоугольников

program Pr;
uses Graph, CRT;
const
  min = 2;
var
  gd, gm : Integer;

procedure Draw(x, y, l : Integer);
begin
  if KeyPressed then 
    exit;
  if l > min then 
  begin
    l := l div 2;
    SetFillStyle(1, 1);
    Bar(x, y, x + l, y - l * 2);
    SetFillStyle(1, 15);
    Bar(x, y, x - l, y - l * 2);
    Draw(x - l div 2, y - l, l);
    Draw(x + l div 2, y - l, l);
  end;
end;

begin
  gd := Detect;
  InitGraph(gd, gm, 'c:\bp\bgi');
  Draw(320, 350, 256);
  ReadKey;
  CloseGraph;
end.

program Tree;

uses Graph;

procedure LinePolar(r1 : Real; a1 : Real; r2 : Real; a2 : Real);
begin
     Line(
          Round(320 + r1 * cos(a1)),
          Round(240 - r1 * sin(a1)),
          Round(320 + r2 * cos(a2)),
          Round(240 - r2 * sin(a2)));
end;

function pow(d : Real; n : Integer) : Real;
var
   i : Integer;
   result : Real;
begin
     result := 1.0;
     for i := 1 to n do begin
         result := result * d;
     end;
     pow := result;
end;

function radius(s : Real; r : Real; i : Integer): Real;
begin
     radius := s * (1 - pow(r, i)) / (1 - r);
end;

function angle(d : Integer; i : Integer; j : Integer) : Real;
begin
     angle := 2 * pi / pow(d, i) * (j - (pow(d, i) - 1) / 2);
end;


procedure Draw(n : Integer; d : Integer; r : Real; s : Integer);
var
   i, j : Integer;
   r1, r2, a1, a2 : Real;

begin
     for i := 1 to n do begin
         r1 := radius(s, r, i);
         r2 := radius(s, r, i - 1);
         for j := 0 to Round(pow(d, i)) - 1 do begin
             a1 := angle(d, i, j);
             a2 := angle(d, i - 1, j div d);
             LinePolar(r1, a1, r2, a2);
         end;
     end;
end;

var
   gd, dm : Integer;

begin
     gd := Detect;
     InitGraph(gd, dm, 'd:\tp7\bgi');
     Draw(3, 8, 0.8, 90);
     ReadLn;
     CloseGraph;
end.


Смотрите также:

Ссылки:

  • H-Fractal .
  • Морозов А. Д. Введение в теорию фракталов. — Москва-Ижевск: Институт компьютерных исследований, 2002, 12—18.
  • k-Cayley Trees .