递归执行广度优先搜索

Question

假设您希望以递归方式实现广度优先搜索二叉树.你会怎么做？

是否可以仅使用调用堆栈作为辅助存储？

Answer 1

(我假设这只是某种思考练习,甚至是一个技巧家庭作业/面试问题,但我想我可以想象一些奇怪的情况,你出于某种原因不允许任何堆空间[一些非常糟糕的习惯]内存管理器？一些奇怪的运行时/操作系统问题？],你仍然可以访问堆栈...)

广度优先遍历传统上使用队列,而不是堆栈.队列和堆栈的性质完全相反,所以尝试使用调用堆栈(这是一个堆栈,因此名称)作为辅助存储(队列)几乎注定要失败,除非你正在做对于你不应该使用的调用堆栈,这是一种愚蠢的荒谬.

同样,您尝试实现的任何非尾递归的本质实质上是向算法添加堆栈.这使得它不再是二叉树上的广泛搜索,因此传统BFS的运行时间和其他内容不再完全适用.当然,你总是可以将任何循环简单地转换为递归调用,但这不是任何有意义的递归.

但是,正如其他人所证明的那样,有些方法可以以某种代价实现遵循BFS语义的东西.如果比较的成本很高但节点遍历很便宜,那么就像@Simon Buchan那样,你可以简单地运行迭代深度优先搜索,只处理叶子.这意味着堆中不存在增长的队列,只是一个本地深度变量,并且当树一遍又一遍地遍历时,堆栈在调用堆栈上反复建立.正如@Patrick所指出的那样,由数组支持的二叉树通常以广度优先的遍历顺序存储,因此对该广度优先搜索将是微不足道的,也不需要辅助队列.

Answer 2

如果使用数组来支持二叉树,则可以用代数方式确定下一个节点.如果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)        

Answer 3

我找不到完全递归的方法(没有任何辅助数据结构).但是如果队列Q通过引用传递,那么你可以使用以下愚蠢的尾递归函数:

BFS(Q)
{
  if (|Q| > 0)
     v <- Dequeue(Q)
     Traverse(v)
     foreach w in children(v)
        Enqueue(Q, w)    

     BFS(Q)
}

Answer 4

以下方法使用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;
    }
}

Answer 5

Java中的简单BFS和DFS递归:
只需在堆栈/队列中推送/提供树的根节点并调用这些函数.

public static void breadthFirstSearch(Queue queue) {

    if (queue.isEmpty())
        return;

    Node node = (Node) queue.poll();

    System.out.println(node + " ");

    if (node.right != null)
        queue.offer(node.right);

    if (node.left != null)
        queue.offer(node.left);

    breadthFirstSearch(queue);
}

public static void depthFirstSearch(Stack stack) {

    if (stack.isEmpty())
        return;

    Node node = (Node) stack.pop();

    System.out.println(node + " ");

    if (node.right != null)
        stack.push(node.right);

    if (node.left != null)
        stack.push(node.left);

    depthFirstSearch(stack);
}

Answer 6

这是一个 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 = []

Answer 7

我想在最上面的答案中添加我的观点，因为如果该语言支持诸如生成器之类的东西，则 bfs 可以共同递归地完成。

首先，@Tanzelax 的回答是：

广度优先遍历传统上使用队列，而不是堆栈。队列和堆栈的性质几乎相反，因此尝试使用调用堆栈（这是一个堆栈，因此得名）作为辅助存储（队列）几乎注定会失败

事实上，普通函数调用的堆栈的行为与普通堆栈不同。但是生成器函数将暂停函数的执行，因此它使我们有机会生成下一级节点的子节点，而无需深入研究该节点的更深层次的后代。

下面的代码是Python中的递归bfs。

def bfs(root):
  yield root
  for n in bfs(root):
    for c in n.children:
      yield c

这里的直觉是：

1. bfs first 将返回根作为第一个结果
2. 假设我们已经有了 bfs 序列，bfs 中的下一级元素是序列中前一个节点的直接子节点
3. 重复以上两个过程