| ВНИМАНИЕ | Для заказа программы на двоичное поисковое дерево пишите на мой электронный адрес proglabs@mail.ru |
Посмотрим на следующее бинарное дерево поиска, состоящие из $15$ узлов. Ключами вершин выступают целые числа ( в данном случае даже натуральные числа ).
➡ Мне нужен алгоритм поиска элемента в бинарном дереве. Сразу нужно подумать о том, что должна возвращать поисковая функция!
Очевидно, что для поиска нужно указать значение ключа. В результате поиска можно получить только $2$ ситуации:
| узел, имеющий заданное поисковое значение ключа, найден в дереве | дерево не содержит узла с заданным поисковым ключевым значением |
1 ситуация
Если вершина с заданным поисковым ключом обнаружена в дереве, то надо вернуть указатель на эту вершину. Это позволит после поиска производить над ней нужную обработку, например, вывести ключ или данные на экран ( или в файл ), или изменить нужные данные на новые ( обновить информацию в узле ). С этим разобрались!
2 ситуация
Если вершина с заданным поисковым ключом не обнаружена в дереве, то следует вернуть нулевой указатель ( в языке программирования С — NULL-указатель, например ). С этим тоже разобрались!
➡ Да, еще нужно помнить о таком моменте: я рассматриваю бинарные деревья поиска, которые не содержит дублирующих узлов по ключу, то есть все вершины имеют уникальные ключевые значения.
Допустим, я хочу найти узел с ключом равным $56$. Проверим визуально, содержит ли заданное дерево вершину с этим ключом.
Видно, что, да, содержит. Искомая вершина выделена желтым цветом.
Отследим траекторию движения от корня дерева до искомой вершины с ключом $56$.
Алгоритм поиска схож с алгоритмом вставки. Продвигаемся вглубь дерева, сравнивая ключ искомого узла с ключом текущего узла. Если искомый ключ меньше текущего — идем влево, иначе — вправо.
| # | Сравниваемые ключи | Направление спуска |
| 1 | $56 > 22$ | вправо |
| 2 | $56 < 91$ | влево |
| 3 | $56 > 44$ | вправо |
| 4 | $56 > 45$ | вправо |
| 5 | $56 < 62$ | влево |
| 7 | $56 = 56$ | узел найден |
💡 Нужно помнить о том, что рекурсивная функция должна вернуть указатель на найденный узел, а не указатель на корень дерева.
Допустим, сейчас я хочу найти в этом двоичном поисковом дереве узел с ключом равным $30$. Посмотрим, к какому результату приведет этот поиск.
| # | Сравниваемые ключи | Направление спуска |
| 1 | $30 > 22$ | вправо |
| 2 | $30 < 91$ | влево |
| 3 | $30 < 44$ | влево |
| 4 | $30 > 23$ | вправо |
| 5 | NULL | узел не найден |
А это моя программная реализация на языке «чистый» Си рекурсивной функции поиска элемента в бинарном дереве по ключу:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
//------------------------------------------------------------------------------ // поиск узла в дереве по ключу // в случае успешного поиска возвращается константный указатель на найденный узел // если узла с заданным ключом нет, то возвращается нулевой указатель //------------------------------------------------------------------------------ const Node* Search_node( const Node* const root, const int key ) { // если спустились в дереве ниже листа, то узла с искомым ключом нет в дереве if ( root == NULL ) { return NULL; } // поиск завершился успехом; в качестве ответа возвращаем указатель на текущий узел if ( key == root -> key ) { return root; } // спускаемся по дереву, сравнивая заданный ключ с ключом в текущем узле if ( key < root -> key ) { return Search_node( root -> left, key ); } else { return Search_node( root -> right, key ); } } //------------------------------------------------------------------------------ |
Пишите в комментариях, с какими типами поиска элементов в двоичном дереве вы сталкивались на практике. А также задавайте уточняющие вопросы.
| ВНИМАНИЕ | Для заказа программы на двоичное поисковое дерево пишите на мой электронный адрес proglabs@mail.ru |
Добавить комментарий