假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
当前回答
如果使用数组来支持二叉树,则可以用代数方法确定下一个节点。如果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)
其他回答
设v为起始顶点
设G是问题中的图
下面是不使用队列的伪代码
Initially label v as visited as you start from v
BFS(G,v)
for all adjacent vertices w of v in G:
if vertex w is not visited:
label w as visited
for all adjacent vertices w of v in G:
recursively call BFS(G,w)
#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;
}
下面的方法使用DFS算法来获取特定深度的所有节点——这与对该级别进行BFS相同。如果您找到树的深度,并对所有级别执行此操作,结果将与BFS相同。
public void PrintLevelNodes(Tree root, int level) {
if (root != null) {
if (level == 0) {
Console.Write(root.Data);
return;
}
PrintLevelNodes(root.Left, level - 1);
PrintLevelNodes(root.Right, level - 1);
}
}
for (int i = 0; i < depth; i++) {
PrintLevelNodes(root, i);
}
找到树的深度是小菜一碟:
public int MaxDepth(Tree root) {
if (root == null) {
return 0;
} else {
return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1;
}
}
我想在上面的答案中加上我的观点,如果语言支持生成器之类的东西,bfs可以协递归地完成。
首先,@Tanzelax的回答是:
宽度优先遍历传统上使用队列,而不是堆栈。队列和堆栈的性质几乎是相反的,因此试图使用调用堆栈(因此得名为堆栈)作为辅助存储(队列)几乎是注定要失败的
实际上,普通函数调用的堆栈不会像普通堆栈那样运行。但是生成器函数将暂停函数的执行,因此它给了我们产生下一层节点的子节点的机会,而无需深入研究节点的更深层次的后代。
下面的代码是Python中的递归bfs。
def bfs(root):
yield root
for n in bfs(root):
for c in n.children:
yield c
这里的直觉是:
BFS首先将根作为第一个结果返回 假设我们已经有了BFS序列,BFS中的下一层元素是序列中前一个节点的直接子节点 重复以上两个步骤
我必须实现以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;
}