Поиск заданного узла в дереве

Задача поиска заданного узла в сформированном дереве сводится к сравнению искомого числа с информационными частями очередных узлов дерева. Добавим в описание переменных предыдущей программы три переменные:

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; просмотров: 534;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.009 сек.