Поиск узла бинарного дерева поиска
Бинарное дерево поиска не имеет индекса, поэтому для операции поиска в бинарном дереве поиска здесь определён метод contain, чтобы определить, содержит ли бинарное дерево поиска определённый элемент, возвращая переменную типа boolean. Эта операция поиска также является рекурсивным процессом. Конкретная реализация кода выглядит следующим образом:
// Проверяет, содержит ли двоичное дерево поиска с корнем в node узел со значением ключа key, используя рекурсивный алгоритм
private boolean contain(Node node, Key key){
if( node == null )
return false;
if( key.compareTo(node.key) == 0 )
return true;
else if( key.compareTo(node.key) < 0 )
return contain( node.left , key );
else // key > node->key
return contain( node.right , key );
}
...
Следующий пример выполняет поиск элемента 43 в бинарном дереве поиска.

(1)Элемент 43 больше корневого узла 42, поэтому нужно продолжить сравнение в правом дочернем узле.

(2)Элемент 43 меньше 59, поэтому нужно продолжить сравнение в левом дочернем узле.


(4)Найдите левый дочерний узел 43 узла 51, который в точности равен, и процесс завершается.
Если нужно найти значение, соответствующее ключу, код выглядит следующим образом:
// Найти значение, соответствующее key, в двоичном дереве поиска с корнем в node, рекурсивный алгоритм
// Вернуть NULL, если значение не существует
private Value search(Node node, Key key){
if( node == null )
return null;
if( key.compareTo(node.key) == 0 )
return node.value;
else if( key.compareTo(node.key) < 0 )
return search( node.left , key );
else // key > node->key
return search( node.right, key );
}
...
Пример кода на Java
Загрузка пакета исходного кода:Скачать
src/example/binary/BinarySearchTreeSearch.java код файла:
/**
* Поиск в бинарном дереве поиска
*/
public class BinarySearchTreeSearch<Key extends Comparable<Key>, Value> {
// Узлы в дереве — приватный класс; внешнему миру не нужно знать конкретную реализацию узлов двоичного дерева поиска
private class Node {
private Key key;
private Value value;
private Node left, right;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
left = right = null;
}
}
// Корневой узел
private Node root;
// Количество узлов в дереве
private int count;
// Конструктор, по умолчанию создаёт пустое двоичное дерево поиска
public BinarySearchTreeSearch() {
root = null;
count = 0;
}
// Вернуть количество узлов в бинарном дереве поиска
public int size() {
return count;
}
// Вернуть, является ли бинарное дерево поиска пустым
public boolean isEmpty() {
return count == 0;
}
// Вставить новую пару данных (key, value) в бинарное дерево поиска
public void insert(Key key, Value value){
root = insert(root, key, value);
}
// Проверить, существует ли key в бинарном дереве поиска
public boolean contain⟦⟧Key(Key key){
return contain(root, key);
}
// Найти в бинарном дереве поиска значение, соответствующее key. Если значение не существует, вернуть null
public Value search(⟦⟧Key key){
return search( root , key );
}
//********************
//* Вспомогательные функции для бинарного дерева поиска
//********************
// Вставка узла (key, value) в бинарное дерево поиска с корнем в node с использованием рекурсивного алгоритма
// Возвращает корень двоичного дерева поиска после вставки нового узла
private Node insert(Node node, Key key, Value value){
if( node == null ){
count ++;
return new Node(key, value);
}
if( key.compareTo(node.key) == 0 )
node.value = value;
else if( key.compareTo(node.key) < 0 )
node.left = insert( node.left , key, value);
else // key > node->key
node.right = insert( node.right, key, value);
return node;
}
// Проверяет, содержит ли двоичное дерево поиска с корнем в node узел со значением ключа key, используя рекурсивный алгоритм
private boolean contain(Node node, Key key){
if( node == null )
return false;
if( key.compareTo(node.key) == 0 )
return true;
else if( key.compareTo(node.key) < 0 )
return contain( node.left , key );
else // key > node->key
return contain( node.right , key );
}
// Найти значение, соответствующее key, в двоичном дереве поиска с корнем в node, рекурсивный алгоритм
// Вернуть NULL, если значение не существует
private Value search(Node node, Key key){
if( node == null )
return null;
if( key.compareTo(node.key) == 0 )
return node.value;
else if( key.compareTo(node.key) < 0 )
return search( node.left , key );
else // key > node->key
return search( node.right, key );
}
}