Поиск заданного узла в дереве
Задача поиска заданного узла в сформированном дереве сводится к сравнению искомого числа с информационными частями очередных узлов дерева. Добавим в описание переменных предыдущей программы три переменные:
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}
Дата добавления: 2015-08-08; просмотров: 493;