24.01.2013, 15:42 | #1 (permalink) |
Новичок
Регистрация: 24.01.2013
Сообщений: 2
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
Построить оптимальное дерево поиска
И можно ли это переделать под оптимальное дерево поиска? Код: Код:
Program Tree; Uses Crt; {Варианты запуска обхода с подсчетом: 1 - количество вершин, имеющих хотя бы одну ненулевую связь; 2 - количество вершин, имеющих две ненулевые связи; 3 - количество вершин, имеющих не более одной ненулевой связи. } Const AtLeastOne=1; Two=2; NoMoreThanOne=3; Type inform = Integer; ss = ^zveno; zveno = Record key: Integer; inf: Inform; left, right: ss; End; Var t: ss; n,c, i: Integer; {----формирование дерева----} Procedure Insert (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 Insert (p^. left,x); End; If x>=p^. inf Then Begin Insert (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 Else Begin { Рассматриваются варианты вызова функции с соответствующими условием} { Первый вариант - либо left, либо right не равны Nil } If ( (v = AtLeastOne) and ( (p^. left <> Nil) or (p^. right <> Nil))) or { Второй вариант - и left, и right не равны Nil } ( (v = Two) and ( (p^. left <> Nil) and (p^. right <> Nil))) or { Третий вариант - либо left, либо right равны Nil } ( (v = NoMoreThanOne) 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 ('Введите количество элементов дерева: '); Readln (n); randomize; For i:=1 To n Do Begin Writeln ('Введите элемент дерева'); Read (c); Insert (t,c); End; Print (t,0); Writeln ('Количество вершин с >= 1 ненулевой связью: ',Count (t,AtLeastOne)); Writeln ('Количество вершин с 2-мя ненулевыми связями: ',Count (t,Two)); Writeln ('Количество вершин с <= 1 ненулевой связью: ',Count (t,NoMoreThanOne)); Readkey; End. |
24.01.2013, 15:42 | |
Helpmaster
Member
Регистрация: 08.03.2016
Сообщений: 0
|
Дам вам ссылки на темы, которые имеют что то общее с вашей темой Как построить убежище? Приложение для поиска песен Shazam |
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
|
|