Деревья
У нас есть еще пара замечаний по поводу функций lookup и insert. Во-первых, они выглядят поразительно похожими на алгоритм двоичного поиска из начала главы. Это вовсе не случайно, так как они построены на той же идее "разделяй и властвуй", что и двоичный поиск, – основе логарифмических алгоритмов.
Во-вторых, эти процедуры рекурсивны. Если их переписать итеративно, то они будут похожи на двоичный поиск еще больше. На самом деле итеративная версия функции lookup может быть создана в результате элегантной трансформации рекурсивной версии. Если мы еще не нашли элемента, то последнее действие функции заключается в возврате результата, получающегося при вызове себя самой, такая ситуация называется хвостовой рекурсией (tail recursion). Эта конструкция может быть преобразована в итеративную форму, если подправить аргументы и стартовать функцию заново. Наиболее прямой метод – использовать оператор перехода goto, но цикл while выглядит чище:
После того как мы научились перемещаться по дереву, остальные стандартные операции реализуются совершенно естественно. Мы можем использовать технологии управления списками, например написать общую процедуру обхода дерева, которая вызывает заданную функцию для каждой вершины. Однако в этом случае нужно сделать выбор: когда выполнять операцию над данной вершиной, а когда обрабатывать оставшееся дерево? Ответ зависит от того, что представляет собой дерево: если оно хранит упорядоченные данные, как в дереве двоичного поиска, то мы сначала посещаем левую часть, а затем уже правую.
Иногда структура дерева отражает какое-то внутреннее упорядочение данных, как в генеалогических деревьях, и порядок обхода листьев будет зависеть от отношений, которые дерево представляет.
Фланговый порядок (in-order) обхода выполняет операцию в данной вершине после просмотра ее левого поддерева и перед просмотром правого:
Эта последовательность действий используется, когда вершины должны обходиться в порядке сортировки, например для печати их по порядку, что можно сделать так:
applyinorder(treep, printnv, "%s: %x\n");
Сразу намечается вариант сортировки: вставляем элементы в дерево, выделяем память под массив соответствующего размера, а затем используем фланговый обход для последовательного размещения их в массиве.