Pascaler
О проекте Теоретический материал Тестирование Архив задач
Войти в личный кабинет



О проекте


Преподавателям


Смотрите информацию подарочный сертификат спа спб у нас.

Тема: Основные понятия.

Граф – это непустое множество точек (вершин) и множество отрезков (ребер), концы которых принадлежат заданному множеству точек.

Если на каждом ребре задать направление, то граф будет ориентированным.

 

Если, двигаясь по ребрам графа в заданном направлении, можно попасть из заданной вершины 1 в заданную вершину 2, то говорят, что эти вершины соединены путем.

Замкнутый путь, состоящий из различных ребер, называется циклом.

Граф называется связным, если любые две его вершины соединены путем.

Связный граф без циклов называется деревом.

С каждой вершиной дерева связывается конечное число отдельных деревьев, называемых поддеревьями.

Рассмотрите пример дерева, в узлах которого располагаются символы.

Для дальнейшей работы с деревьями необходимо определить ряд понятий.

  • Вершина у, находящаяся непосредственно ниже вершины х, называется непосредственным потомком х, а вершина х называется предком у.


  • Если вершина не имеет потомков, то она называется терминальной вершиной или листом, если имеет, то называется внутренней вершиной.


  • Количество непосредственных потомков внутренней вершины называется ее степенью.


  • Степенью дерева называется максимальная степень всех вершин.

Например,

  • вершины F, D, E являются непосредственными потомками вершины В;


  • вершины F, D, E являются листьями;


  • вершины C, G, H – внутренние;


  • степень вершины В – 3, а вершины Н – 1;


  • степень дерева равна 3.

Определение. Двоичное дерево – это дерево, в котором из каждой вершины исходит не более двух ребер.

Задание. Наберите текст программы на компьютере и рассмотрите ее действие. Данная программа демонстрирует создание произвольного двоичного дерева.

Program DemidenkoS;
Uses
  Crt, Graph;
Const
  Arr : array [1..6] of integer=(160,80,40,20,10,5);
  Arr1 : array [1..6] of integer=(120,80,70,60,50,40);
Type
  ss=^sp;
  sp=record
       elem:byte;
       Next : array[1..2] of ss;
  end;
Var
  a, b, c, d : longint;
  s : string;
  grDriver : integer;
  grMode : integer;
  a1, b1 : real;
  x, Some, Max, Min : ss;
Procedure Zap(y : ss; n : integer);
Var
  aa,bb:integer;
Begin
  y^.elem:=random(99)+1;
  bb:=random(3);
  if n<1
    then
      bb:=2;
        if n<a
          then
            for aa : =1 to bb do
              begin
                new(y^.next[aa]);
                y^.next[aa]^.next[1]:=nil;
                y^.next[aa]^.next[2]:=nil;
                zap(y^.next[aa],n+1);
              end;
End;
Procedure Strel(x1, y1 : integer; k : Real);
Var
  aa : Real;
Begin
  aa:=arctan(k);
  if k>0
    then
      begin
        line(x1,y1,x1+round(10*cos(aa+pi/18)), y1-round(10*sin(aa+pi/18)));
        line(x1,y1,x1+round(10*cos(aa-pi/18)), y1-round(10*sin(aa-pi/18)));
        line(x1+round(10*cos(aa+pi/18)),y1- round(10*sin(aa+pi/18)),x1+ round(10*cos(aa-pi/18)),y1- round(10*sin(aa-pi/18)));
      end
    else
      begin
        aa:=-aa;
        line(x1,y1,x1-round(10*cos(aa+pi/18)), y1-round(10*sin(aa+pi/18)));
        line(x1,y1,x1-round(10*cos(aa-pi/18)), y1-round(10*sin(aa-pi/18)));
        line(x1-round(10*cos(aa+pi/18)),y1- round(10*sin(aa+pi/18)),x1- round(10*cos(aa-pi/18)),y1- round(10*sin(aa-pi/18)));
      end
end;
Procedure Wiv(y : ss; n, x1, y1 : integer);
Var
  spi : ss;
Begin
  SetColor(n+1);
  Circle(x1,y1,10);
  Str(y^.elem, s);
  if length(s)=2
    then
      OutTextXY(x1-6, y1-2, s)
    else
      OutTextXY(x1-3, y1-2, s);
        if n<a
          then
            begin
              if y^.next[1]<>nil
                then
                  begin
                    SetColor(n+1);
                    Line(x1,y1+10,x1-(arr[n] div 2),y1+((arr1[n]-20) div 2)+10);
                    SetColor(n+2);
                    Line(x1-(arr[n] div 2),y1+((arr1[n]-20) div 2)+10,x1-arr[n],y1+arr1[n]-10);
                    Strel(x1-arr[n],y1+arr1[n]-10, (arr1[n]-20)/arr[n]);
                    Wiv(y^.next[1],n+1,x1-arr[n],y1+ arr1[n]);
                  end;
              if y^.next[2] <> nil
                then
                  begin
                    SetColor(n+1);
                    Line(x1,y1+10,x1+arr[n],y1+arr1[n]-10);
                    SetColor(n+2);
                    Line(x1+(arr[n] div 2),y1+((arr1[n]-20) div 2)+10,x1+arr[n],y1+arr1[n]-10);
                    Strel(x1+arr[n],y1+arr1[n]-10,- (arr1[n]-20)/arr[n]);
                    Wiv(y^.next[2],n+1,x1+arr[n],y1+ arr1[n]);
                  end;
           end;
end;
Begin
  ClrScr;
  Randomize;
  Repeat
  new(x);
  a:=6;
  x^.next[1]:=Nil;
  x^.next[2]:=Nil;
  Zap(x,0);
  Max:=x;
  Min:=x;
  writeln;
  grDriver := Detect;
  InitGraph(grDriver, grMode,'c:tp7bgi');
  SetFillStyle(solidfill,15);
  SetColor(15);
  Wiv(x,1,320,50);
  Delay(5000);
  until KeyPressed;
End.

Задание. Поэкспериментируйте над предложенной программой, внося свои изменения. Результат покажите учителю.

Вернуться назад
2003—2012 © Группа «Vimedia»
Проект «Pascaler» — лучший на ХI Всероссийской конференции молодых исследователей с международным участием «Шаг в будущее», Россия, Москва, 12 – 16 апреля 2004г.