Бинарное дерево поиска

       Then Count:=1 + Count(p^.left,v) + Count(p^.right,v)

       { Иначе берём 0 и  добавляем рекурсивные  вызовы }

       else Count:=0 + Count(p^.left,v) + Count(p^.right,v)

       End;

       End; 

       В процедуру встроен счетчик Count, который по окончании работы программы выдает искомый результат. 

       РАЗДЕЛ  3. Рабочая программа, с комментариями 

Programderevo;

UsesCrt; 

{Варианты запуска обхода с подсчетом:

1 - количество вершин, имеющих хотя бы  одну ненулевую  связь;

2 - количество вершин, имеющих две ненулевые  связи;

3 - количество вершин, имеющих не более  одной ненулевой  связи.} 

ConstNeMensheOdnoj=1;

Dve=2;

NeBolsheOdnoj=3; 

Type inform = Integer;

ss = ^zveno;

zveno = Record

key: Integer;

inf: Inform;

left, right: ss;

End; 

Var t:ss;

n,nn,c,i,k: Integer; 
 

{----формированиедерева----} 

Procedure Vstavka (Var p: ss; x: Integer);

Begin

If p = Nil Then

Begin

New (p);

p^.inf:=x;

p^.key:=1;

p^.left:=Nil;

p^.right:=Nil;

End

else begin

If x<p^.inf Then Begin Vstavka (p^.left,x); End;

If x>=p^.inf Then Begin Vstavka (p^.right,x); End;

end;

End; 

{----выводдерева----} 

Procedure Print (Var p: ss; h: Integer);

Var i: Integer;

Begin

If p <> Nil Then

Begin

Print(p^.right,h+4);

For i:=1 To h Do Write (' ');

Writeln (p^.inf);

Print (p^.left,h+4);

End;

End; 

{ Рекурсивная функция,  делающая подсчёт для текущего дерева }

Function Count(p: ss; v: integer):integer;

Begin

{ Нет элемента -- результата ноль }

IF p = Nil Then Count:=0

ElseBegin

{ Рассматриваются  варианты вызова  функции с соответствующими  условием}

{ Первый вариант  -- либо left, либо right не  равны Nil }

If ((v = NeMensheOdnoj) and ((p^.left<> Nil) or (p^.right<> Nil)))

or

{ Второй вариант  -- и left, и right не равны Nil  }

((v = Dve) and ((p^.left<> Nil) and (p^.right<> Nil)))

or

   { Третий вариант  -- либо left, либо right равны  Nil  }

((v = NeBolsheOdnoj) and ((p^.left = Nil) or (p^.right = Nil)))

{ Какой-то из вариантов  сработал => ставим 1

и добавляем результаты рекурсивных вызовов левой и правой ветви}

Then Count:=1 + Count(p^.left,v) + Count(p^.right,v)

{ Иначе берём 0 и  добавляем рекурсивные  вызовы }

else Count:=0 + Count(p^.left,v) + Count(p^.right,v)

End; 

End; 

{----обходдерева----} 
 

Begin ClrScr;

Writeln ('Vvedite koli4estvo elementovdereva: ');

Readln (n);

randomize;

For i:=1 To n Do

Begin

Writeln('Vvedite o4erednoj element');

Read (c);

Vstavka (t,c);

End;

Print (t,0); 

Writeln('Koli4estvo vershin c >= 1 nenulevojsvjazi: ',Count(t,NeMensheOdnoj));

Writeln('Koli4estvo vershin c 2 nenulevymisvjazjami: ',Count(t,Dve));

Writeln('Koli4estvo vershin c <= 1 nenulevojsvjazi: ',Count(t,NeBolsheOdnoj)); 

Readkey;

End. 
 

       РАЗДЕЛ  4.Описание интерфейса программы 
 

       При запуске программы пользователь увидит форму с полем для ввода количества элементов дерева (Рис. 5).  

       

       Рис. 5 «Рабочее окно программы»

       Затем поочередно вводим необходимые данные(Рис. 6).

       

       Рис.6 «Ввод данных»

       

       Рис. 7«Вывод результата работы программы на экран» 

       После нажатия Enterпрограмма будет выдавать графическое представление дерева, а также искомые величины.(Рис. 7) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

       ВЫВОДЫ 

            В данной курсовой  работе была  создана  программа в среде  TurboPascal, которая позволяет создавать бинарное дерево и выполнять с ним следующие операции: добавлять элементы дерева, выводить дерево на экран, выполнять обход дерева   сверху вниз.   При обходе подсчитывать:количество вершин, имеющих хотя бы одну ненулевую связь, количество вершин, имеющих две ненулевые связи, количество вершин, имеющих не более одной ненулевой связи. Были описаны алгоритмы выполнения этих операций. Для решения этой задачи была прочитана соответствующая литература. Я приобрел опыт в работе с компонентами среды TurboPascal, и познакомилась с некоторыми приемами программирования. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

       СПИСОК  ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ   

1. Ахо А.А., Хопкрофт  Д.Э., Ульман Д.Д. Структуры данных  и алгоритмы. М.: Вильямс, 2000. 

2. Беллман Р.  Динамическое программирование. M. ИЛ, 1960.  

3. Бежанова М.М,  Москвина Л.А.. Практическоепрограмирование. Приемы создания программ на языке Паскаль. М..Научный Мир. 2000. – 270 с. 

4.Подвальный С.Л.,Холопкина Л.В., Носачева М.П.Программирование на языке паскаль:практикум. Воронеж. ГОУВПО ВГТУ. 2008. 

5.Информация с Веб-сайта http://www.lib.csu.ru. 

6. Информация с Веб-сайта http://algolist.manual.ru/sort/pyramid_sort.php;