86
Метод
FindNode() представляет собой рекурсивную
процедуру обхода де-
рева с поиском узла, расстояние от которого до
координат указателя мыши
минимально. В завершение работы метод
FormMain_MouseDown устанав-
ливает флажок разрешения перемещения узла
drawing = true.
Обработчик
события FormMain_
MouseMove, связанный с перемеще-
нием мыши при нажатой левой кнопке, обращается к методу
Delta(), изме-
няющему координаты выбранного узла и всех его потомков.
Затем заново
строится изображение дерева. Метод
Delta() представлен в листинге 4.9.
Листинг 4.9. Изменение координат узла и его потомков
public void Delta(Node p, int dx, int dy)
//
смещение поддерева
{
p.x -= dx; p.y -= dy;
if (p.left != null)
Delta(p.left, dx, dy);
if (p.right != null)
Delta(p.right, dx, dy);
}
4.2.2. П
ОИСК ПО ДЕРЕВУ С ВКЛЮЧЕНИЕМ
Эффективность использования структуры упорядоченное дерево мож-
но наглядно продемонстрировать на примере задачи о построении частотного
словаря. Суть этой задачи заключается в построении на
основе заданного
текста упорядоченной последовательности входящих в него слов с указанием
для каждого из них кратности вхождения.
С помощью упорядоченного дерева эту задачу можно решить следую-
щим образом. Последовательно перебирая слова текста, строим дерево, каж-
дый узел которого содержит два информационных поля: слово и кратность
его вхождения. Для каждого очередного слова производится поиск в дереве.
Если слово найдено, то увеличивается значение поля кратности вхождения у
соответствующего узла. В противном случае для этого слова создается новый
узел со значением поля кратности, равным 1. Этот процесс называется
поис-
ком по дереву с включением.
Алгоритм поиска по дереву с включениями приведен в листинге 4.10.
17 / 23
