假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
当前回答
下面是递归BFS的Scala 2.11.4实现。为了简洁起见,我牺牲了尾部调用优化,但是TCOd版本非常相似。参见@snv的帖子。
import scala.collection.immutable.Queue
object RecursiveBfs {
def bfs[A](tree: Tree[A], target: A): Boolean = {
bfs(Queue(tree), target)
}
private def bfs[A](forest: Queue[Tree[A]], target: A): Boolean = {
forest.dequeueOption exists {
case (E, tail) => bfs(tail, target)
case (Node(value, _, _), _) if value == target => true
case (Node(_, l, r), tail) => bfs(tail.enqueue(List(l, r)), target)
}
}
sealed trait Tree[+A]
case class Node[+A](data: A, left: Tree[A], right: Tree[A]) extends Tree[A]
case object E extends Tree[Nothing]
}
其他回答
下面使用Haskell对我来说似乎很自然。在树的各个层次上递归迭代(这里我将名字收集到一个大的有序字符串中,以显示树的路径):
data Node = Node {name :: String, children :: [Node]}
aTree = Node "r" [Node "c1" [Node "gc1" [Node "ggc1" []], Node "gc2" []] , Node "c2" [Node "gc3" []], Node "c3" [] ]
breadthFirstOrder x = levelRecurser [x]
where levelRecurser level = if length level == 0
then ""
else concat [name node ++ " " | node <- level] ++ levelRecurser (concat [children node | node <- level])
下面是一个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 = []
二进制(或n-ary)树的BFS可以在没有队列的情况下递归完成,如下所示(在Java中):
public class BreathFirst {
static class Node {
Node(int value) {
this(value, 0);
}
Node(int value, int nChildren) {
this.value = value;
this.children = new Node[nChildren];
}
int value;
Node[] children;
}
static void breathFirst(Node root, Consumer<? super Node> printer) {
boolean keepGoing = true;
for (int level = 0; keepGoing; level++) {
keepGoing = breathFirst(root, printer, level);
}
}
static boolean breathFirst(Node node, Consumer<? super Node> printer, int depth) {
if (depth < 0 || node == null) return false;
if (depth == 0) {
printer.accept(node);
return true;
}
boolean any = false;
for (final Node child : node.children) {
any |= breathFirst(child, printer, depth - 1);
}
return any;
}
}
按升序遍历打印数字1-12的示例:
public static void main(String... args) {
// 1
// / | \
// 2 3 4
// / | | \
// 5 6 7 8
// / | | \
// 9 10 11 12
Node root = new Node(1, 3);
root.children[0] = new Node(2, 2);
root.children[1] = new Node(3);
root.children[2] = new Node(4, 2);
root.children[0].children[0] = new Node(5, 2);
root.children[0].children[1] = new Node(6);
root.children[2].children[0] = new Node(7, 2);
root.children[2].children[1] = new Node(8);
root.children[0].children[0].children[0] = new Node(9);
root.children[0].children[0].children[1] = new Node(10);
root.children[2].children[0].children[0] = new Node(11);
root.children[2].children[0].children[1] = new Node(12);
breathFirst(root, n -> System.out.println(n.value));
}
下面是一个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)
下面的方法使用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;
}
}