Очередное число: 15
Очередное число: 4 Очередное число: 9 …….. Очередное число: 0 Отсортированная последовательность: 3 4 4 5 5 7 9 9 14 14 15 16 17 18 20 Программа: Program Bi_Tree; Uses WinCRT; Type TRebro = ^TUzel; TUzel = Record Data : Integer; Left, Right : Rebro; End; Var root, q, v : TRebro; Procedure Order(base: TRebro); процедура просмотра дерева Begin If (base <> Nil) Then Begin Order(base^.Left); Write(base^.Data:5); Order(base^.Right); End; End; Begin ClrScr; New(root); Write('Первое число: '); ReadLn(root^.Data); первое число - в корень дерева root^.Left:=Nil; root^.Right:=Nil; Repeat Write('Очередное число: '); New(v); ReadLn(v^.Data); If (v^.Data = 0) если очередное число - ноль, Then Break; то выходим из цикла ввода v^.Left:=Nil; v^.Right:=Nil; q:=Root; поисковик - в корень дерева While (q <> Nil) Do пока не добрались до листа: Begin If (v^.Data < q^.Data) если введенное число меньшечисла в очередном узле Then If (q^.Left <> Nil) и левая ссылка узла не пуста, Then q:=q^.Left то делаем шаг влево, Else иначе Begin если левая ссылка узла пуста, q^.Left:=v; то подвешиваем туда очередноечисло Break; и выходим из цикла поиска End; If (v^.Data >= q^.Data) если введенное число больше илиравночислу в очередном узле Then If (q^.Right <> Nil) и правая ссылка узла непуста, Then q:=q^.Right то делаем шаг вправо, Else иначе Begin если правая ссылка узла пуста, q^.Right:=v; то подвешиваем туда очередное число Break; и выходим из цикла поиска End; End; {While} Until (False); WriteLn; Writeln('Отсортированная последовательность: '); Order(root); WriteLn; ReadLn; End. Поиск заданного узла в дереве Задача поиска заданного узла в сформированном дереве сводится к сравнению искомого числа с информационными частями очередных узлов дерева. Добавим в описание переменных предыдущей программы три переменные: Var poisk: Integer; искомое число flag: 0..1; флаг поиска; flag=1 – число найдено n: Word; количество найденных одинаковых чисел Искомые числа вводить циклом до ввода 0 – конец поиска: Что искать: 20 Такое число есть Найдено чисел: 1 Что искать: 50 Такого числа нет ......... Что искать: 0 Конец поиска Программа: Program Bi_Tree; Uses WinCRT; Type TRebro = ^TUzel; TUzel = Record Data : Integer; Left, Right : Rebro; End; Var root, q, v : TRebro; poisk: Integer; искомое число flag: 0..1; флаг поиска n: Word; количество найденных одинаковых чисел Procedure Formir_Tree; процедура формирования бинарного дерева Begin New(root); Write('Первое число: '); ReadLn(root^.Data); первое число - в корень дерева root^.Left:=Nil; root^.Right:=Nil; Repeat Write('Очередное число: '); New(v); ReadLn(v^.Data); If (v^.Data = 0) если очередное число - ноль, Then Break; то выходим из цикла ввода v^.Left:=Nil; v^.Right:=Nil; q:=Root; поисковик - в корень дерева While (q <> Nil) Do пока не добрались до листа: Begin If (v^.Data < q^.Data) если введенное число меньшечисла в очередном узле Then If (q^.Left <> Nil) и левая ссылка узла не пуста, Then q:=q^.Left то делаем шаг влево, Else иначе Begin если левая ссылка узла пуста, q^.Left:=v; то подвешиваем туда очередноечисло Break; и выходим из цикла поиска End; If (v^.Data >= q^.Data) если введенное число больше илиравночислу в очередном узле Then If (q^.Right <> Nil) и правая ссылка узла непуста, Then q:=q^.Right то делаем шаг вправо, Else иначе Begin если правая ссылка узла пуста, q^.Right:=v; то подвешиваем туда очередное число Break; и выходим из цикла поиска End; End; {While} Until (False); End; конец процедуры формирования дерева Procedure Order(base: TRebro); процедура просмотра дерева Begin If (base <> Nil) Then Begin Order(base^.Left); Write(base^.Data:5); Order(base^.Right); End; End; конецпроцедуры просмотра дерева Begin основная программа ClrScr; Formir_Tree; обращение к процедуре формирования дерева WriteLn; Writeln('Отсортированная последовательность: '); Order(root); обращение кпроцедуре просмотра дерева WriteLn; Repeat начало цикла поиска Write(‘Что искать: ’); ReadLn(poisk); ввод искомого числа If (poisk = 0) если ввели 0, Then Break; то выходим из цикла поиска q:=root; поисковик – в корень дерева flag:=0; еще ничего не найдено n:=0; ни одного значения не найдено While (q <> Nil) Do пока не добрались до листа: Begin If (q^.Data = poisk) Then еслизначение найдено: Begin flag:=1; n:=n+1; количество найденных одинаковых значений End; If (poisk < q^.Data) спускаемся на следующий узел Then q:=q^.Left Else q:=q^.Right; End; {While} дошли до листа If (flag = 1) Then Begin WriteLn(‘Такое число есть’); WriteLn(‘Найдено чисел: ’, n); End Else WriteLn(‘Такого числа нет’); Until (False); конец цикла поиска ReadLn; End. ©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|