Рекурсивное перемещение в ширину функционирует в Java или C++?
Вот код Java для перемещения в ширину:
void breadthFirstNonRecursive(){
Queue<Node> queue = new java.util.LinkedList<Node>();
queue.offer(root);
while(!queue.isEmpty()){
Node node = queue.poll();
visit(node);
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
}
Действительно ли возможно записать рекурсивную функцию, чтобы сделать то же?
Сначала, я думал, что это будет легко, таким образом, я выпустил это:
void breadthFirstRecursive(){
Queue<Node> q = new LinkedList<Node>();
breadthFirst(root, q);
}
void breadthFirst(Node node, Queue<Node> q){
if (node == null) return;
q.offer(node);
Node n = q.poll();
visit(n);
if (n.left != null)
breadthFirst(n.left, q);
if (n.right != null)
breadthFirst(n.right, q);
}
Затем я нашел, что это не работает. Это, на самом деле делает то же самое как это:
void preOrder(Node node) {
if (node == null) return;
visit(node);
preOrder(node.left);
preOrder(node.right);
}
Кто-либо думал об этом прежде?
3 ответа
Я не могу представить , зачем вам это нужно, когда у вас есть совершенно хорошее итеративное решение, но готово;)
void breadth_first(Node root):
Queue q;
q.push(root);
breadth_first_recursive(q)
void breadth_first_recursive(Queue q):
if q.empty() return;
Node n = q.pop()
print "Node: ", n
if (n.left) q.push(n.left)
if (n.right) q.push(n.right)
breadth_first_recursive(q)
Я должен добавить, что если вы действительно хотите пройти через узлов дерева рекурсивно, тогда вы можете выполнить DFS с параметром уровня и вывести узлы только на уровне уровне , а затем выполнить рекурсию вверх. Но это просто сумасшедший разговор, потому что вы слишком много раз пересматривали бы узлы ... Просто примите тот факт, что BFS - это итеративный алгоритм. :)
Алгоритм BFS не является рекурсивным алгоритмом (в отличие от DFS).
Можно попробовать написать рекурсивную функцию, имитирующую алгоритм, но это закончится довольно странно. Какой в этом смысл?
Вы можете использовать итеративное углубление глубины поиска, которое фактически представляет собой алгоритм широты, использующий рекурсию. Это даже лучше, чем BFS, если у вас высокий коэффициент ветвления, так как он не использует много памяти.