Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Поиск в двоичном дереве.




Функция выдает в результате работы ссылки на узел, содержащий необходимые данные или пустую ссылку, если нужная информация в дереве отсутствует.

function search (tree:Link;key:char):Link;

begin

if tree=nil then search:=nil

else

with tree^ do

if key<data then

search:=search(Left,key)

else

if key>data then

search:=search(Right,key)

else search:=tree;

end;

Т.к. поиск идет по одному единому пути от корня к нужной вершине то его можно программировать с помощью итерации.

function search (tree:Link;key:char):Link;

var endofsearch:Boolean;

begin

endofsearch:=false;

repeat

if tree:=nil then

endofsearch:=tree

with tree^ do

if key<data then tree:=Left

else

if key>data then tree:=Right

else

endofsearch:=true;

intil endofsearch

search:=tree;

end;

Если ключ не найден то результат nil.

function search (tree:Link;key:char):Link;

begin

with (tree<>nil) and (tree^.data<>key) do

if tree^.data<key then

tree:=tree^.Right

else

tree:=tree^.Left;

end;

Как и в случаи поиска в массиве сложность условия окончания наводит о мысли, о барьере.

function search (tree:Link;key:char):Link;

begin

S^.data:=key;

While tree^.data<key

then tree:=tree^.Right

else tree:=tree^.Left

search:=tree;

end;

Если в дереве с корнем 3 ключ со значением key не будет обнаружен т функция search получит значение S, а не nil как в первом случаи, т.е. будет указывать на барьер.

Типичный пример программы использ. динамичное размещение переменных с доступа к ним через ссылки. Задачей частотной словаря можно наз. поиск по дереву с включением.

 






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных