假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
当前回答
我必须实现以BFS顺序输出的堆遍历。它实际上不是BFS,但完成了相同的任务。
private void getNodeValue(Node node, int index, int[] array) {
array[index] = node.value;
index = (index*2)+1;
Node left = node.leftNode;
if (left!=null) getNodeValue(left,index,array);
Node right = node.rightNode;
if (right!=null) getNodeValue(right,index+1,array);
}
public int[] getHeap() {
int[] nodes = new int[size];
getNodeValue(root,0,nodes);
return nodes;
}
其他回答
在学习AlgoExpert时,对这个问题进行了改编。提示符中已经提供了以下Class。这里是python中的迭代和递归解决方案。这个问题的目标是返回一个输出数组,其中列出了按访问顺序排列的节点名称。如果遍历顺序为A -> B -> D -> F,则输出为['A','B','D','F']
class Node:
def __init__(self, name):
self.children = []
self.name = name
def addChild(self, name):
self.children.append(Node(name))
return self
递归
def breadthFirstSearch(self, array):
return self._bfs(array, [self])
def _bfs(self, array, visited):
# Base case - no more nodes to visit
if len(visited) == 0:
return array
node = visited.pop(0)
array.append(node.name)
visited.extend(node.children)
return self._bfs(array, visited)
迭代
def breadthFirstSearch(self, array):
array.append(self.name)
queue = [self]
while len(queue) > 0:
node = queue.pop(0)
for child in node.children:
array.append(child.name)
queue.append(child)
return array
#include <bits/stdc++.h>
using namespace std;
#define Max 1000
vector <int> adj[Max];
bool visited[Max];
void bfs_recursion_utils(queue<int>& Q) {
while(!Q.empty()) {
int u = Q.front();
visited[u] = true;
cout << u << endl;
Q.pop();
for(int i = 0; i < (int)adj[u].size(); ++i) {
int v = adj[u][i];
if(!visited[v])
Q.push(v), visited[v] = true;
}
bfs_recursion_utils(Q);
}
}
void bfs_recursion(int source, queue <int>& Q) {
memset(visited, false, sizeof visited);
Q.push(source);
bfs_recursion_utils(Q);
}
int main(void) {
queue <int> Q;
adj[1].push_back(2);
adj[1].push_back(3);
adj[1].push_back(4);
adj[2].push_back(5);
adj[2].push_back(6);
adj[3].push_back(7);
bfs_recursion(1, Q);
return 0;
}
下面是一个python实现:
graph = {'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F'],
'F': ['C']}
def bfs(paths, goal):
if not paths:
raise StopIteration
new_paths = []
for path in paths:
if path[-1] == goal:
yield path
last = path[-1]
for neighbor in graph[last]:
if neighbor not in path:
new_paths.append(path + [neighbor])
yield from bfs(new_paths, goal)
for path in bfs([['A']], 'D'):
print(path)
下面是一个BFS递归遍历Python实现,用于没有周期的图。
def bfs_recursive(level):
'''
@params level: List<Node> containing the node for a specific level.
'''
next_level = []
for node in level:
print(node.value)
for child_node in node.adjency_list:
next_level.append(child_node)
if len(next_level) != 0:
bfs_recursive(next_level)
class Node:
def __init__(self, value):
self.value = value
self.adjency_list = []
我想在上面的答案中加上我的观点,如果语言支持生成器之类的东西,bfs可以协递归地完成。
首先,@Tanzelax的回答是:
宽度优先遍历传统上使用队列,而不是堆栈。队列和堆栈的性质几乎是相反的,因此试图使用调用堆栈(因此得名为堆栈)作为辅助存储(队列)几乎是注定要失败的
实际上,普通函数调用的堆栈不会像普通堆栈那样运行。但是生成器函数将暂停函数的执行,因此它给了我们产生下一层节点的子节点的机会,而无需深入研究节点的更深层次的后代。
下面的代码是Python中的递归bfs。
def bfs(root):
yield root
for n in bfs(root):
for c in n.children:
yield c
这里的直觉是:
BFS首先将根作为第一个结果返回 假设我们已经有了BFS序列,BFS中的下一层元素是序列中前一个节点的直接子节点 重复以上两个步骤