Выполнение поиска в ширину рекурсивно
4 ответа
(Я предполагаю, что это всего лишь некоторые своего рода мысленное упражнение или даже трюк с домашним заданием / вопросом на собеседовании, но я полагаю, я мог бы представить какой-то странный сценарий, когда вам по какой-то причине не разрешается какое-либо пространство кучи [какой-то действительно плохой пользовательский менеджер памяти? ] пока у вас еще есть доступ к стеку ...)
При обходе в ширину традиционно используется очередь, а не стек. Природа очереди и стека в значительной степени противоположны, поэтому попытка использовать стек вызовов (который является стеком, отсюда и название) в качестве вспомогательного хранилища (очереди) в значительной степени обречен на неудачу, если вы не делаете что-то тупо нелепое со стеком вызовов, чего не должно быть.
Точно так же природа любой рекурсии без хвоста, которую вы пытаетесь реализовать, по сути, добавляет стек в алгоритм. Из-за этого больше не выполняется поиск по ширине в двоичном дереве, и, таким образом, время выполнения и многое другое для традиционных BFS больше не применяются полностью. Конечно, вы всегда можете тривиально превратить любой цикл в рекурсивный вызов, но это не какая-то значимая рекурсия.
Однако, как показали другие, есть способы реализовать что-то, что следует семантике BFS, за определенную плату.Если стоимость сравнения высока, но обход узла дешев, тогда, как это сделал @Simon Buchan , вы можете просто запустить итеративный поиск в глубину, обрабатывая только листья. Это будет означать, что в куче не хранится растущая очередь, а будет только локальная переменная глубины, а стеки будут накапливаться в стеке вызовов снова и снова по мере того, как дерево просматривается снова и снова. И, как заметил @Patrick , двоичное дерево, поддерживаемое массивом, в любом случае обычно сохраняется в порядке обхода в ширину, поэтому поиск в ширину в этом случае был бы тривиальным, также без необходимости во вспомогательной очереди.
Я не смог найти способ сделать это полностью рекурсивным (без какой-либо вспомогательной структуры данных ). Но если очередь Q передается по ссылке, тогда у вас может быть следующая дурацкая хвостовая рекурсивная функция:
BFS(Q)
{
if (|Q| > 0)
v <- Dequeue(Q)
Traverse(v)
foreach w in children(v)
Enqueue(Q, w)
BFS(Q)
}
Тупой способ:
template<typename T>
struct Node { Node* left; Node* right; T value; };
template<typename T, typename P>
bool searchNodeDepth(Node<T>* node, Node<T>** result, int depth, P pred) {
if (!node) return false;
if (!depth) {
if (pred(node->value)) {
*result = node;
}
return true;
}
--depth;
searchNodeDepth(node->left, result, depth, pred);
if (!*result)
searchNodeDepth(node->right, result, depth, pred);
return true;
}
template<typename T, typename P>
Node<T>* searchNode(Node<T>* node, P pred) {
Node<T>* result = NULL;
int depth = 0;
while (searchNodeDepth(node, &result, depth, pred) && !result)
++depth;
return result;
}
int main()
{
// a c f
// b e
// d
Node<char*>
a = { NULL, NULL, "A" },
c = { NULL, NULL, "C" },
b = { &a, &c, "B" },
f = { NULL, NULL, "F" },
e = { NULL, &f, "E" },
d = { &b, &e, "D" };
Node<char*>* found = searchNode(&d, [](char* value) -> bool {
printf("%s\n", value);
return !strcmp((char*)value, "F");
});
printf("found: %s\n", found->value);
return 0;
}
Если вы используете массив для поддержки двоичного дерева, вы можете определить следующий узел алгебраически. Если i - узел, то его дочерние узлы можно найти по 2i + 1 (для левого узла) и 2i + 2 (для правого узла). Следующий сосед узла задается i + 1, если только i не является степенью 2
Вот псевдокод для очень наивной реализации поиска по ширине на дереве двоичного поиска с поддержкой массива. Предполагается, что массив имеет фиксированный размер и, следовательно, дерево имеет фиксированную глубину. Он будет искать узлы без родителей и может создать неуправляемо большой стек.
bintree-bfs(bintree, elt, i)
if (i == LENGTH)
return false
else if (bintree[i] == elt)
return true
else
return bintree-bfs(bintree, elt, i+1)