ТОР 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 как в первом случаи, т.е. будет указывать на барьер. Типичный пример программы использ. динамичное размещение переменных с доступа к ним через ссылки. Задачей частотной словаря можно наз. поиск по дереву с включением.
Не нашли, что искали? Воспользуйтесь поиском:
|